This paper considers the navigation of a three degrees-of-freedom mobile robot equipped with position and tactile sensors in an unknown planar environment. The paper focuses on the contact preserving segments of the robot's path. Any contact preserving path can trace a single or two simultaneous contacts. The paper establishes that motions involving two contacts induce two types of configuration-space curves: contractible loops representing passable gaps, and non- contractible loops representing impassable gaps. The paper identifies a generic class of contact preserving paths which requires only single-contact tracings with efficient transitions at double-contact configurations involving impassable gaps, and at triple-contact configurations involving both passable and impassable gaps. A preliminary tactile-sensor navigation algorithm based on these paths is illustrated with an example.

This paper is concerned with online navigation of a size D mobile robot in an unknown planar environment. A formal means for assessing algorithms for online tasks is competitiveness. For the navigation task, competitiveness measures the algorithm's path length relative to the optimal offline path length. While competitiveness usually means constant relative performance, it is measured in this paper in terms of a quadratic relationship between online performance and optimal offline solution. An online navigation algorithm for a size D robot called CBUG is described. The competitiveness of CBUG is analyzed and shown to be quadratic in the length of the shortest offline path. Moreover, it is shown that, in general, quadratic competitiveness is the best achievable performance over all online navigation algorithms. Thus, up to constants, CBUG achieves optimal competitiveness. The algorithm is improved with some practical speedups, and the usefulness of its competitiveness in terms of path stability is illustrated in office-like environments.

We explore an on-line problem where a group of robots has to reach a target whose position is known in an unknown planar environment whose geometry is acquired by the robots during task execution. The critical parameter in such a problem is the physical motion time, which, under the assumption of uniform velocity of all the robots, corresponds to length or cost of the path traveled by the robot which reached the target. The Competitiveness of an on-line algorithm measures its performance relative to the optimal off-line solution to the problem. While competitiveness usually means constant relative performance, this paper uses generalized competitiveness, i.e. any functional relationship between online performance and optimal off-line solution. Given an online task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all online algorithms for the task, such that the two bounds satisfy the same functional relationship. We prove that in general any on-line navigation algorithm must have at least a quadratic competitive performance. This paper describes a new on-line navigation algorithm, called MRBUG (short for Multi-Robot BUG), which requires constant memory and has a quadratic competitive performance. Thus, the above mentioned problem is classified into a quadratic competitive class. Moreover, since MRBUG achieves the quadratic lower bound, it has optimal competitiveness. The algorithm performance is illustrated in office-like environments

We explore an online problem where a group of robots has to find a target whose position is unknown in an unknown planar environment whose geometry is acquired by the robots during task execution. The critical parameter in such a problem is the physical motion time, which, under the assumption of uniform velocity of all the robots, corresponds to length or cost of the path traveled by the robot which finds the target. The competitiveness of an online algorithm measures its performance relative to the optimal offline solution to the problem. While competitiveness usually means constant relative performance, this paper uses generalized competitiveness, i.e. any functional relationship between online performance and optimal offline solution. Given an online task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all online algorithms for the task, such that the two bounds satisfy the same functional relationship. We classify a common online motion planning problem into competitive class. In particular, it is shown that group of robots navigation to a target whose position is recognized only upon arrival belongs to a quadratic competitive class. This paper describes a new online navigation algorithm, called MRSAM (short for multi-robot search area multiplication), which requires linear memory and has a quadratic competitive performance. Moreover, it is shown that in general any online navigation algorithm must have at least a quadratic competitive performance. The MRSAM algorithm achieves the quadratic lower bound and thus has optimal competitiveness. The algorithm's performance is illustrated in an office-like environments

This paper is concerned with on-line navigation of a size D mobile robot in an unknown planar environment. The competitiveness of an on-line navigation algorithm measures its path length relative to the length of the optimal off-line path. While competitiveness usually means constant relative performance, it is generalized here to any functional relationship between on-line performance and optimal off-line solution. This paper describes a new on-line navigation algorithm, called CBUG, which requires constant memory and has a quadratic competitive performance. Moreover, it is shown that in general any online navigation algorithm must have at least a quadratic competitive performance. The CBUG algorithm achieves the quadratic lower bound and thus has optimal competitiveness.

We describe an on-line sensor based algorithm for covering planar areas by a square-shaped tool attached to a mobile robot. Let D be the tool size. The algorithm, called Spiral-STC, incrementally subdivides the planar work-area into disjoint D-size cells, while following a spanning tree of the resulting grid. The algorithm covers general grid environments using a path whose length is at most (n + m)D, where n is the number of D-size cells and m /spl les/ n is the number of boundary cells, defined as cells that share at least one point with the grid boundary. We also report that any on-line coverage algorithm generates a covering path whose length is at least (2 - /spl epsiv/)l/sub opt/ in the worst case, where l/sub opt/ is the length of the optimal covering path. Since (n + m)D /spl les/ 2l/sub opt/, Spiral-STC is worst-case optimal. Moreover, m << n in practical environments, and the algorithm generates close-to-optimal covering paths in such environments. Simulation results demonstrate the spiral-like covering patterns typical to the algorithm.

The paper considers the problem of covering a continuous planar area by a square-shaped tool attached to a mobile robot. Using a tool-based approximation of the work-area, we present an algorithm that covers every point of the approximate area. The algorithm, called spanning tree covering (STC), subdivides the work-area into disjoint cells corresponding to the square-shaped tool, then follows a spanning tree of the graph induced by the cells, while covering every point precisely once. We present and analyze three versions of the STC algorithm. The first version is an off-line algorithm that computes an optimal covering path in linear time O(N), where N is the number of cells comprising the approximate area. The second version is an online or sensor based algorithm, that completes an optimal covering path in time O(N), but requires O(N) memory for its implementation. The third version of STC is "ant"-like, where the robot may leave pheromone-like markers during the coverage process. The ant-like STC algorithm runs in time O(N) and requires only O(1) memory. We present simulation results of the three STC algorithms, demonstrating their effectiveness in cases where the tool size is significantly smaller than the work-area characteristic dimension.