| Abstract: |  Multi-agent path coordination is essential for navigation of multiple robots in a common environment. In this thesis we study a problem of multi-agent path coordination in a continuous space with polygonal obstacles. This problem is challenging because it may require planning in a state space exponential to the number of agents. The well known techniques that are able to solve this problem are reactive collision avoidance and sampling based planning. In this thesis we provide an overview of a widely used approach for reactive collision avoidance - a velocity obstacle. We also study the sampling based planning approach, focusing on a well known RRT* algorithm.
A state of the art reactive collision avoidance technique - ORCA, as well as the RRT* algorithm both have limited coverage of the problem instance space. We propose a new algorithm - ORCA-RRT*, which combines both mentioned techniques. We find that this approach is able to benefit from both its parts resulting in better coverage of the problem instance space along with higher quality of the provided solutions.
We compare the performance of our ORCA-RRT* algorithm with the reactive technique as well as the RRT* planning algorithm. We experimentally show that a) ORCA-RRT* is able to overcome local minima, which occur in many dense problem instances and cause a significant decrease in the performance of the local reactive collision avoidance technique and b) ORCA-RRT* solves many instances with high number of agents, which other RRT*-based algorithms are not able to solve due to the exponential growth of the state space with the number of agents.
|
|---|