Decentralized path planning for multiple agents in complex environments using rapidly-exploring random trees

This thesis presents a novel approach to address the challenge of planning paths for real-world multi-agent systems operating in complex environments. The technique developed, the Decentralized Multi-Agent Rapidly-exploring Random Tree (DMARRT) algorithm, is an extension of the CL-RRT algorithm to the multi-agent case, retaining its ability to plan quickly even with complex constraints. Moreover, a merit-based token passing coordination strategy is also presented as a core component of the DMA-RRT algorithm. This coordination strategy makes use of the tree of feasible trajectories grown in the CL-RRT algorithm to dynamically update the order in which agents plan. This reordering is based on a measure of each agent's incentive to replan and allows agents with a greater incentive to plan sooner, thus reducing the global cost and improving the team's overall performance. An extended version of the algorithm, Cooperative DMA-RRT, is also presented to introduce cooperation between agents during the path selection process. The paths generated are proven to satisfy inter-agent constraints, such as collision avoidance, and a set of simulation and experimental results verify the algorithm's performance. A small scale rover is also presented as part of a practical test platform for the DMA-RRT algorithm.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2010

Author dc:creator

• Desaraju, Vishnu R. (Vishnu Rajeswar)

Advisor dc:contributor.advisor

• Jonathan P. How.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/62480

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/62480