Richard Borie

AAMAS Conference 2010 Conference Paper

ESP: Pursuit Evasion on Series-Parallel Graphs

• Kenny Daniel
• Richard Borie
• Sven Koenig
• Craig Tovey

We develop a heuristic approach, called ESP, that solves large pursuit-evasionproblems on series-parallel (that is, treewidth-2) graphs quickly and withsmall costs. It exploits their topology by performing dynamic programming ontheir decomposition graphs. We show that ESP scales up to much larger graphsthan a strawman approach based on previous results from the literature.

IJCAI Conference 2009 Conference Paper

• Richard Borie
• Craig Tovey
• Sven Koenig

We study pursuit-evasion problems where a number of pursuers have to clear a given graph. We study when polynomial-time algorithms exist to determine how many pursuers are needed to clear a given graph and how a given number of pursuers should move on the graph to clear it with either a minimum sum of their travel distances or minimum task-completion time. We generalize prior work to both unit-width arbitrary-length and unitlength arbitrary-width graphs and derive both algorithms and complexity results for a variety of graph topologies. In this context, we describe a polynomial-time algorithm, called CLEARTHETREE, that is much shorter and algorithmically simpler than the state-of-the-art algorithm for the minimum pursuer problem on trees. Our theoretical research lays a firm theoretical foundation for pursuit evasion on graphs and informs practitioners about which problems are easy and which ones are hard.

AAAI Conference 2008 Conference Paper

Agent Coordination with Regret Clearing

• Sven Koenig
• Richard Borie
• Vangelis Markakis

Sequential single-item auctions can be used for the distributed allocation of tasks to cooperating agents. We study how to improve the team performance of sequential singleitem auctions while still controlling the agents in real time. Our idea is to assign that task to agents during the current round whose regret is large, where the regret of a task is defined as the difference of the second-smallest and smallest team costs resulting from assigning the task to the secondbest and best agent, respectively. Our experimental results show that sequential single-item auctions with regret clearing indeed result in smaller team costs than standard sequential single-item auctions for three out of four combinations of two different team objectives and two different capacity constraints (including no capacity constraints).