AAMAS 2011 - May 2-6, 2011 - Taipei, Taiwan

Doctoral Consortium Abstracts


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


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


My research focuses on understanding and analyzing prediction markets using multi-agent system and game theory-based tools. Prediction markets, in which trading agents trade outcomes of events (like “Barack Obama will win the presidential election”), are similar to stock markets in that they aggregate the beliefs of many agents with different information about an event, and produce a single number, a market price. The main challenge in designing, deploying and operating prediction markets is the lack of understanding about what makes a successful prediction market, i.e.(1) how information affects traders and prediction market price, (2) how to incentivize traders to reveal their socially useful information, and (3) under what conditions do prediction markets perform the best. I address the first question by developing a multi-agent system that is used to analyze the effect of information on the prediction market performance and show that our model provides a better understanding and novel insights into the behavior of prediction markets and its participants. For the second question I propose a correlated equilibrium strategy for the trading agents within a partially observable stochastic game-based model that incentivizes traders to reveal their true beliefs and show that the market's participants following my strategy achieve higher profit by 35-127%. And for the third question I apply Boolean Network techniques to study the dynamics of prediction markets under various conditions and show under what parameter values the prediction market stabilizes and how its dynamics change with the introduction of noise and increased number of traders. A Multi-Agent System for Predicting Future Event Outcomes Janyl Jumadinovahas 2 papers


Copyright © 2011 IFAAMAS