Obstacle detection is a critical task in mobile robot navigation. To allow for rapid reactions to changes in the environment, it is required to complete its operation in short time intervals. That can be difficult if computing and/or sensing robot resources are limited. Therefore, it is important to design precisely what sensorial information would be needed to guarantee detection, and how it would be gathered to guarantee throughput. In this paper we present analysis and experiments related to the design of an obstacle detection system for a mobile robot with limited sensing capabilities. Objectives are to preserve safety while maintaining good motion performance. The design is made in two steps. Firstly, to find what is the minimum information needed to assure safety as a function of the sensors at hand, the robot capabilities and the intended motion control policy. Second, to manage the available sensors in order to provide the required information when needed. For the example studied, a justified solution has been defined which guarantees detection, robot safety, and good motion performance in real time. The solution has been tested with experiments that illustrate the effectivity achieved.

As part of a Defense Advanced Research Projects Agency/National Science Foundation study on human-robot interaction (HRI), over sixty representatives from academia, government, and industry participated in an interdisciplinary workshop, which allowed roboticists to interact with psychologists, sociologists, cognitive scientists, communication experts and human-computer interaction specialists to discuss common interests in the field of HRI, and to establish a dialogue across the disciplines for future collaborations. We include initial work that was done in preparation for the workshop, links to keynote and other presentations, and a summary of the findings, outcomes, and recommendations that were generated by the participants. Findings of the study include-the need for more extensive interdisciplinary interaction, identification of basic taxonomies and research issues, social informatics, establishment of a small number of common application domains, and field experience for members of the HRI community. An overall conclusion of the workshop was expressed as the following-HRI is a cross-disciplinary area, which poses barriers to meaningful research, synthesis, and technology transfer. The vocabularies, experiences, methodologies, and metrics of the communities are sufficiently different that cross-disciplinary research is unlikely to happen without sustained funding and an infrastructure to establish a new HRI community.

In experimental robotics it is common to complement the motion planning algorithm with a local obstacle avoidance module. We are concerned here with the specifications of a range sensor specifically design for the task. Such sensor has special requirements: it has to guarantee detection and response, and it has to guarantee throughput, providing information ail a rate in proportion to robot velocity. An analysis is presented which allows the selection of the sensor requirements for collision avoidance tasks in mobile robots. The design takes into account robot dynamics, it is compatible with fast motion-only the indispensable environment zones are explored-and avoids unnecessary velocity reductions. Experiments show the possibilities and limitations of the approach.

The paper is concerned with the development of methods that can be used to augment human performance in three degree of freedom (DOF) motion planning tasks. Previous experimental studies have shown that human performance in such motion planning tasks is inadequate, especially when complex objects and/or environments are involved. Our approach is based on the use of configuration space (C-Space) to simplify the motion planning task from that of moving a complex object in work space (W-space) to moving a point in a C-space maze. Tools are developed which allow the user to easily grasp all the information contained in 3D C-space and use it to solve the task at hand.

This paper describes a novel approach to the study of human performance in motion planning for complex objects. The proposed approach is based on an anonymous operation over the Internet. A system useful in conducting these types of studies is developed and applied in a study of human performance in the use of the configuration space (C-space) method of teleoperation. Results of this study are presented with the conclusion that the C-space method of teleoperation is suitable for most subjects and significant improvements in performance can be expected when utilizing the C-space over traditional work space control.

Discusses an approach to combining human and machine intelligence in teleoperation of 6 degree of freedom (DOF) arm manipulators. Two algorithms are presented that can operate in near real time and can deal with an unknown environment. We capitalize on the fact that the operator needs help primarily in the areas where the arm is near the obstacles; this lowers the computational costs. The main, major linkage algorithm operates on the principle of a greedy search. Perception of the hints provided by the operator is used in a few basic rules that limit the directions of the search. Overall, the intention is to allow the operator to concentrate on "global" motion planning tasks and leave collision detection and local path finding to the machine intelligence. An experimental study in progress is presented that is expected to demonstrate the algorithms' performance and to suggest the types of situations where it will be the most effective.

This work addresses the problem of finding the shortest path for a vehicle (say, a mobile robot or a car) moving in a limited workspace. The proposed approach makes use of a tool dubbed the reflective unfolding operator which has a clear geometric interpretation and provides an interesting means for solving other trajectory design problems. The authors' previously reported result (1997) which relates to the special case of a car maneuvering within a disc-shaped area, is extended here to the general case of an arbitrarily shaped area. The approach is illustrated by computer simulations.

This work deals with a specific walking pattern in biped robot locomotion $an ability to turn. This ability, which is an essential part of a free walk on a 2D surface, is indispensable for a walk among obstacles. Only the turning operation property is considered. Using local information about its surroundings obtained from the robot sensors, and depending-on the shape and location of an obstacle on its way, the turning strategy is applied to negotiate the obstacle and resume stable motion. One difficulty is in maintaining robot stability during turning. The control strategy is based on the zero moment point. Motion stability is ensured by adjusting the swing leg center of mass and hip position trajectories in a trial and error fashion. The procedure is fast enough for real-time implementation. Simulation experiments demonstrate the stability of motion when negotiating various obstacles.

This paper considers an approach to operator-guided real time motion control of robot arm manipulators that's based on the use of configuration space (C-space). The goal is to improve operator performance in a complex environment with obstacles, In such tasks, traditional teleoperation techniques, which are all based on control in work space (W-space), suffer from human errors tied to deficiencies in human spatial reasoning. The C-space approach transforms the problem into one humans are much better equipped to handle-moving a point in a maze-and results in a significant improvement in performance: shorter path, less time to complete the task, and virtually no arm-obstacle collisions. Versions of the approach are described for two-dimensional (2-D) and three-dimensional (3-D) tasks, and tools are developed to efficiently interface the human and machine intelligence. Effectiveness of the C-space approach is demonstrated by a series of experiments, showing an improvement in performance on the order of magnitude in the 2-D case and a factor of two to four in the 3-D case, compared to usual work space control.

Extends results in sensor-based motion planning with dynamics for a point robot to a more realistic case of a dimensioned robot. We consider a disc-shaped mobile robot with a differential drive system operating in a planar environment with unknown arbitrarily shaped stationary obstacles. Given the constraints on the robot kinematics, dynamics, sensing, and control means, an algorithm is developed that generates collision-free trajectories with guaranteed convergence. To make the extension to a vehicle with finite dimensions possible, a suitable methodology for the choice of actuator controls is proposed. Under the proposed strategy, whenever a turn in the motion is required, the robot attempts to accomplish it in minimum time, while simultaneously moving in space. Even with a reasonably fast motion, its safety is guaranteed by maintaining at all times an emergency stopping path. Simulated examples demonstrate the algorithm's performance.

Discusses the use of configuration space (C-space) as a means of visualization and control in teleoperation of robot arm manipulators. The motivation is to improve operator performance in tasks involving manipulator motion in a complex three-dimensional (3D) environment with obstacles. Unlike other motion planning tasks, operators are known to make expensive mistakes in arm control, due to deficiencies of human spatial reasoning. The advantage of C-space is that in it the arm becomes a point, a case which humans are much better equipped to handle. To make such operation possible, a tool is proposed that reduces motion in 3D C-space to that in 2D C-space. It is then shown on results from testing 18 human subjects that translating the problem of a three-link 3D arm manipulator motion into C-space improves the operator performance remarkably, by a factor of 2 to 4, compared to usual work space control.

The objective of this work is to develop a fault tolerant system for a sensitive skin-based motion planning system. The purpose of the skin is to provide real-time collision avoidance for a machine (e.g. a mobile robot or an arm manipulator) operating in an uncertain environment with obstacles. The skin is designed to cover virtually any kind of machine; in the version used in this project the skin covers an industrial arm manipulator and contains about 1000 infrared sensors. In order to operate such a complex system in real time, effective fault tolerance is necessary. The latter is achieved in our system via component redundancy: the distance measurements necessary for motion planning are done using a particular scheme for sensor grouping. The system achieves safe motion planning even if some of the sensors are dead or partially inoperative. Based on the fault tolerance model used a fault tolerance algorithm is developed, tested and demonstrated experimentally.

Focuses on sensor-based motion planning of a biped robot operating in an environment with obstacles. Using its sensors, the robot is able to obtain local information about its surroundings. A number of stable walking patterns are investigated. Depending on the shape and location of an obstacle on the robot's way, the decision making algorithm chooses the best relevant walking pattern; the robot then negotiates the obstacle and resumes stable motion. The proposed control strategy is based on the zero moment point. The stability of each walking pattern is ensured by adjusting the swing leg center of mass and hip position trajectories in a trial and error fashion, fast enough for real-time implementation. Simulation experiments demonstrate stability of motion when negotiating various obstacles.

As sensor arrays become ever larger in complex automation systems, provisions for sensor fault detection and tolerance become mandatory. This work addresses the question of real-time fault tolerance in large two-dimensional sensor arrays, with the number of sensors on the order of thousands or more. As an example, we consider a flexible sensitive skin system with uniformly distributed infrared sensors. The purpose of the skin is to cover the whole body of a mobile robot or a robot arm manipulator, and serve as a front end of a motion planning and collision avoidance system. The goal of the proposed approach to fault tolerance is to maintain machine's functionality in situations with damaged sensors; without it, erroneous motion or collisions with surrounding objects would occur. The approach makes use of analytic redundancy whereby periodical comparison is made of sensor measurements with dynamically adjusted expected values of sensor readings. Two fault tolerance schemes, online and off-line, are considered. The properties of both schemes are analyzed and results of experiments demonstrating their performance are discussed.

The problem of motion planning in three dimensions for n tethered robots is considered. Motivation for this problem comes from the need to coordinate the motion of a group of tethered underwater vehicles. The motion plan must be such that it can be executed without the robots' tethers becoming tangled. The simultaneous-motion plan is generated in three steps. First, an ordering of the robots is produced that maximizes the number of robots that can move along straight lines to their targets. Then paths for the robots are computed assuming they move sequentially in the given order. Two methods of computing the sequential-motion plan for the robots are presented. The first method is computationally simple but guarantees no bound on the path length with respect to the optimal length; the second method guarantees nearly optimal paths for the given ordering at the expense of additional computation. Finally, trajectories are determined that allow the robots to move simultaneously. The motion plan generated is guaranteed not to result in tangled tethers. The algorithms we present are shown to run in O(n/sup 4/) time in total in the worst case, which is less than the additional computation needed to produce the nearly optimal paths using existing approximation algorithms.

The effect of robot dynamics on autonomous navigation is a key issue in sensor-based motion planning. In most of existing works, the solution is attempted by separating the planning and control into two sequential stages; as a minus, this may, for example, adversely effect the algorithm convergence. The strategy proposed in this paper solves the problem by combining motion planning and control within a single-stage procedure. The procedure exhibits good dynamic behavior, while providing safety (collision avoidance) and fast response. Results of testing the approach on a commercial Nomad-200 mobile robot are presented. Also discussed is the effect of model parameters on motion performance.

One way to avoid obstacles without modeling the environment is to use a sensor-based sensitive skin covering the body of the robot along with proper sensor-based motion planning algorithms. Compared to prior attempts, the system developed at the UW-Madison Robotics Lab and discussed here presents a system that can be easily reconfigured for a variety of applications. This is accomplished via modularized sensitive skin patches that can be connected in various ways, and a hierarchical control architecture that can be easily modified for various system configurations. In the implemented version, the skin contains about 1000 infrared sensors; it can be easily expanded, with minor changes. The system has been successfully tested in preliminary trials.

Discusses the feasibility of using configuration space (C-space) as a means of visualization and control in operator-guided real-time motion of a robot arm manipulator. The motivation is to improve performance of the human operator in tasks involving the manipulator motion in an environment with obstacles. Unlike some other motion planning tasks, operators are known to make expensive mistakes in such tasks, even in a simpler two-dimensional case. Using an example of a two-dimensional arm manipulator, we show that translating the problem into C-space improves the operator performance remarkably, on the order of magnitude compared to the usual work space control.

In this paper we pose the following two questions: Given two points, start and target, within a relatively small closed planar area W/spl sub/R/sup 2/, each with a prescribed direction of motion (orientation) in it, and assuming a possibility of reversals of motion: (i) What is the shortest path of bounded curvature that connects the points and lies completely in W? (ii) What is the minimum number of motion reversals (path cusps) one needs to arrive at the target point with the prescribed orientation? Such questions appear in various applications with nonholonomic motion constraints, as for example in motion planning for driverless cars. The proposed approach solves both problems. It makes use of a tool dubbed the reflective unfolding operator which has a clear geometric interpretation and provides an interesting means for solving other trajectory design problems.

We pose the following questions: Given two points within a closed area W/spl sub/R/sup 2/, each with a prescribed direction of motion in it, (i) what is the shortest path of bounded curvature that joins them and lies completely in W? (ii) what is the minimum number of cusps one needs to design a path in W? These kind of questions appear in various applications, such as robot motion planning. The proposed approach makes use of a tool dubbed the reflective unfolding operator which has a clear geometric interpretation and provides an interesting means for solving other trajectory design problems. In this text, the approach is applied to the following problem: for a car moving with bounded curvature and possible reversals, given the starting and target directions of motion at the center of a disc D of some radius R, design the shortest possible path fully lying in D. The path produced by the algorithm turns out to also be of the lowest complexity (the minimum number of cusps).

The problem of motion planning in three dimensions for n tethered robots is considered. Motivation for this problem comes from the need to coordinate the motion of a group of tethered underwater vehicles. The motion plan must be such that it can be executed without the robots' tethers becoming tangled. The simultaneous-motion plan is generated in three steps. First an ordering of the robots is produced that maximizes the number of robots that can move along straight lines to their targets. Then paths for the robots are computed assuming they move sequentially in the given order. Two methods of computing the sequential-motion plan for the robots are presented. The first method is computationally simple but guarantees no bound on the path length with respect to the optimal length; the second method guarantees nearly optimal paths for the given ordering. Finally, trajectories are determined that allow the robots to move simultaneously. The motion plan generated is guaranteed not to result in tangled tethers. The algorithms for these three steps can be shown to ran in time O(n/sup 4/) in total in the worst case.

Most of today's approaches to sensor-based motion planning focus on kinematic and geometric issues and ignore the system dynamics. Those few that address dynamics do so in a two-stage fashion by considering one issue at the time. This work attempts to incorporate control of body dynamics into the sensor-based motion planning process. A point mobile robot is assumed to operate in a planar environment with unknown arbitrary stationary obstacles. Based on its current velocity and sensory data about the surrounding obstacles, the robot plans its motion to locally maximize the turning angle toward the current intermediate target. An optimal braking procedure takes care of sudden potential collisions by guaranteeing a safe emergency stopping path. Given the constraints on robot's dynamics, sensing, and control means, conditions are formulated for generating trajectories that guarantee convergence and the robot's safety at all times. The approach calls for continuous computation and is fast enough for real-time implementation. Simulated examples demonstrate its performance.

Given two points in the plane, each with the prescribed direction of motion, the question being asked is to find the shortest smooth path of bounded curvature that joins them. The classical result by Dubins (1957) that is commonly used gives a sufficient set of paths which is guaranteed to contain the shortest path; the latter is then found by explicitly calculating every path in the set. In this paper we show that in the case when the distance between the two points is above some minimum, the solution sought can be found via a simple classification scheme. Besides computational savings (essential, for example, in real-time motion planning), this result sheds light on the nature of factors affecting the length of paths in the Dubins's problem.

The existing approaches to sensor-based motion planning tend to deal solely with kinematic and geometric issues, and ignore the system dynamics. This work attempts to incorporate body dynamics into the paradigm of sensor-based motion planning. The authors consider the case of a mass point robot operating in a planar environment with unknown arbitrary stationary obstacles. Given the constraints on the robot's dynamics, sensing, and control means, conditions are formulated for generating trajectories which guarantee convergence and the robot's safety at all times. The approach calls for continuous computation and is fast enough for real time implementation. The robot plans its motion based on its velocity, control means, and sensing information about the surrounding obstacles, and such that in case of a sudden potential collision it can always resort to a safe emergency stopping path. Simulated examples demonstrate the algorithm's performance.

We considered the problem of motion planning for a number of small, disc-like robots in a common planar workspace. Each robot is tethered to a point on the boundary of the workspace by a flexible cable of finite length. These cables may be pushed and bent by robots that come in contact with them but remain taut at all times. The robots are given a set of target points to which they must move. Upon arrival at these points, a new set of target points are given. Associated with each set of target points is a configuration of the cables that must be achieved when all robots are at these target points. The motion planning task addressed here is to produce relatively short paths for the robots from an initial (nontrivial) configuration of the cables to a configuration corresponding to the next set of target points. An O(n/sup 2/logn) algorithm is presented for achieving this task for n robots.

The existing approaches to sensor-based motion planning tend to deal solely with kinematic and geometric issues, and ignore the system dynamics. This work attempts to incorporate body dynamics into the paradigm of sensor-based motion planning. The authors consider the case of a point mass mobile robot operating in a planar environment with unknown stationary obstacles of arbitrary shape. Given the constraints on the robot's dynamics, sensing, and control means, conditions are formulated for generating collision-free trajectories with guaranteed convergence. The approach calls for continuous computation and is fast enough for real time implementation. Based on its velocity and sensing data, the robot continuously plans its motion based on the canonical solution which presents the time-optimal path within the robot's current sensing range. For a special case of a sudden potential collision an option of a safe emergency stopping path is always maintained. Simulated examples demonstrate the algorithm's performance.

An algorithm for motion planning for multiple mobile tethered robots in a common planar environment is presented. The tethers of the robots are flexible cables that can be pushed and bent by other robots during their motion. Given the start and target positions of all robots and their cables, the objective is to design a sequential motion strategy for the robots that will not entangle the robot tethers. An algorithm is described that achieves this objective while generating an ordering of the robots that produces reasonably short paths. The algorithm's complexity is O(n/sup 4/), where n is the number of robots.>

An approach is presented for exploring an unknown, arbitrary surface in three-dimensional (3D) space by a mobile robot. The main contributions are (1) an analysis of the capabilities a robot must possess and the trade-offs involved in the design of an exploration strategy, and (2) two provably-correct exploration strategies that exploit these trade-offs and use visual sensors (e.g., cameras and range sensors) to plan the robot's motion. No such analysis existed previously for the case of a robot moving freely in 3D space. The approach exploits the notion of the occlusion boundary, i.e., the points separating the visible from the occluded parts of an object. The occlusion boundary is a collection of curves that "slide" over the surface when the robot's position is continuously controlled, inducing the visibility of surface points over which they slide. The paths generated by our strategies force the occlusion boundary to slide over the entire surface. The strategies provide a basis for integrating motion planning and visual sensing under a common computational framework.>

The performance of systems for sensor-based robot motion planning is known to depend heavily on the basic search algorithms used. Typically, these are provable graph search schemes modified into maze search algorithms by taking into account the topology of the physical objects in the workspace-for example, the fact that the boundary of a 2-dimensional object is a simple closed curve. Although several maze search algorithms are already available, more are needed to improve the performance and fill gaps in required properties. This work presents a new algorithm that possesses properties not covered so far, and then assesses its performance. The algorithm allows one to use directional input information (such as azimuth angles) rather than the usual Cartesian coordinates; it also allows the robot to "cut corners" on its way to the target, thus shortening the path.>

Considers the problem of planning the grasp operation for a multi-finger hand. The hand is expected to be able to handle three-dimensional objects of arbitrary unknown shapes as long as they are of "reasonable" size so as to make the grasping operation meaningful. The object geometry is not known beforehand. To provide input information for the interaction necessary, a whole-sensitive hand is assumed-every point of its surfaces possesses tactile sensing. The important property of the problem formulation is that in the grasp produced the hand and the fingers are expected to "hug" the object in a manner a human hand holds an apple-with the maximum contact with its surface for a firm, comfortable grasp. A novel, powerful strategy for real-time grasping is suggested which makes use of techniques for highly redundant sensor-based planar motion planning. An example is given that illustrates the performance of the approach.>

This paper presents an approach for decentralized motion planning for multiple mobile robots operating in a common 2D environment with unknown stationary obstacles. Each robot is capable of translatory motion and is equipped with range sensors which allow it to sense surrounding objects. Each robot knows its current position, is able to distinguish a robot from an obstacle, and can assess the instantaneous motion of any robot it can sense. Other than this, the robot has no knowledge about the scene, or of the paths or objectives of other robots; there is no mutual communication among the robots. No constraints are imposed on the paths or shapes of robots and obstacles. Each robot plans its path toward its target dynamically, based on its current position and sensory feedback. Given the assumptions of incomplete information and decentralized planning, the suggested heuristic algorithm demonstrates a remarkable robustness and ability for successful decentralized real-time motion planning in an unknown complex environment.>

This paper is concerned with motion planning for a mobile robot operating in a planar environment with multiple arbitrarily moving obstacles. The robot and obstacles are rigid bodies of arbitrary shapes. All rigid motion-rotation and translation-is considered for the obstacles; the robot can move only by translation. The robot has no advance information about the obstacles' shapes or motion, and obtains information about the surrounding environment from its sensors, in real time. Necessary and sufficient conditions are derived under which collision-free motion of the robot to its target position can be guaranteed. Namely, it is shown that if the maximum velocity of the robot is bounded below by a multiple of the maximum allowable velocity of the obstacles, then a provable motion planning algorithm can be devised. The constant multiple in this bound takes into account the nonconvexity of the obstacles and a bound on the (minimal) distance between any obstacle and the robot's target position.>

The problem of generating collision-free motion in an operator-assisted teleoperated robot arm manipulator system is discussed. The concentration is on several system requirements: a real real-time operation, a guarantee of collision-free motion for the entire body of the arm manipulator, and an ability to handle obstacles of arbitrary shapes. The suggested methodology draws on recent work on motion planning with incomplete information for whole-sensitive robots.>

A mobile robot has been constructed, and a motion planning methodology for operating in an environment with unknown arbitrary obstacles has been implemented and tested in a complex cluttered environment. The authors address the following implementation issues: the robot's ability to cope with limited information available from typical sensors while operating in a cluttered environment with unknown obstacles; handling the registration problem, to assess the robot's current location; performing necessary data processing and planning fast enough to assure acceptable motion speeds; handling situations which require the robot to make loops, retreat, and visit some areas of its path more than once. The results indicated feasibility of practical systems capable of operating in a complex uncertain environment.>

A strategy is described for on-line motion ]planning with incomplete information for a special type of highly redundant planar robot kinematics, called a snake. The snake consists of many simple serially connected links and has on-line sensing which provides information about its immediate surroundings. The task is to move the snake head point from its starting position to a known target position while generating collision-free motion for the rest of the snake body, in an environment filled with unknown obstacles of arbitrary shape. Computationally, the procedure is linear in the number of the snake Links; it is highly efficient and can be easily realized in real time. The procedure makes use of a unit motion far a single link based on the tractriz curve. This choice results in automatically achieving a “natural” motion distributed continulously and asymmetrically along the snake body - the joint displacements tend to ‘“die out” in the direction from the head to the tail. The generated path possessies an optimality property - the instantaneous total displacement of all the links/joints is minimum.

Recent research on sensor-based motion planning has produced theory and algorithms for motion planning for robots operating in an environment with unknown obstacles. The implementation of such systems requires constructing a robot, sensors, and a complex control computer environment - a time-consuming and costly undertaking. To provide a necessary bridge between theory and implementation - to test algorithmic solutions and to cut down on the number of experimental alternatives - a computer simulation system for modeling sensor-based motion planning has been developed. The system provides means for modeling various robots, sensor systems, and sets of obstacles in the robot environment, testing a variety of two- and threedimensional motion planning algorithms, and testing human performance in motion planning. It also provides a real-time animation of the robot motion. The simulation is realistic in that only information from the assumed sensor media is used as input to a motion planning algorithm. These features make it a unique system for simulating robot planning and control in an uncertain environment.

A generalization to the 3-D manipulator of a 2-D approach to sensor-based robot motion planning in an unknown environment with arbitrary obstacles is considered. For the approach to guarantee convergence, it is vital that the number of options that the arm has for passing around an obstacle be limited. A three-link arm has an infinite number of directions for passing around an obstacle, but, by making use of the natural constraints imposed by the arm kinematics, the 2-D approach is extended to a three-link 3-D arm manipulator with sliding joints (a Cartesian robot arm). The technique exploits certain properties, called anisotropy and monotonicity, of the arm configuration space. The resulting algorithm is the first nonheuristic algorithm for online motion planning in three dimensions, with no prior knowledge of the obstacles. Collision-free motion is guaranteed for every point of the robot body; in no case does the generated path amount to an exhaustive search of the work space.>

Recent results in sensor-based motion planning suggest that the collision avoidance task can be handled automatically, thus freeing the operator for global control. Whole-sensitive arm manipulators bodies are covered with a sensitive skin sensor to detect nearby objects are proposed for this purpose. The data from the sensitive skin is used with the sensor data processing and motion planning algorithms to avoid collisions for the entire robot arm body in an unknown or time-varying environment. The result is a highly efficient, safe, and robust hybrid system in which the shift motion control between the operator and the automatic system is done transparently and in real-time. The motion of the master arm is either executed faithfully, or, to avoid collisions, is used as general guidance for the slave arm.>

The objective of the hospital transport mobile robot, HelpMate, is to carry out such tasks as the delivery of off-schedule meal trays, lab and pharmacy supplies, and patient records. Unlike many existing delivery systems in the industry which operate within a rigid network of wires buried or attached to the floor, a hospital transport robot is expected to be able to navigate much like a human, including handling uncertainty and unexpected obstacles. The navigation system of HelpMate makes use of the specific structure of a hospital hallway environment and relies on recent results on provable sensor-based motion planning algorithms that specifically address the issue of navigation in an unknown and unstructured environment. also incorporated in the system are algorithms for handling unmodeled factors such as sensor noise and sensor inaccuracy, errors in position estimation, and moving obstacles.>

Studies the topology of the free configuration space (FCS) of any robot that consists of one or more connected rigid bodies and operates in an environment with obstacles. It is shown that if a certain unrestrictive robot-obstacle spatial relationship is satisfied, then FCS is uniformly locally connected (ULC). Conditions are derived under which the FCS boundary presents a manifold. Although the ULC property is not sufficient for the general case, it is shown that for the two-dimensional (2D) case the ULC property guarantees that FCS is bounded by simple curves. This result provides an effective tool for reducing the robot motion problem to the analysis of simple closed curves in the robot configuration space.>

A number of existing maze-searching and robot motion planning algorithms are studied from the standpoint of a single performance criterion. The main motivation is to build a framework for selecting basic planning algorithms for autonomous vehicles and robot arm manipulators that operate in an environment filled with unknown obstacles of arbitrary shapes. In choosing an appropriate criterion, it is noted that besides convergence, minimizing the length of generated paths is a single major consideration in planning algorithms. In addition, since no complete information is ever available, optimal solutions are ruled out. Accordingly, the performance criterion is defined in terms of the upper bound on the length of generated paths as a function of the maze perimeter. The comparison shows that the special structure of graphs that correspond to planar environments with obstacles actually makes it possible to exceed the efficiency of general maze-searching algorithms.>

Experimental attempts to build teleoperated master-slave robot arm manipulators revealed that a human operator has difficulty in interpreting input information (coming, e.g. directly via visual tract or from fixed or moving TV monitors at the scene), and consequently in teleoperation decision making. The problem becomes more pronounced when the slave arm has to operate in a complex environment where every point of the arm body is subject to potential collision. Results are presented of experimental tests with human operators that trace the source of the difficulty to the limitations in human abilities for space orientation and interpretation of geometrical data, and a solution that capitalizes on recent developments in sensor-based motion planning for whole-sensitive robot arms is proposed. The result would be a hybrid system in which global planning is done by a human operator, whereas local collision-free motion is controlled by an assisting autopilot.>

A sensor-based motion planning system for a robot arm manipulator must include these four basic components: sensor hardware; real-time signal/sensory data processing hardware/software a local step planning subsystem that works at the basic sample rate of the arm; and a subsystem for global planning. The objective of this work is to develop the fourth component, a real-time implementable algorithm that realizes the upper, global level of planning. Based on the current collection of local normals, the algorithm generates preferable directions of motion around obstacles, in order to guarantee reaching the target position if it is reachable. Experimental results from testing the developed system are also discussed.>

The terrain acquisition problem is formulated as that of continuous motion planning, and no constraints are imposed on obstacle geometry. Two algorithms are described for acquiring planar terrains with obstacles of arbitrary shape. Estimates of the algorithm performance are derived as upper bounds on the lengths of generated paths.>

A model of mobile robot navigation is considered in which the robot is a point automaton operating in an environment with unknown obstacles of arbitrary shapes. The robot's input information includes its own and the target-points coordinates as well as local sensing information such as that from stereo vision or a range finder. These algorithmic issues are addressed: (1) Is it possible to combine sensing and planning functions to produce 'active sensing' guided by the needs of planning? (The answer is yes). (2) Can richer sensing (e.g., stereo vision versus tactile) guarantee better performance, that is, resulting in shorter paths? (The general answer is no). A paradigm for combining range data with motion planning is presented. It turns out that extensive modifications of simpler tactile algorithms are needed to take full advantage of additional sensing capabilities. Two algorithms that guarantee convergence and exhibit different styles of behavior are described, and their performance is demonstrated in simulated examples.>

The authors describe an ongoing research project on the development of a sensitive skin and its control scheme for a 3D robot arm. The skin consists of hundreds of active infrared proximity sensors that cover the whole arm. This sensor-based motion planning system senses obstacles by emitting amplitude-modulated infrared light and then sensing the reflected signal. The problem of interpreting data from the sensors is handled by the step planning algorithm, which transforms the sensor data into local tangent normals in the configuration space. Once this information is available, a global path planning algorithm can then be used to move the arm through freespace or to follow the contour of obstacles that are encountered. Details of the skin design are presented, along with the computer hardware and operating logistics and the sensor data interpretation algorithm that connects this subsystem to the global motion planning subsystem.>

Results of one effort to implement a motion planning system for a robot arm operating in an uncertain environment are discussed. It is known that path planning algorithms with proven convergence can be designed for some planar and three-dimensional robot arm manipulators operating among unknown obstacles of arbitrary shapes. The attractiveness of such systems lies in their ability to operate in a complex, perhaps even time-varying, unstructured environment. Implementation of these algorithms, however, presents a variety of hardware and algorithmic problems related to: covering the arm with arrays of sensors to form a sensitive skin; processing real-time sensor data; designing complementary algorithms for step-by-step motion planning based on limited local information; and integrating these components, together with global planning algorithms, in a single system. The authors discuss various tradeoffs and solutions implemented in the sensor-based planning system for a planar arm manipulator developed in their laboratory and present a summary of their experiments with it.>

The problem of sensor-based path planning for robot arm manipulators operating among unknown obstacles of arbitrary shape is considered. It has been known that, in principle, algorithms with proven convergence can be designed for planar and simple three-dimensional robot arms operating under such conditions. However, implementation of these algorithms presents a variety of hardware and algorithmic problems related to covering the robot arm with a sensitive skin, processing data from large arrays of sensors, and designing algorithms for step-by-step motion planning based on limited information. The authors describe the hardware and the lower-level control algorithms of a system for robot motion planning in an uncertain environment and summarize results of experiments with the system.>

The authors present a paradigm for combining vision with motion planning. It turns out that extensive modifications of so-called tactile algorithms are needed to take full advantage of the additional sensing capabilities, while not sacrificing the algorithm convergence. Different design principles can be introduced that result in algorithm versions exhibiting different styles of behavior and producing different paths, without, in general, being superior to each other.>

This paper presents a survey of one approach to planning collision-free paths for an automaton operating in an environment with obstacles. Path planning is one of the central problems in robotics. Typically, the task is presented in the two- or three-dimensional space, with the automaton being either an autonomous vehicle or an arm manipulator with a fixed base. The multiplicity of approaches one finds in this area revolves around two basic models: in one, called path planning with complete information, perfect information about the geometry and positions of the robot and the obstacles is assumed, whereas in the other, called path planning with incomplete information, an element of uncertainty about the environment is present. The approach surveyed here, called dynamic path planning, has been developed in the last few years; it is based on the latter model and gives rise to algorithmic and computational issues very different from those in the former model. The approach produces provable (nonheuristic) path planning algorithms for an automaton operating in a highly unstructured environment where no knowledge about the obstacles is available beforehand and no constraints on the geometry of the obstacles are imposed.

An approach of dynamic path planning (DPP) was introduced elsewhere, and nonheuristic algorithms were described for planning collision-free paths for a point automaton moving in an environment filled with unknown obstacles of arbitrary shape. The DPP approach was further extended to a planar robot arm with revolute joints; in this case, every point of the robot body is subject to collision. Under the accepted model, the robot, using information about its immediate surroundings provided by the sensory feedback, continuously (dynamically) generates its path. Various kinematic configurations of planar arms with revolute and sliding joints are analyzed in this paper from the standpoint of applying the same strategy. It is shown that, depending on the arm kinematics, specific modifications must be introduced in the path planning algorithm to preserve convergence. The approach presents an attractive method for robot motion planning in unstructured environments with uncertainty.

The approach (called Continuous Path Planning, or CPP) developed in [1,10] for non-heuristic path planning for a point automaton or various planar robot arms moving in an environment with unknown obstacles, is extended here on a three-dimensional (3D) cartesian arm. The task is to move the arm endpoint from the starting to a target position. The arm body is assumed to be capable of "feeling" a contact (physical or at a distance) with an obstacle. With such local information, the convergence to a global goal can be assured. No constraints are imposed on the shape of the obstacles.

A necessary feature of robot systems is a capability to process robot paths in terms of Cartesian coordinates. However, the so-called articulated robot arms which represent the more advanced systems operate in terms of their revolute and sliding joint coordinates, and these do not lend themselves easily to translation into Cartesian equivalents. As a rule, the direct (joint-to-Cartesian space) coordinate transformation can be solved for in closed form. As for the inverse (Cartesian-to-joint) transformation, for some rather common arm designs practical solutions cannot be found in closed form. An iterative procedure for one such class of articulated robots is presented. The procedure produces an exact solution for the wrist tip position coordinates and an approximate solution for the wrist orientation coordinates. The convergence characteristics of the procedure are discussed.