Scalable Multi-Agent Pathfinding on Grid Maps with Tractability and Completeness Guarantees

Cindy Wang (SoCS CECS)

CS HDR MONITORING AI Research Group

DATE: 2010-04-15
TIME: 14:00:00 - 14:30:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
Navigating multiple mobile units on grid maps is a challenging problem with many real-life applications. A centralized search in the combined state space of all units scales very poorly in practice. Traditional approaches decompose the initial problem into a series of smaller searches, improving the scalability and the speed. However, such methods are incomplete. They provide no guarantees with respect to the total running time, and are unable to apriori tell whether they would succeed in finding a solution to a given instance.

Recently, algorithms have been introduced that are complete on well-specified subclasses of problems. They also provide low-polynomial upper bounds for the running time, the solution length and the memory requirements. However, the speed and scale-up capabilities of such algorithms, compared to incomplete methods, has been an open question in the past.

In this talk we present steps towards bridging the gap between the two categories of algorithms, combining strengths specific to each of them. We extend MAPP (Wang and Botea, 2009), a recent algorithm in the latter category. The resulting algorithm is competitive, in terms of empirical performance, with state-of-the-art incomplete algorithms, while maintaining and even extending the theoretical properties of the original MAPP, such as its completeness range.

BIO:
PhD student in Computer Science. http://users.cecs.anu.edu.au/~cwang