RAIDER: Resilient Actionable Intelligence for Distributed Environment understanding and Reasonings
Motion planning and trajectory generation are crucial problems to be solved for the realization of autonomous systems in real-life application. Although, such problems can be solved using optimal control or dynamic programming in theory, the computational complexity prohibits the direct application of these techniques, especially when the dimension of the problem is high (e.g., robotic arms, under-actuated aerial vehicles, robot swam). Alleviating the curse of dimensionality, sampling-based motion planning algorithms have gained large popularity for its ability to handle higher dimensions and kino-dynamic constraints.
Utilizing distributed multiple trees in a randomized search has shown certain advantages over its single-tree counterpart, as a multi-tree framework allows a parallel and distributed exploration of the search space with fast exploitation of the local connectivity. Essentially, the multi-tree framework is a generalization of the incremental search methods which seek for a minimal effort to re-plan given the previous search result to the objective of utilizing not only temporally distributed but also spatially distributed search results for better informed planning in dynamical environments.
We solve a single-query planning problem in which distributed multi-agent in the same search space builds their individual trees which hold valuable information about the local topology of the obstacle free search space. We utilize the information encoded as disjoint multiple trees to exploit the local connectivity of the search space and to explore in a more parallelized fashion. The key problem is two-fold, first is to reduce the inter-agent communication by exploiting the existing paths as much as possible, and second is to find an optimal solution with respect to the merged graph of disjoint trees for a single-query planning problem to guarantee an asymptotic optimality. The proposed method solves the first problem by formulating multi-agent connection as a high-level planning problem such that the expensive collision check is prioritized for promising disjoint trees with a heuristic guidance, and then uses A* algorithm to rewire the identified disjoint trees to ensure the optimal connection.
Sponsors
This project is funded by ONR.
