Craig Tovey

AAAI Conference 2016 Conference Paper

Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem

• Hang Ma
• Craig Tovey
• Guni Sharon
• T. K. Kumar
• Sven Koenig

We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robotrouting problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for flowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multiagent path-finding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a flow-based ILP formulation and an adaptation of conflict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances.

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.

AAAI Conference 2010 Conference Paper

Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D

• Alex Nash
• Sven Koenig
• Craig Tovey

Grids with blocked and unblocked cells are often used to represent continuous 2D and 3D environments in robotics and video games. The shortest paths formed by the edges of 8neighbor 2D grids can be up to ≈ 8% longer than the shortest paths in the continuous environment. Theta* typically finds much shorter paths than that by propagating information along graph edges (to achieve short runtimes) without constraining paths to be formed by graph edges (to find short “any-angle” paths). We show in this paper that the shortest paths formed by the edges of 26-neighbor 3D grids can be ≈ 13% longer than the shortest paths in the continuous environment, which highlights the need for smart path planning algorithms in 3D. Theta* can be applied to 3D grids in a straight-forward manner, but it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex and thus it performs many more line-of-sight checks per expanded vertex on a 26-neighbor 3D grid than on an 8-neighbor 2D grid. We therefore introduce Lazy Theta*, a variant of Theta* which uses lazy evaluation to perform only one line-of-sight check per expanded vertex (but with slightly more expanded vertices). We show experimentally that Lazy Theta* finds paths faster than Theta* on 26-neighbor 3D grids, with one order of magnitude fewer line-of-sight checks and without an increase in path length.

AAAI Conference 2010 Conference Paper

Progress on Agent Coordination with Cooperative Auctions

• Sven Koenig
• Pinar Keskinocak
• Craig Tovey

Auctions are promising decentralized methods for teams of agents to allocate and re-allocate tasks among themselves in dynamic, partially known and time-constrained domains with positive or negative synergies among tasks. Auctionbased coordination systems are easy to understand, simple to implement and broadly applicable. They promise to be efficient both in communication (since agents communicate only essential summary information) and in computation (since agents compute their bids in parallel). Artificial intelligence research has explored auction-based coordination systems since the early work on contract networks (Smith 1980), mostly from an experimental perspective. This overview paper describes our recent progress towards creating a framework for the design and analysis of cooperative auctions for agent coordination.

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.

IJCAI Conference 2007 Conference Paper

• Sven Koenig
• Craig Tovey
• Xiaoming Zheng
• Ilgaz Sungur

We study auction-like algorithms for the distributed allocation of tasks to cooperating agents. To reduce the team cost of sequential single-item auction algorithms, we generalize them to assign more than one additional task during each round, which increases their similarity to combinatorial auction algorithms. We show that, for a given number of additional tasks to be assigned during each round, every agent needs to submit only a constant number of bids per round and the runtime of winner determination is linear in the number of agents. The communication and winner determination costs do not depend on the number of tasks and thus scale to a large number of tasks for small bundle sizes. We then demonstrate empirically that the team cost of sequential bundle-bid single-sale (= single-item) auction algorithms can be substantially smaller than that without bundles for multi-agent routing problems with capacity constraints.

AIJ Journal 2003 Journal Article

Performance bounds for planning in unknown terrain

• Sven Koenig
• Craig Tovey
• Yuri Smirnov

Planning in nondeterministic domains is typically intractable due to the large number of contingencies. Two techniques for speeding up planning in nondeterministic domains are agent-centered search and assumption-based planning. Both techniques interleave planning in deterministic domains with plan execution. They differ in how they make planning deterministic. To determine how suboptimal their plans are, we study two planning methods for robot navigation in initially unknown terrain that have successfully been used on mobile robots but not been analyzed before. The planning methods differ both in the technique they use to speed up planning and in the robot-navigation task they solve. Greedy Mapping uses agent-centered search to map unknown terrain. Dynamic A∗ uses assumption-based planning to navigate to a given goal location in unknown terrain. When we formalize abstractions of these planning methods on undirected graphs G=(V, E), they turn out to be similar enough that we are able to analyze their travel distance in a unified way. We discover that neither method is optimal in a worst-case sense, by a factor of Ω(log|V|/loglog|V|). We also derive factor O( |V| ) upper bounds to show that these methods are not very badly sub-optimal in this sense. These results provide a first step towards explaining the good empirical results that have been reported about Greedy Mapping and Dynamic A∗ in the experimental literature. More generally, they show how to use tools from graph theory to analyze the plan quality of practical planning methods for nondeterministic domains.