Links

Tools

Export citation

Search in Google Scholar

Multiagent Path finding with Agent Persistence

Published in 2015 by Caleb E. Davis
This paper was not found in any repository; the policy of its publisher is unknown or unclear.
This paper was not found in any repository; the policy of its publisher is unknown or unclear.

Full text: Unavailable

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

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