Date of Award

5-1-2015

Degree Type

Honors College Thesis

Department

Computing

First Advisor

Bikramjit Banerjee, Ph.D.

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*.

Available for download on Tuesday, March 02, 2219

Share

COinS