In systems, where multiple robots operate in a shared area, one has to ensure that the robots do not collide not only with known static and dynamic obstacles, but also with each other. Such a task can be accomplished in the framework of multi-robot trajectory planning by planning coordinated trajectories for the whole multi-robot team. However, the problem of finding coordinated trajectories is known to be NP-hard even for the simplest models of robots. In our work we investigate tractable subclasses of the problem and speed-up techniques for general formulation of the problem.
Decentralized Decoupled Techniques with Guarantees
The known complete approaches for multi-robot trajectory planning suffer from computational complexity that is exponential in the number of robots. In our work we characterize a class of environments called well-formed infrastructures, where solution can be computed using a decoupled approach efficiently (in polynomial time in the number of robots) in a guaranteed manner.
Sampling-based Techniques for Multi-robot Path Planning
The state-of-the-art algorithms for multi-robot pathfinding typically rely on some heuristic forward-search algorithm, where A* is often the algorithm of choice. We proposed MA-RRT*, a novel algorithm for multi-agent motion planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm called RRT*.