# Doctoral Consortium Abstracts

DC7
Multi-agent path planning is a challenging problem with numerous real-life applications, including robotics, logistics, military operations planning, disaster rescue, and computer games.
We look at navigating large numbers of mobile units to their targets on navigation graphs such as grid maps.
The size of problems examined is significantly larger than can be handled using optimal multi-agent pathfinding algorithms in practice.
We introduced Mapp, a *tractable* algorithm for multi-agent path planning on undirected graphs.
Mapp and its extended versions are complete on well specified and tractably testable classes of problems.
They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions.
Experiments on realistic game grid maps, with uniformly randomly generated start and target locations for each unit, show Mapp as a state-of-the-art multi-agent pathfinding algorithm in terms of scalability and success ratio (i.e., percentage of solved units).
Even on challenging scenarios with 2000 units, Mapp solves 92% to 99.7% of units.
Far and Whca, two fast but incomplete algorithms that were previously state-of-the-art in terms of scalability, solve as few as 17.5% and 12.3% of these problems.
The quality of Mapp's solutions is empirically analyzed using multiple quality criteria: total travel distance, makespan, and sum of actions (including move and wait actions).
Mapp is competitive in terms of solution quality and speed with Far and Whca*. Mapp further provides the formal characterizations that Far and Whca* lack, on problems it can solve as well as low-polynomial upper bounds on the resources required.
As optimal algorithms have limited scalability, we evaluated the solution quality of suboptimal algorithms using lower bounds of optimal values. We showed that Mapp's solutions have a reasonable quality.
For example, Mapp's total travel distance is on average 19% longer than a lower bound on the optimal value.
Massively Multi-Agent Pathfinding made Tractable, Efficient, and with Completeness Guarantees
Ko-Hsin Cindy Wang

DC15
Game theory is a useful tool for reasoning about interactions between agents and in turn aiding in the decisions of those agents. In fact, Stackelberg games are natural models for many important applications such as oligopolistic markets and security domains. Indeed, Stackelberg games are at the heart of three deployed systems, ARMOR; IRIS; and GUARDS, for aiding security officials in making critical resource allocation decisions. In Stackelberg games, one player, the leader, commits to a strategy and follower makes her decision with knowledge of the leader's commitment. Existing algorithms for Stackelberg games efficiently find optimal solutions (leader strategy), however, they critically assume that the follower plays optimally. Unfortunately, in many applications, agents face human followers (adversaries) who - because of their bounded rationality and possibly limited information of the leader strategy - may deviate from their expected optimal response. Not considering these likely deviations when dealing with human adversaries may cause an unacceptable degradation in the leader's reward, particularly in security applications where these algorithms have seen deployment. To that end, I explore robust algorithms for agent interactions with human adversaries in security applications. I have developed a number of robust algorithms for a class of games known as “Security Games” and am working toward enhancing these approaches for a richer models of these games that I developed known as “Security Circumvention Games”.
Real-World Security Games: Toward Addressing Human Decision-Making Uncertainty
James Pitahas 2 papers