Decentralized, Noncooperative Multirobot Path Planning with Sample-BasedPlanners

• Main Author: Le, William
• Format: Text
• Language: unknown
• Published: DigitalCommons@CalPoly 2020
• Subjects: Path Planning; Robotics; Multi-robot; Controls and Control Theory; Orca
• Online Access: https://digitalcommons.calpoly.edu/theses/2557; https://doi.org/10.15368/theses.2020.120; https://digitalcommons.calpoly.edu/context/theses/article/3693/viewcontent/LeThesis.pdf; https://digitalcommons.calpoly.edu/context/theses/article/3693/filename/0/type/additional/viewcontent/test_replan_nodes.csv.gz; https://digitalcommons.calpoly.edu/context/theses/article/3693/filename/1/type/additional/viewcontent/results_2.csv.gz; https://digitalcommons.calpoly.edu/context/theses/article/3693/filename/2/type/additional/viewcontent/nodes_2.csv.gz; https://digitalcommons.calpoly.edu/context/theses/article/3693/filename/3/type/additional/viewcontent/robot_time_2.csv.gz; https://digitalcommons.calpoly.edu/context/theses/article/3693/filename/4/type/additional/viewcontent/waypoints_2.csv.gz

In this thesis, the viability of decentralized, noncooperative multi-robot path planning algorithms is tested. Three algorithms based on the Batch Informed Trees (BIT*) algorithm are presented. The first of these algorithms combines Optimal Reciprocal Collision Avoidance (ORCA) with BIT*. The second of these algorithms uses BIT* to create a path which the robots then follow using an artificial potential field (APF) method. The final algorithm is a version of BIT* that supports replanning. While none of these algorithms take advantage of sharing information between the robots, the algorithms are able to guide the robots to their desired goals, with the algorithm that combines ORCA and BIT* having the robots successfully navigate to their goals over 93% for multiple environments with teams of two to eight robots.