Determining the existence of a collision-free path between two points is one of the most fundamental questions in robotics. However, in situations where crossing an obstacle is costly but not impossible, it may be more appropriate to ask for the path that crosses the fewest obstacles. This may arise in both autonomous outdoor navigation (where the obstacles are rough but not completely impassable terrain) or indoor navigation (where the obstacles are doors that can be opened if necessary). This problem, the minimum constraint removal problem, is at least as hard as the underlying path existence problem. In this paper, we demonstrate that the minimum constraint removal problem is NP-hard for navigation in the plane even when the obstacles are all convex polygons, a case where the path existence problem is very easy.

What kind of tasks are robots with extremely simple control laws capable of performing? Consider a point robot that navigates by aligning itself to a certain fixed angle relative to the environment boundary, then driving in a straight line. Even without knowing the robot's exact location, basic, noisy odometry and counting sensors can be used to narrow down the robot's possible locations over time. This paper describes methods of determining the possible locations of the robot after the robot has moved a sufficient distance or has impacted the boundary a sufficient number of times.

This paper examines the problem of determining the distribution of a number of indistinguishable moving bodies located in regions separated by sensor beams that can detect whether a body moves across them. We characterize the conditions under which an exact distribution of bodies can be determined, and compute bounds on the expected number of sensor observations required to determine this exact distribution for a certain movement model of the bodies.

A robot navigates in a polygonal region populated by a set of partially distinguishable landmarks. The robot's motion primitives consist of actions of the form “drive toward a landmark of class x”. To effectively navigate, the robot must always be able to see a landmark. Also, if the robot sees two landmarks of the same class, its motion primitives become ambiguous. Finally, if the robot wishes to navigate from landmark s0to landmark sgoalwith a simple graph search algorithm, then there must be a sequence of landmarks [s0, s1, s2, ..., sk= sgoal], in which landmark siis visible from si-1. Given these three conditions, how many landmark classes are required for navigation in a given polygon P? We call this minimum number of landmark classes the connected landmark class number, denotedχCL(P). We study this problem for the monotone polygons, an important family of polygons that are frequently generated as intermediate steps in other decomposition algorithms. We demonstrate that for all odd k, there exists a monotone polygon Mkwith 3 over 4 (k2+ 2k + 1) vertices such thatχCL(P) ≥ k. We also demonstrate that for any n-vertex monotone polygon P,χCL(P) ≤ n/3 + 12.

Suppose that two members of a finite point guard set S within a polygon P must be given different colors if their visible regions overlap, and that every point in P is visible from some point in S. The chromatic art gallery problem, introduced in [7], asks for the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of P. We study two related problems. First, given a polygon P and a guard set S of P, can the members of S be efficiently and optimally colored so that no two members of S that have overlapping visibility regions have the same color? Second, given a polygon P and a set of candidate guard locations N, is it possible to efficiently and optimally choose the guard set S ⊆ N that requires the minimum number of colors? We provide an algorithm that solves the first question in polynomial time, and demonstrate the NP-hardness of the second question. Both questions are motivated by common robot tasks such as mapping and surveillance.

A novel criterion is introduced for assessing the diversity of a collection of paths or trajectories. The main idea is the notion of survivability, which measures the likelihood that numerous paths are obstructed by the same obstacle. This helps to improve robustness with respect to collision, which is an important challenge in the design of real-time planning algorithms. Efficient algorithms are presented for computing the survivability criterion and for selecting a subset of paths that optimize survivability from a larger collection. The algorithms are implemented and solutions are illustrated for two different systems. Chi-square tests are used to show uniform coverage obtained by using the computed paths in a simple breadth-first search. Random obstacle placement is used to show superior robustness of these primitives compared to uniform sampling of the control space.

Researchers have addressed the localization problem for mobile robots using many different kinds of sensors, including rangefinders, cameras, and odometers. In this paper, we consider localization using a robot that is virtually "blind", having only a clock and contact sensor at its disposal. This represents a drastic reduction in sensing requirements, even in light of existing work that considers localization with limited sensing. We present probabilistic techniques that represent and update the robot's position uncertainty and algorithms to reduce this uncertainty. We demonstrate the experimental effectiveness of these methods using a Roomba autonomous vacuum cleaner robot in laboratory environments.