This paper investigates a range of strategies for determining when to explicitly replan paths. An computationally inexpensive event-driven method is presented which allows the robot to execute an a priori path reactively until a significant deviation in the path occurs, at which point the robot explicitly replans. The event-driven strategy is compared to replanning after every move, and replanning after every n moves on a mobile robot for a wide variety of influences, including different unmodeled obstacle configurations and densities, and quality of the a priori map. The paper concludes that, in general, planning as frequently as resources permits results in smoother actual paths and faster completions. However, if the updated map is inaccurate, the event-driven method is superior.

This paper presents a new approach to reactive control utilizing the output of an explicit path planner which considers terrain preferences. To demonstrate the concept, a wavefront propagation, type of planner algorithm, Trulla, is integrated into a reactive framework and used as part of the overall architecture. Terrain preferences are represented as weights or costs which are considered in generating a near optimal path. The algorithm is demonstrated on the CSM Denning-Branch MRV4 mobile robot for three scenarios: navigation out of a box canyon, planning with terrain preferences, and opportunistic path improvement.

This paper addresses the problem of determining the reliability of individual sensors in a multi-sensor robotic system in an unknown environment. The inherent difficulty in this problem is that the decision must be based solely upon the data from the sensors themselves. While some previous research has considered unstructured environments (see Refs. 1 and 2 for examples) little if any consideration has been given to totally unknown environments. This problem has usually been avoided by assuming that the sensors would not provide erroneous data or ignoring sensors when they appeared to provide erroneous data. We believe a more robust solution is to consider each sensor’s performance over time compared to other sensors, and from this determine a measure of confidence in each sensor. This allows sensors which temporarily provide erroneous data to be accommodated. A system which can determine the reliability of its sensors is more robust since it can wisely decide which sensors are most appropriate for a given task and can also determine whether sensor conflicts are the result of poorly performing sensors.

This paper discusses an approach to mo- bile robot path planning which utilizes a wavefront- like propagation method for determining near-optimal paths. This approach is different from previous wave propagation methods in three aspects: it attempts to find near-optimal paths from all locations in the free space to the destination instead of one optimal path from the source location to the destination, may per- form repeated propagations to converge to a solution, and is composed of simplified computations based on local information to facilitate a VLSI implementation. I. INTRODUCTION Wavefront propagation methods for robot path plan- ning have been proposed by other researchers. The tradi- tional approach is to start with a list containing only the destination point (or a region representing a small area around the destination point) and propagate a value rep- resenting the cost of traveling between the two regions to each unvisited neighbor of the region. The region is removed from the list and all its newly visited neighbors are added to the list. The list is sorted by increasing cost and the process is repeated with the lowest cost region in the list. This process terminates when the source region is reached. The actual path is then constructed between the endpoints using the computed cost values. Jahanbin and Fallside(l) have presented some wavefront propagation path planning algorithms consisting only of free-space and obstacles in configuration space. They pre- sented two solutions to the planning problem, one for uniform region sizes and another for non-uniform region sizes. The propagation was performed by the use of a mask which was placed over successive positions on the wavefront. Various shape wavefronts could be propagated depending on the weights in the mask. Once the propa- gation was completed the path was constructed from the source to the lowest cost neighbor and this process was repeated until the destination was reached. There are two

The problem of finding a path for a mobile robot in two dimensions among stationary obstacles using a free-space graph representation of the robot's workspace is examined. One problem with solutions of this type has been the time it takes to construct a graph from the image of the workspace. Two solutions are presented which seek to resolve this situation by constructing the graph representation 'on the fly' in a scanline fashion by processing the image one line at a time from top to bottom. Each method consists of three processes: one which breaks the obstacles in the image into pseudo-obstacles, another which analyzes the pseudo-obstacles and locates regions in the free space which represent nodes in the graph, and a third which completes the graph by locating similarities of the free space regions and uses them as edges. The modularity lends itself toward pipelined processing to reach the solution. Discussions are presented and results given of the graph construction process and the paths found on sample images as well as comparative times.>