Date of Award
Spring 5-1-2015
Degree Type
Honors College Thesis
Department
Computing
First Advisor
Bikramjit Banerjee
Abstract
Multiagent path finding (MAPF) is the process of searching and planning agent paths for multiple agents. Each agent has its own start and goal position, and the A* search algorithm is generally used for solving this problem. This thesis proposes an alternative algorithm, Conflict Based Search Agent Persistence (CBSAP), to the basic Conflict Based Search (CBS) (Sharon et al. 2012) which has shown to solve problems CBS and A* could not solve. CBS is a two-‐ level algorithm. At the high level, constraints are created and added to the Constraint Tree, and then searched for a valid solution within the Constraint Tree. At the low level, individual agents calculate new paths along with the constraints given providing the solutions inside each node of the Constraint Tree. This thesis focuses on the method of resolving conflicts within the high level algorithm: in some cases, conflicts could encounter after an agent reaches its goal. The main idea is to implement a solution that does not assume an agent disappears after reaching its goal. Preventing agents from immediately occupying the previous location of other agents. We analyzed our new approach compared to the CBS algorithm and provide experimental results and theoretical proof demonstrating that it outperforms CBS and GJA*.
Copyright
Copyright for this thesis is owned by the author. It may be freely accessed by all users. However, any reuse or reproduction not covered by the exceptions of the Fair Use or Educational Use clauses of U.S. Copyright Law or without permission of the copyright holder may be a violation of federal law. Contact the administrator if you have additional questions.
Recommended Citation
Davis, Caleb E., "Multiagent Path Finding with Agent Persistence" (2015). Honors Theses. 454.
https://aquila.usm.edu/honors_theses/454