We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robot-routing 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 multi-agent 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.

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. Auction-based 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, 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.

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.

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.

Localization, which is the determination of one's location in a known terrain, is a fundamental task for autonomous robots. This paper presents several new basic theoretical results about localization. We show that, even under the idealized assumptions of accurate sensing and perfect actuation, it is intrinsically difficult to localize a robot with a travel distance that is close to minimal. Our result helps to theoretically justify the common use of fast localization heuristics, such as greedy localization, which always moves the robot to a closest informative location (where the robot makes an observation that decreases the number of its possible locations). We show that the travel distance of greedy localization is much larger than minimal in some terrains because the closest informative location can distract greedy localization from a slightly farther, but much more informative, location. However, we also show that the travel distance of greedy localization can be larger, but not much larger, than the terrain sizen. Thus, the travel distance of greedy localization scales well with the terrain size and is much larger than minimal in some terrains, not because it is large with respect to the terrain size, but because the minimal travel distance is exceptionally small in these terrains. As a corollary to our analysis, we show that the travel distance of greedy mapping (which always moves the robot to a closest location, where it makes an observation that increases its knowledge of the terrain) cannot be much larger than the terrain size. In theoretical terms, we prove the NP-hardness of minimization of travel distance for localization to within a logarithmic factor of the terrain size. We prove that the travel distance of greedy localization is at least ordern/ log2nlarger than minimal in some terrains and that it is at least ordernlogn/ log lognin the worst case. Finally, we prove that the travel distance of both greedy localization and greedy mapping is at most ordernlogn. Previously, it was only known that it is NP-hard to localize with minimal travel distance and that the travel distances of greedy localization and greedy mapping are at most ordern3/2.

Localization is a fundamental problem in robotics. The “kidnapped robot” possesses a compass and map of its environment; it must determine its location at a minimum cost of travel distance. The problem is NP-hard [G. Dudek, K. Romanik, and S. Whitesides, SIAM J. Comput., 27 (1998), pp. 583–604] even to minimize within factor $c\log n$ [C. Tovey and S. Koenig, Proceedings of the National Conference on Artificial Intelligence, Austin, TX, 2000, pp. 819–824], where n is the map size. No approximation algorithm has been known. We give an $O(\log^3n)$-factor algorithm. The key idea is to plan travel in a “majority-rule” map, which eliminates uncertainty and permits a link to the $\frac{1}{2}$-Group Steiner (not Group Steiner) problem. The approximation factor is not far from optimal: we prove a $c\log^{2-\epsilon}n$ lower bound, assuming $NP\not\subseteq ZTIME(n^{polylog(n)})$, for the grid graphs commonly used in practice. We also extend the algorithm to polygonal maps by discretizing the problem using novel geometric techniques.

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.

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

D* is a greedy heuristic planning method that is widely used in robotics, including several Nomad class robots and the Mars rover prototype, to reach a destination in unknown terrain. We obtain nearly sharp lower and upper bounds of $\Omega(n\log n/\log\log n)$ and O(n log n), respectively, on the worst-case total distance traveled by the robot, for the grid graphs on n vertices typically used in robotics applications. For arbitrary graphs we prove an O(n log 2 n ) upper bound.

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.

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.

We consider a very general online scheduling problem with an objective to minimize the maximum level of resource allocated. We find a simple characterization of an optimal deterministic online algorithm. We develop further results for the two, more specific problems of single resource scheduling and hierarchical line balancing. We determine how to compute optimal online algorithms for both problems using linear programming and integer programming, respectively. We show that randomized algorithms can outperform deterministic algorithms, but only if the amount of work done is a nonconcave function of resource allocation.

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.

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.

Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. This paper develops several results, some worst-case and some probabilistic, on the performance of 2- and k-opt local search for the traveling salesman problem, with respect to both the quality of the solution and the speed with which it is obtained.

In this paper, we investigate the problem of electrical testing of multichip modules (MCM's) substrate interconnections prior to chip assembly. Recently, single-probe test techniques for MCM substrate interconnections have been proposed that provide fault coverage comparable to double-probe test techniques. This work has two objectives. First, we assess the advantage of single-probe test techniques over double-probe techniques where overall test time is concerned. Second, we develop efficient heuristics to optimize the total distance traveled by a single test probe on an MCM substrate and thereby reduce the substrate testing time. We provide tight bounds on both single- and double-probe testing times. For substrates with two to three terminal pads in each of n nets, the expected travel time for a single probe is shorter by a factor of order n/sup 1/4 /. Experiments on benchmark MCM netlists with real probe traversal speeds confirm that single-probe testing has an increasing advantage over double-probe testing, as the number of nets increases. For an MCM substrate of 800 nets, the projected test time is faster by a factor of 2.5. A practical algorithm for finding efficient traversal routes is presented. It is based on heuristic procedures of tour construction and local improvement for solving a variation of the traveling salesman problem. Experiments show that up to 40% reduction in probe traversal time can be obtained with our algorithm.

We present new explicit lower bounds for some Ramsey numbers. All the graphs are cyclic and are on a prime number of vertices. We give theoretical motivation for searching for Ramsey graphs of prime order and provide additional computational evidence that primes tend to be better than composites.

An algorithm for finding the optimal traversal route of a single probe to test MCM interconnects is presented. The goal of this work is to optimize the total distance traveled by a single test probe on an MCM substrate and thereby reduce the substrate testing time. It is assumed that only one terminal pad of each interconnection net is to be probed. Our algorithm is based on tour construction and improvement with arbitrary insertion for solving a complex variation of the traveling salesman problem. Improved insertion and shuffling techniques guarantee the step by step optimization of the total traversal cost. The validity of the algorithm has been confirmed with experiments and shows that up to 50% reduction in probe traversal time can be obtained with our technique.

The popular class of series-parallel graphs can be built recursively from single edges by combining smaller components via connections only at a fixed pair of vertices called terminals. This recursive construction property with a limited number of terminals is essential to the linear time solution of problems on these graphs. A second useful property of these graphs is that decomposition is deterministic with respect to the series-parallel rules. This implies that the parse-tree of decomposition (which is required by the algorithms) can be determined in a straightforward manner by repeatedly applying the decomposition rules. Subject to retaining these properties, we examine how far the series-parallel graphs can be generalized. Corollaries of our results yield the deterministic decomposition of the series-parallel and Halin graph classes.

Graham’s multiprocessor precedence-constrained scheduling anomaly is shrunk where no list schedule is optimal for both $m = 2$ and 3 processors, and a simpler anomaly for $m > 2$ is constructed. As a corollary a very easy proof is obtained that shows that the general problem is NP-complete under tighter restrictions than previously known (schedule length 3, no precedence chains of length more than 2).