Craig A. Tovey

AAMAS Conference 2025 Conference Paper

On the Gale-Shapley Algorithm for Stable Matchings with a Partial Honesty Nash Refinement

• James P. Bailey
• Craig A. Tovey

It has long been known that every individually rational matching is obtainable by some Nash equilibrium — even those that make little sense in practice. In the social choice and voting literature, Nash refinements are commonly used to avoid these spurious equilibria. In this paper, we examine the Gale-Shapley algorithm (deferred acceptance) where agents behave strategically but are minimally dishonest, a common refinement in the social choice and voting literature. Under this condition we show that when men propose, every equilibrium corresponds to the woman-optimal marriage, thereby yielding a unique prediction for the outcome for the stable matching problem.

AAMAS Conference 2025 Conference Paper

The Price of Anarchy in Spatial Social Choice

• James P. Bailey
• Craig A. Tovey

Except for a few strategy-proof mechanisms on the real line, spatial social choice mechanisms are usually manipulable. But is it wise to treat all manipulations as equally bad? We use the price of anarchy to make finer distinctions than between “strategy-proof” and “manipulable. ” The price of anarchy measures how much strategic behavior can alter the cost in social choice. Supported by experimental economics data, our measure employs a novel minimal dishonesty criterion to refine the set of Nash equilibria. Using the price of anarchy, we study standard spatial selection rules and uncover a class of selection rules that are immune to the negative consequences of manipulation despite remaining manipulable. This is in contrast to standard approaches that sacrifice other beneficial properties, e. g. , unbiased tie-breaking, to gain strategy-proofness. The concepts herein could be applied to other social choice scenarios in which a publicly known mechanism relies on private information.

AAMAS Conference 2024 Conference Paper

Impact of Tie-Breaking on the Manipulability of Elections

• James P. Bailey
• Craig A. Tovey

In this paper, we quantify the impact of manipulation using the price of anarchy measurement and study the impact of the lexicographic and the random candidate tie-breaking rules. We show that neither dominates the other in terms of mitigating the impact of manipulation. Specifically, we show that the random candidate tie-breaking rule lowers the impact of manipulation in plurality elections whereas the lexicographic tie-breaking rule lowers the impact of manipulation in elections determined by majority judgment.

AIJ Journal 2021 Journal Article

Path-length analysis for grid-based path planning

• James P. Bailey
• Alex Nash
• Craig A. Tovey
• Sven Koenig

In video games and robotics, one often discretizes a continuous 2D environment into a regular grid with blocked and unblocked cells and then finds shortest paths for the agents on the resulting grid graph. Shortest grid paths, of course, are not necessarily true shortest paths in the continuous 2D environment. In this article, we therefore study how much longer a shortest grid path can be than a corresponding true shortest path on all regular grids with blocked and unblocked cells that tessellate continuous 2D environments. We study 5 different vertex connectivities that result from both different tessellations and different definitions of the neighbors of a vertex. Our path-length analysis yields either tight or asymptotically tight worst-case bounds in a unified framework. Our results show that the percentage by which a shortest grid path can be longer than a corresponding true shortest path decreases as the vertex connectivity increases. Our path-length analysis is topical because it determines the largest path-length reduction possible for any-angle path-planning algorithms (and thus their benefit), a class of path-planning algorithms in artificial intelligence and robotics that has become popular.

SoCS Conference 2010 Conference Paper

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

• Alex Nash
• Sven Koenig
• Craig A. 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 8-neighbor 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.

IROS Conference 2007 Conference Paper

Multi-robot routing with rewards and disjoint time windows

• Justin Melvin
• Pinar Keskinocak
• Sven Koenig
• Craig A. Tovey
• Banu Yuksel Ozkaya

Multiple robots are often faster and more fault- tolerant than single robots for applications such as planetary exploration and search and rescue. We study applications where robots move in two-dimensional terrain and have to visit targets of given priorities during given time windows that do not overlap. We analyze the complexity of these coordination tasks and, where possible, use techniques from operations research to develop coordination methods that are efficient and optimize the team performance. We then develop auction-based coordination methods that build on these results and show experimentally that they run in seconds and achieve good team performance for NP-hard coordination tasks.

SODA Conference 2006 Conference Paper

A near-tight approximation lower bound and algorithm for the kidnapped robot problem

• Sven Koenig
• Apurva Mudgal
• Craig A. Tovey

IROS Conference 2006 Conference Paper

Improving Sequential Single-Item Auctions

• Xiaoming Zheng
• Sven Koenig
• Craig A. Tovey

We study how to improve sequential single-item auctions that assign targets to robots for exploration tasks such as environmental clean-up, space-exploration, and search and rescue missions. We exploit the insight that the resulting travel distances are small if the bidding and winner-determination rules are designed to result in hillclimbing, namely to assign an additional target to a robot in each round of the sequential single-item auction so that the team cost increases the least. We study the impact of increasing the lookahead of hillclimbing and using roll-outs to improve the evaluation of partial target assignments. We describe the bidding and winner-determination rules of the resulting sequential single-item auctions and evaluate them experimentally, with surprising results: larger lookaheads do not improve sequential single-item auctions reliably while only a small number of roll-outs in early rounds already improve them substantially

ICRA Conference 2003 Conference Paper

Improved analysis of D

• Craig A. Tovey
• Sam Greenberg
• Sven Koenig

D* is a planning method that always routes a robot in initially unknown terrain from its current location to a given goal location along a shortest presumed unblocked path. The robot moves along the path until it discovers new obstacles and then repeats the procedure. D* has been used on a large number of robots. It is therefore important to analyze the resulting travel distance. Previously, there has been only one analysis of D*, and it has two shortcomings. First, to prove the lower bound, it uses a physically unrealistic example graph which has distances that do not correspond to distances on a real map. We show that the lower bound is not smaller for grids, the kind of map-based graph on which D* is usually used. Second, there is a large gap between the upper and lower bounds on the travel distance. We considerably reduce this gap by decreasing the upper bound on arbitrary graphs, including grids. To summarize, we provide new, substantially tighter bounds on the travel distance of D* on grids, thus providing a realistic analysis for the way D* is actually used.

IROS Conference 2003 Conference Paper

Improved analysis of greedy mapping

• Craig A. Tovey
• Sven Koenig

We analyze greedy mapping, a simple mapping method that has successfully been used on mobile robots. Greedy mapping moves the robot from its current location on a shortest path towards a closest unvisited, unscanned or informative location, until the terrain is mapped. Previous work has resulted in upper and lower bounds on its worst-case travel distance but there was a large gap between the bounds. In this paper, we reduce the gap substantially by decreasing the upper bound from /spl Oscr/; (|V|/sup 3/2/) to /spl Oscr/; (|V|ln|V|) edge traversals, where |V| is the number of vertices of the graph. This upper bound demonstrates that the travel distance of greedy mapping is guaranteed to be small and thus suggests that greedy mapping is indeed a reasonable mapping method. The guaranteed good performance of greedy mapping is robust in that it holds for different versions of greedy mapping, regardless of sensor type and sensor range.

IROS Conference 2001 Conference Paper

Greedy localization

• Craig A. Tovey
• Sven Koenig

We show that finding localization plans with optimal worst-case execution time for localization tasks with short-range sensors in discretized domains is NP-hard, even within a logarithmic factor. This strongly suggests that finding and executing localization plans with optimal or even near-optimal worst-case execution time cannot be done in polynomial time. Greedy localization methods interleave planning and execution and keep the amount of planning performed between moves small. We analyze one such greedy localization method, the delayed planning architecture, and show that it can find and execute localization plans in polynomial time and thus substantially reduce the sum of planning and execution time compared to localization methods that find localization plans with optimal or near-optimal execution time. We also characterize how suboptimal the execution time of its localization plans can be. These results provide a first step towards analyzing other greedy localization methods.

ICRA Conference 2001 Conference Paper

Greedy Mapping of Terrain

• Sven Koenig
• Craig A. Tovey
• William Halliburton

We study a greedy mapping method that always moves the robot from its current location to the closest location that it has not visited (or observed) yet, until the terrain is mapped. Although one does not expect such a simple mapping method to minimize the travel distance of the robot, we present analytical results that show (perhaps surprisingly) that the travel distance of the robot is reasonably small. This is interesting because greedy mapping has a number of desirable properties. It is simple to implement and integrate into complete robot architectures. It does not need to have control of the rebut at all times, takes advantage of prior knowledge about parts of the terrain (if available), and can be used by several robots cooperatively.

SODA Conference 1999 Conference Paper

Online Resource Minimization

• Anton J. Kleywegt
• Vijay S. Nori
• Martin W. P. Savelsbergh
• Craig A. Tovey

SODA Conference 1994 Conference Paper

New Results on the Old k-Opt Algorithm for the TSP

• Barun Chandra
• Howard J. Karloff
• Craig A. Tovey