Gravity based caging grasps are robotic grasps where the robot hand passively supports an object against gravity. When a robot hand supports an object at a local minimum of the object gravitational energy, the robot hand forms a basket like grasp of the object. Any object movement in a basket grasp requires an increase of the object gravitational energy, thus allowing secure object pickup and transport with robot hands that use a small number fingers. Thebasket grasp depthmeasures the minimal additional energy the object must acquire to escape the basket grasp. This paper extends previous work detailing a computation scheme that determines the depth of entire sets of candidate basket grasps associated with alternative finger placements on the object boundary before pickup. The computation relies on categorization ofescape stancesthat mark the basket grasp depth: double-support escapes are first analyzed and computed, then single-support escapes are analyzed and computed. The minimum energy combination of both types of escape stances defines the depth of entire sets of candidate basket grasps, which is then used to identify the deepest and hence most secure basket grasp. This paper additionally presents experimental validation of the computation scheme as well as numerical analysis of basket grasp robustness to object estimation errors.

Gravity based caging grasps are robotic grasps where the robot hand passively supports an object against gravity. When a robot hand supports an object at a local minimum of the object gravitational energy, the robot hand forms a basket like grasp of the object. Any object movement in a basket grasp requires an increase of the object gravitational energy, thus allowing secure object pickup and transport with robot hands that use a small number fingers. The basket grasp depth measures the minimal additional energy the object must acquire to escape the basket grasp. This paper describes a computation scheme that determines the depth of entire sets of candidate basket grasps associated with alternative finger placements on the object boundary before pickup. The computation relies on categorization of escape stances that mark the basket grasp depth: double-support escapes are first analyzed and computed, then single-support escapes are analyzed and computed. The minimum energy combination of both types of escape stances defines the depth of entire sets of candidate basket grasps, which is then used to identify the deepest and hence most secure basket grasp. The computation scheme is fully implemented and demonstrated on several examples with reported run-times.

This article studies the time optimal paths of a car-like mobile robot navigating in an obstacle-free planar environment. The robot, with forward and backward speeds, is controlled by bounded acceleration and limited front-wheels steering rate. The article extends previous results that solved this problem for a simplified car-robot model controlled by bounded speed and limited heading rate. The simplified car-robot model forms a unicycle with coupled bounds on the control inputs, while the full car-robot model has independent control inputs. The problem is analyzed as an optimal control problem by the minimum principle and by singular control theory. While the simplified car-robot model gives six time optimal path primitives, the optimality conditions for the full car-robot model yieldtwelve path primitivesthat form the time optimal paths. Three primitives involve singular controls of the steering front wheels that asymptotically align the robot along a straight line motion. All path primitives are analytically characterized and representative examples are studied in order to demonstrate how the path primitives combine to form the time optimal paths.

This paper considers progressively more demanding off-line shortest path sensory coverage problems in an optimization framework. In the first problem, a robot finds the shortest path to cover a set of target nodes with its sensors. Because this mixed integer nonlinear optimization problem (MINLP) is NP-hard, we develop a polynomial-time approximation algorithm with a bounded approximation ratio. The next problem shortens the coverage path when possible by viewing multiple targets from a single pose. Its polynomial-time approximation simplifies the coverage path geometry. Finally, we show how the complete sensory coverage problem can be formulated as a MINLP over a decomposition of a given region into arbitrary convex polygons. Extensions of the previously introduced algorithms provides a polynomial time solution with bounded approximation. Examples illustrate the methods.

This paper considers basket grasps, where a two-finger robot hand forms a basket that can safely lift and carry rigid objects in a 2-D gravitational environment. The two-finger basket grasps form special points in a high-dimensional configuration space of the object and two-finger robot hand. This paper establishes that all two-finger basket grasps can be found in a low-dimensional contact space that parametrizes the two-finger contacts along the supported object boundary. Using contact space, each basket grasp is associated with its depth that provides a security measure while carrying the object, as well as its safety margin away from a critical finger opening where the object drops-off into its intended destination. Geometric techniques that compute the depth and drop-off finger opening are described and illustrated with detailed graphical and numerical examples.

Multifinger caging offers a robust object grasping approach. However, while efficient computation of two-finger caging grasps is well developed, the computation of three-finger caging grasps has remained a challenge. This paper considers the caging of polygonal objects with three-finger hands which maintain an equilateral triangle formation during the grasping process. While the c-space of such hands is 4-D, their contact space that represents all two and three finger contacts along the grasped object's boundary forms a 2-D stratified manifold. The paper describes a caging graph that can be constructed in the hand's relatively simple contact space. Starting from a desired immobilizing grasp of the polygonal object, the caging graph can be readily searched for the largest finger opening that maintains a three-finger cage about the object to be grasped. Any equilateral finger placement within the corresponding caging regions guarantees robust object grasping.

Compliant grasping systems offer a wide range of robot hand designs. Understanding the stability behavior of compliant grasps can enhance the reliability and security of such hands. A classical result in compliant grasp mechanics states that a stable multifinger grasp can suddenly lose its stability when the finger force magnitudes exceed a critical threshold determined by the grasp's geometry. This event is known as coin snapping. This paper provides a full analysis of the coin snapping phenomenon for planar grasps governed by linear compliance laws. The analysis leads to important insights concerning compliant grasp security. For instance, does a grasping system give warning signs before an object snaps out of the fingers' grip? Is this an inevitable phenomenon in linearly compliant grasps? By systematically studying the bifurcation patterns of compliant multifinger grasps, this paper provides analytic characterization of the stability behavior of these systems, as well as answers to the mentioned questions under certain simplifying assumptions. Graphical examples and experimental measurements illustrate and validate the results.

The classical definition and analysis of force closure in robotic grasping focuses only on the fingertip bodies and their contacts with the grasped object. However, the kinematic properties of the hand mechanism can have a non-trivial effect on the actual type of force closure which can be realized at a given grasp. This paper takes a new look at this classical problem, and introduces technical results on force closure, or wrench resistance, which incorporate the hand mechanism's kinematics in this important grasp security measure. Based on a decomposition of the finger contact forces into canonical subspaces, the paper introduces a division of the finger contact forces into active and passive forces, as well as a dual division into resistant and internal contact forces. The paper develops new formal definitions of these concepts, and describes their mutual orthogonality relationships. Based on these definitions, the paper introduces new theorems of wrench resistant grasps which factor the hand mechanism's structure into the analysis of a given grasp. Examples illustrate how the hand mechanism's structure affects its ability to maintain secure wrench resistant grasps.

This paper is concerned with online coverage of unknown planar environments by a mobile robot of size D operating with a limited energy capacity battery. The battery capacity is represented by the path length L that the robot can travel under a full battery charge. Starting at S, the robot has to cover a planar environment containing unknown obstacles, and return to S upon task completion. During task execution, the robot may return to S at any time to recharge its battery. This paper first describes a battery powered offline coverage methodology, then introduces the battery powered coverage (BPC) algorithm that performs online battery powered coverage using position and local obstacle detection sensors. The performance of the BPC algorithm is measured by its competitiveness, determined by measuring the mobile robot's total online path length, l, relative to the optimal offline solution lopt. This paper establishes that the BPC algorithm has a competitive performance of l ≤ ( L/ D) lopt. This paper additionally establishes a universal lower bound of l ≥ log( L/ 4 D) lopt over all online battery powered coverage algorithms. Execution example illustrates the usefulness of the BPC algorithm.

This paper studies cages of convex polygonal objects using three point fingers. The fingers are said to cage the object when it is impossible to move the object arbitrarily far from its initial placement without penetrating the fingers. We consider a three-parameter model of the relative position of the fingers, which gives complete generality for three point fingers in the plane. We consider robustness of caging grasps - what variations in the relative position of the fingers is allowed without breaking the cage. Using a simple decomposition of free space around the polygon, we present an algorithm which gives all caging placements of the fingers and a characterization of the robustness of these cages, albeit at the cost of significant computational complexity.

Multifinger caging offers a rigorous and robust object grasping approach. Focusing on two-finger caging, this paper describes an algorithm for finding all two-finger cage formations of planar polygonal objects based on contact-space formulation. The paper shows that two-finger cages have several useful properties in contact space. First, the critical points of the cage representation in the hand's configuration space appear as critical points of the interfinger distance function in contact space. Second, these critical points can be graphically characterized directly on the object's boundary. Third, contact space admits a natural rectangular decomposition such that all critical points lie on the rectangle boundaries, and the sublevel sets of contact space and free space are topologically equivalent. These properties lead to a caging graph that can be readily constructed in contact space. Starting from a desired immobilizing grasp of a polygonal object, the caging graph is searched for the minimal, intermediate, and maximal caging regions surrounding the immobilizing grasp. An example constructed from real-world data illustrates and validates the method.

Multi-finger caging offers a robust approach to grasping. This paper describes an algorithm to find caging formations of a 3D polyhedron for two point fingers using a lower-dimensional contact-space formulation. The paper shows that contact space has several useful properties. First, the critical points of the cage in the hand's configuration space are identical to the critical points of the interfinger distance in contact space. Second, contact space can be naturally decomposed into 4D regions having useful properties. A geometric analysis of the critical points of the interfinger distance function results in a catalog of grasps in which the cages change topology, leading to a simple test to classify critical points. These properties lead to an easily constructed caging graph whose nodes contain the critical points of contact space. Starting from an immobilizing grasp, this graph can be searched to find local, intermediate, and maximal caging regions around that initial grasp. An implemented algorithm demonstrates the method.

This paper describes a method for computing the global time optimal path of a mobile robot navigating among obstacles subject to safe braking constraints. The paper first generalizes the classical Brachistochrone problem into a time optimal navigation problem, where the mobile robot navigates under a braking safety constraint near a point obstacle or a wall segment. The time optimal navigation problem is then formulated for general polygonal environments. Based on this formulation, the paper constructs a speed graph for the environment which consists of time optimal arcs that connect critical via points. The speed graph is then used to identify the path homotopy class which most likely contains the global time optimal path. Once a candidate homotopy class is selected, the exact time optimal path subject to safe braking constraints is computed within the homotopy class based on convexity properties of these paths. The results are illustrated with examples, described as readily implementable procedures, and demonstrated with experiments.

This paper is concerned with an online tethered coverage (TC), in which a mobile robot of size D is attached to a fixed point S by a cable of finite length L. Starting at S, the robot has to cover an unknown planar environment that contains obstacles and return to S with the cable fully retracted. The paper first establishes an optimal offline TC methodology, then introduces the TC algorithm that performs an online TC using position and local obstacle detection sensors. The performance of the TC algorithm is measured by its competitiveness, determined by measuring its total online path length l relative to the optimal offline solution lopt . The paper establishes that the TC algorithm has a competitive performance of l ≤ 2 L/D lopt. The paper additionally establishes a lower bound of l ≥ log(L/D) loptover a generic family of TC algorithms of which the TC algorithm is a special case. Execution example and experiments with a tethered recoiling mechanism illustrate the usefulness of the TC algorithm.

Based on a novel contact-space formulation, this paper presents a new algorithm to find two-fingered caging grasps of planar polygonal objects. We show that the caging problem has several useful properties in contact space. First, the critical points of the cage representation in the hand's configuration space appear as critical points of an inter-finger distance function in contact space. Second, the critical points of this distance function can be simply characterized. Third, the contact space admits a rectangular decomposition where the distance function is convex in each rectangle, and all critical points lie on the rectangle boundaries. This property leads to a natural “caging graph,” which can be readily searched to construct the caging sets. An example, constructed from real-world data illustrates and validates the method.

We introduce the concept of Local Force Closure. We define a local force closure grasp as a grasp which is capable of resisting some given external wrench as well as (through local variation in contact wrenches) any wrench in some neighborhood of the given wrench, with grasp quality exceeding some given threshold. Local force closure is useful in applications where a grasp only needs to resist some given external wrench, rather than fully constraining object, but where there is some uncertainty regarding the exact external wrench that needs to be resisted, or where there is a possibility of having to cope with some (relatively small) unknown disturbance forces. We show that by allowing disc-shaped fingers in contact with convex vertices of a polygonal object, any given wrench can be resisted by just two frictionless fingers. For a given polygonal object with n vertices and an external wrench wext, we show how to find all pairs of features of P, that admit grasps capable of resisting wextwith grasp quality greater or equal to some threshold Q, in O(n3/2+ε+ K) time, where K is the number of pairs in the output and ε is some arbitrarily small, positive constant. We then show how to adapt our algorithm to guarantee that the features reported, admit local force closure grasps.

This paper considers the problem of fast autonomous mobile robot navigation between obstacles while attempting to maximize velocity subject to safe braking constraints. The paper introduces position-velocity configuration space. Within this space, keeping a uniform braking distance from the obstacles can be modeled as forbidden regions called vc-obstacles. Using Morse Theory, the paper characterizes the critical position-velocity points where two vc-obstacles meet and locally disconnect the free position-velocity space. These points correspond to critical events where the robot's velocity becomes too large to support safe passage between neighboring obstacles. The velocity dependent critical points induce a cellular decomposition of the free position-velocity space into cells. Each cell is associated with a particular range of velocities that can be safely followed by the robot. The paper proposes a practical algorithm that searches the cells' adjacency graph for a maximum velocity path. The algorithm outputs a pseudo time optimal path which maintains safe braking distance from the obstacles throughout the robot motion. Simulations demonstrate the algorithm and highlight the usefulness of taking the path's velocity into account during the path planning process.

The immobilization of nonrigid objects is a relatively unexplored area in grasp mechanics. In this paper, we consider the immobilization of freely moving serial chains ofnhinged polygons using frictionless point fingers. We first set this problem in the context of classical grasping theory by showing that chain immobilization can only be achieved with equilibrium grasps. Then, we describe two immobilization approaches based on first- and second-order geometric effects. Based on curvature effects, chains ofn≠ 3 hinged polygons with nonparallel edges can be immobilized byn+ 2 frictionless point fingers. Serial chains of three hinged polygons form an exception to this rule. Based on first-order geometric effects, we describe how to immobilize any chain ofnhinged polygons with only one extra contact for the entire chain, using a total ofn+ 3 frictionless point fingers. Moreover, the immobilizing grasps are robust with respect to small contact placement errors. The results are illustrated with examples and described as readily implementable procedures.

We explore the problem where a group of robots with different velocities search for a target in an unbounded unknown environment. The target position is un known, hence, an online search algorithm is developed. The H-MRSTM algorithm (Heterogeneous Multi-Robot Search Time Multiplication), launches a group of n robots from a common starting location to search for the target. The robots are assigned to search inside a series of concentric discs with increasing radii. Each robot is assigned to search inside a disc and when completing the search inside this disc without finding the target, the robot is assigned to search in the next unoccupied disc. We prove that every algorithm that solves this search problem must have at least a quadratic time competitive complexity and prove that the H-MRSTM algorithm's complexity is also quadratic. Hence, we obtain both an upper and lower bound on the time competitive complexity of the search problem. Consequently, H-MRSTM is proved to be optimal. Simulations in various environments show that the average case performance of H-MRSTM is superior to that of homogeneous multi-robot and single robot algorithms. In depth simulation analyses evaluated the effect of several other parameters such as the initial disc search time, the distribution of the velocities, the number of robots and the position of the target.

The immobilization of non-rigid objects is a relatively unexplored area in grasp mechanics. This paper considers the immobilization of 2D serial chains of n hinged polygons at a given placement using frictionless point fingers. The paper sets the problem in the context of classical grasping theory by showing that chain immobilization can only be achieved with equilibrium grasps. In earlier work we described an immobilization procedure for serial chains of n≠3 polygons using n+2 frictionless point fingers. However, the immobilization of three-link chains remained an open problem. This paper establishes that three-link chains can usually be immobilized with five point fingers, but certain three-link chains can only be immobilized with six point fingers. The paper then considers the robust immobilization of serial chains under small contact placement errors. We describe a procedure for robust immobilization of n-link chains that requires only one extra contact for the entire chain, using a total of n+3 frictionless point fingers. The immobilization procedures and the exceptional three-link chains are illustrated with example.

This paper presents a new on-line planner for dynamic environments that is based on the concept of velocity obstacles (VO). It addresses the issue of motion safety, i.e. avoiding states of inevitable collision, by selecting a proper time horizon for the velocity obstacle. The proper choice of the time horizon ensures that the boundary of the velocity obstacle coincides with the boundary of the set of inevitable collision states. This time horizon is determined by the minimum time it would take the robot to avoid collision, either by stopping or by passing the respective obstacle. The planner generates a near-time optimal trajectory to the goal by selecting at each time step the velocity that minimizes the time-to-go and is out of the velocity obstacle. The planner takes into account the shape, velocity, and path curvature of the obstacle's trajectory. It is demonstrated for on-line motion planning in very crowded static and dynamic environments.

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 the stability of planar mechanisms supported by multiple frictional contacts against gravity. Stability of equilibrium postures is investigated under initial perturbations which may involve sliding or separation at the contacts. The frictional dynamics is formulated using the notion of contact modes, and the related problems of solution ambiguity and inconsistency are reviewed. The paper then uses the condition of strong equilibrium to eliminate ambiguities, and defines a new condition of kinematic-strong equilibrium which additionally eliminates frictional inconsistencies. It is then proven that strong equilibrium is necessary for stability of frictional equilibrium postures, and that kinematic-strong equilibrium guarantees finite-time recovery of an initially perturbed contact. The results are demonstrated on a reduced model of a rigid body having a variable center-of-mass and supported by two frictional contacts. A companion paper completes the analysis of this reduced problem by investigating the overall hybrid dynamics and deriving sufficient conditions for its stability.

This paper is concerned with the hybrid dynamics and stability of a planar rigid body supported by two frictional contacts in a gravitational field. The stability of equilibrium postures is investigated under initial perturbations which may involve sliding or separation of the contacts. The paper formulates the hybrid dynamics induced by collisions and impacts at the two contacts. The Zeno behavior of bouncing and clattering motion converging to limit points of one- or two-contact re-establishment are analyzed, and a condition guaranteeing convergence to a Zeno point is derived. Finally, this condition is combined with the results of the companion paper to derive sufficient conditions for stability of frictional two-contact equilibrium postures of a planar rigid body.

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.

This paper considers the stability of an object supported by several frictionless contacts in a potential field such as gravity. The bodies supporting the object induce a partition of the object's configuration space into strata corresponding to different contact arrangements. Stance stability becomes a geometric problem of determining whether the object's configuration is a local minimum of its potential energy function on the stratified configuration space. We use stratified Morse theory to develop a generic stance stability test that has the following characteristics. For a small number of contacts - less than three in 2D and less than six in 3D - stance stability depends both on surface normals and surface curvature at the contacts. Moreover, lower curvature at the contacts leads to better stability. For a larger number of contacts, stance stability depends only on surface normals at the contacts. The stance stability test is applied to quasi-static locomotion planning in two dimensions. The region of stable center-of-mass positions associated with ak-contact stance is characterized. Then, a quasi-static locomotion scheme for a three-legged robot over a piecewise linear terrain is described. Finally, friction is shown to provide robustness and enhanced stability for the frictionless locomotion plan. A full maneuver simulation illustrates the locomotion scheme.

The dynamics of a rigid body sliding on a frictional contact can have multiple solutions as well as sudden contact-mode transitions. This paper is concerned with dynamic jamming, an event where a sliding rigid body suddenly jamms and experiences an impact-like transition into free flying mode. Using a simple experiment that mimics a sliding rigid-body situation, dynamic jamming is recorded for the first time. The phenomenon occurs almost at the theoretical position-and-velocity prediction, indicating that this type of jamming is not a mere artifact of the rigid-body modeling paradigm. A new interpretation of dynamic jamming is offered in terms of the body's instantaneous acceleration center. Once this center reaches a graphically determinable jamming line, the body ceases its sliding mode and experiences a dynamic jamming event. Based on this insight, some ways to prevent dynamic jamming are discussed.

Quasistatic multi-legged locomotion consists of a sequence of equilibrium postures where the mechanism supports itself against gravity while moving free limbs to new positions. A posture maintains equilibrium if the contacts can passively support the mechanism against gravity. This paper is concerned with computation and graphical characterization of equilibrium postures for mechanisms supported by frictional contacts in a three-dimensional gravitational field. For a given set of contacts, this problem reduces to the computing feasible region R, defined as the center-of-mass positions that maintain equilibrium while satisfying the frictional constraints. This paper continues a previous work by the authors, and provides a new method for computing the boundary of R for 3-contact stances. The paper also gives physical and geometric interpretations for the boundary of R and discusses its relation with the classical support polygon principle. Finally, the paper reports experimental results that validate the theoretical computation.

Quasistatic multi-legged locomotion consists of a sequence of equilibrium postures where the mechanism supports itself against gravity while moving free limbs to new positions. A posture maintains equilibrium if the contacts can passively support the mechanism against gravity. This paper is concerned with identifying and computing equilibrium postures for mechanisms supported by frictional contacts in a three-dimensional gravitational field. The complex kinematic structure of the mechanism is lumped into a single rigid body B having the same contacts with the environment and a variable center of mass. The identification of equilibrium postures associated with a given set of contacts is reduced to the identification of center-of-mass locations of B that maintain equilibrium stances while all nonlinear frictional constraints are satisfied. Focusing on 3-contact stances, this paper provides an exact formulation for the boundary of the center-of-mass feasible region R as a solution of implicit polynomials. The paper also provides a conservative polyhedral approximation of R by using techniques for projection of convex polytopes. The exact and approximate computations of R are demonstrated with graphical examples

This paper describes a fixture planning method that minimizes object deflection under external loads. The method takes into account the natural compliance of the contacting bodies and applies to two-dimensional and three-dimensional quasirigid bodies. The fixturing method is based on a quality measure that characterizes the deflection of a fixtured object in response to unit magnitude wrenches. The object deflection measure is defined in terms of frame-invariant rigid body velocity and wrench norms and is therefore frame invariant. The object deflection measure is applied to the planning of optimal fixture arrangements of polygonal objects. We describe minimum-deflection fixturing algorithms for these objects, and make qualitative observations on the optimal arrangements generated by the algorithms. Concrete examples illustrate the minimum deflection fixturing method. Note to Practitioners-During fixturing, a workpiece needs to not only be stable against external perturbations, but must also stay within a specified tolerance in response to machining or assembly forces. This paper describes a fixture planning approach that minimizes object deflection under applied work loads. The paper describes how to take local material deformation effects into account, using a generic quasirigid contact model. Practical algorithms that compute the optimal fixturing arrangements of polygonal workpieces are described and examples are then presented.

This paper considers multiple-contact arrangements where several bodies grasp, fixture, or support an object via frictional point contacts. Within a strictly rigid-body modeling paradigm, when an external wrench (i.e., force and torque) acts on the object, the reaction forces at the contacts are typically indeterminate and span an unbounded linear space. This paper analyzes the contact reaction forces within a generalized quasi-rigid-body framework that keeps the desirable geometric properties of rigid-body modeling, while also including more realistic physical effects. We describe two basic principles that govern the contact mechanics of quasi-rigid bodies. The main result is that for any given external wrench acting on a quasi-rigid object, the statically feasible contact reaction forces lie in a bounded Polyhedral set that depends on the external wrench, the grasp's geometry, and the preload forces. Moreover, the bound does not depend upon any detailed knowledge of the contact mechanics parameters. When some knowledge of the parameters is available, the bound can be sharpened. The polyhedral bound is useful for "robust" grasp and fixture synthesis. Given a set of external wrenches that may act upon an object, the grasp's geometry and preload forces can be chosen such that all of these external wrenches would be automatically supported by the contacts

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.

This paper is concerned with the problem of identifying robust equilibrium postures of a planar mechanism supported by fixed frictional contacts in a two-dimensional gravitational field. The complex kinematic structure of the mechanism is lumped into a single rigid body, B, with a variable center of mass. Inertial forces generated by moving parts of the mechanism are lumped into a neighborhood of wrenches centered at the nominal gravitational wrench. The identification of the robust equilibrium postures associated with a given set of contacts is reduced to the identification of center-of-mass locations that maintain equilibrium of B with respect to any wrench in the given neighborhood. The static response of B to an external wrench involves static indeterminacy and frictional constraints. The region of center-of-mass locations that generate equilibrium with respect to a particular external wrench is formulated as a linear programming problem, and a full graphical characterization is provided. The result is then generalized to robust equilibrium postures that resist a neighborhood of external wrenches. Finally, we present experimental results that validate the criteria for feasible equilibrium postures.

We describe a practical method for computing the statically stable postures of a planar mechanism in a two-dimensional gravitational field. Our method lumps the complex kinematic structure of the mechanism into a rigid body B having a variable center of mass, while inertial forces generated by moving parts of the mechanism are lumped into a neighborhood of disturbance wrenches centered at the nominal gravitational wrench. Given this reduction, the statically stable postures of the mechanism correspond to center-of-mass locations of B that guarantee static stability for the neighborhood of wrenches. However, the response of B to an applied wrench involves dynamic ambiguity associated with different reaction modes at the contacts. Hence we compute only those center-of-mass locations where B maintains a non-ambiguous equilibrium for the entire neighborhood of wrenches. These center-of-mass locations are called the robust stability region of the posture. Focusing on two-contact postures, we compute the robust stability region as an arrangement of planar cells. Finally, we sketch an application of the results to robust locomotion planning of a 3-legged mechanism.

The mechanics of friction and compliance in multi-contact arrangements is key to understanding and predicting grasp stability and dynamic response to external loads. This paper introduces a comprehensive model for the nonlinear force-displacement relationship at a frictional contact. The model is given in an analytic lumped parameter form suitable for on-line grasping applications, and is entirely determined by material and geometric properties of the contacting bodies. The force-displacement law predicts a nonlinear tangential stiffening as the normal load increases. As a result, the composite stiffness matrix of a frictional grasp is asymmetric, indicating that such grasps are not governed by any potential energy. The consequences for grasp stability are investigated. We formulate a rule for preloading frictional grasps which guarantees stable response at the individual contacts. Then we obtain a criterion for selecting contact points which guarantees overall grasp stability. The synthesis rule and its effect on grasp stability is illustrated with a simple 2D example.

This paper computes and analyzes the natural compliance of fixturing and grasping arrangements. Traditionally, linear-spring contact models have been used to determine the natural compliance of multiple contact arrangements. However, these models are not supported by experiments or elasticity theory. We derive a closed-form formula for the stiffness matrix of multiple contact arrangements that admits a variety of nonlinear contact models, including the well-justified Hertz model. The stiffness matrix formula depends on the geometrical and material properties of the contacting bodies and on the initial loading at the contacts. We use the formula to analyze the relative influence of first- and second-order geometrical effects on the stability of multiple contact arrangements. Second-order effects, i.e., curvature effects, are often practically beneficial and sometimes lead to significant grasp stabilization. However, in some contact arrangements, curvature has a dominant destabilizing influence. Such contact arrangements are deemed stable under an all-rigid body model but, in fact, are unstable when the natural compliance of the contacting bodies is taken into account. We also consider the combined influence of curvature and contact preloading on stability. Contrary to conventional wisdom, under certain curvature conditions, higher preloading can increase rather than decrease grasp stability. Finally, we use the stiffness matrix formula to investigate the impact of different choices of contact model on the assessment of the stability of multiple contact arrangements. While the linear-spring model and the more realistic Hertz model usually lead to the same stability conclusions, in some cases, the two models lead to different stability results.

This paper describes an experimental fixturing system wherein fixel reaction forces, workpiece loading, and workpiece displacements are measured during simulated fixturing operations. The system's configuration, its measurement principles, and tests to characterize its performance are summarized. This system is used to experimentally determine the relationship between workpiece displacement and variations in fixel preload force or workpiece loading. We compare the results against standard theories, and conclude that commonly used linear spring models do not accurately predict workpiece displacements, while a non-linear compliance model provides better predictive behavior.

This paper considers 2D contact arrangements where several bodies grasp, fixture, or support an object via frictional point contacts. Within a strictly rigid body modelling paradigm, when an external wrench (i.e. force and torque) acts on the object, the reaction forces at the contacts are indeterminate and span an unbounded linear space. This paper analyzes the contact forces within a quasi-rigid body framework that keeps the desirable geometric properties of rigid body modelling, while also includes more realistic physical effects. Using two principles governing the mechanics of quasi-rigid contacts, we show that for any given external wrench acting on the object, the contact forces lie in a bounded polyhedral set. The polyhedral bound depends on the external wrench, the grasp's geometry, and the preload forces. But it does not depend on any detailed knowledge of the contact mechanics parameters. The bound is useful for "robust" grasp and fixture synthesis. Given a collection of external wrenches that may act on an object, the grasp's geometry and preload forces can be chosen such that all of these external wrenches would be automatically supported by the contacts.

This paper presents an algorithm, called PCG, for planning the foothold positions of spider-like robots in planar tunnels bounded by piece-wise linear walls. The paper focuses on 3-limb robots, but the algorithm generalizes to robots with a higher number of limbs. The input to the PCG algorithm is a description of a tunnel having an arbitrary piece-wise linear geometry, a lower bound on the amount of friction at the contacts, as well as start and target foothold positions. Using efficient convex programming techniques, the algorithm approximates the possible foothold positions as a collection of cubes in contact c-space. A graph structure induced by the cubes has the property that its edges represent feasible motion between neighboring sets of 3-limb postures. This motion is realized by lifting one limb while the other two limbs brace the robot against the tunnel walls. A shortest-path search along the graph yields a 3-2-3 gait pattern that moves the robot from start to target using a minimum number of foothold exchanges. Simulation results demonstrate the PCG algorithm in a tunnel environment.

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.

Presents an immobilization based control method for spider-like robots that move quasistatically in tunnel environments. The control method is based on an immobilization theory which ensures that when a spider-like mechanism is bracing against the environment at an immobile posture, the naturally occurring compliance at the contacts stabilizes the mechanism as a single body. Based on this result, we present two versions of a position control law for general k-limbed spider robots. We show that if the controller's stiffness (i.e. proportional gain) is above a lower limit determined by the spider and environment parameters, stability of the closed-loop spider system is guaranteed. We present dynamic simulations of a spider robot moving in a tunnel under the influence of the immobilization-based control law. The simulations show excellent convergence properties of the control algorithm. A four-legged spider prototype has been built, and we conclude with a description of initial experiments with this robot.

The classical notion of force closure is formulated for multifingered hands, where the fingers actively apply any desired force consistent with friction constraints at the contacts. This paper considers a simpler notion of passive force closure, where each finger obeys some force-displacement law that depends on the finger's joint parameters. The fingers apply initial preload grasping forces, and the grasped object is stabilized against external disturbances by the automatic response of the grasping fingers. After motivating the usefulness of passive force closure, we characterize the conditions for its existence. Then we introduce the passive stability set, defined as the collection of external wrenches that can be passively resisted by a given grasp. We introduce a class of grasp arrangements where the grasping mechanism is compliant while the grasped object is rigid. Such compliant-rigid systems are common, and for these systems the passive closure set can be computed in closed form. Simulation results demonstrate the computation of the passive closure set for two and three-finger planar grasps.

This paper presents a curvature-based bound on the number of frictionless fingers or fixtures required to immobilize 3D objects. A recently developed second-order mobility theory has shown that in addition to first-order geometrical effects, second-order or curvature effects play an important role in the kinematics of contact. We show that when second-order effects are included, four convex fingers or fixtures with sufficiently flat curvature can immobilize any generic smooth or polyhedral 3D object. The derivation of the improved bound proceeds by first constructing a suitable equilibrium grasp of the given object, called a pre-immobilizing grasp. Depending on the object's geometry, a pre-immobilizing grasp may have two, three, or four contacts. The conversion of a pre-immobilizing grasp to a four-finger immobilizing grasp depends on the object's curvature at the contacts. This curvature can be convex, concave, or saddle-like. Since a pre-immobilizing grasp can have k = 2, 3, 4 contacts, there are 31 cases to consider. We construct immobilizing grasps for all of these cases, and present simulation results showing the immobilization of selected object types.

This paper presents a systematic approach to quantifying the effectiveness of compliant grasps and fixtures of an object. The approach is physically motivated and applies to the grasping of two- and three-dimensional objects by any number of fingers. The approach is based on a characterization of the frame-invariant features of a grasp or fixture stiffness matrix. In particular, we define a set of frame-invariant characteristic stiffness parameters, and provide physical and geometric interpretation for these parameters. Using a physically meaningful scheme to make the rotational and translational stiffness parameters comparable, we define a frame-invariant quality measure, which we call the stiffness quality measure. An example of a frictional grasp illustrates the effectiveness of the quality measure. We then consider the optimal grasping of frictionless polygonal objects by three and four fingers. Such frictionless grasps are useful in high-load fixturing applications, and their relative simplicity allows an efficient computation of the globally optimal finger arrangement. We compute the optimal finger arrangement in several examples, and use these examples to discuss properties that characterize the stiffness quality measure.

Presents a globally convergent range-sensor based navigation algorithm in three-dimensions, called 3D Bug. The 3D Bug algorithm navigates a point robot in a three-dimensional unknown environment using position and range sensors. The algorithm strives to process the sensory data in the most reactive way possible, without sacrificing the global convergence guarantee. Moreover, unlike previous reactive-like algorithms, 3D Bug uses three-dimensional range data and plans three-dimensional motion throughout the navigation process. The algorithm alternates between two modes of motion. During motion towards the target, which is the first motion mode of the algorithm, the robot follows the locally shortest path in a purely reactive fashion. During traversal of an obstacle surface, which is the second mode of motion, the robot incrementally constructs a reduced data structure of an obstacle, while performing local shortcuts based on range data. We resent preliminary simulation results of the algorithm, which show that 3D Bug generates paths that resemble the globally shortest path in simple scenarios. Moreover, the algorithm generates reasonably short paths even in concave, room-like environments.

This paper presents a novel design of a 4-legged "spider" robot capable of moving in a wide range of two-dimensional tunnels. The spider moves in a quasi-static manner, by stably bracing itself against the tunnel walls and moving a free limb to a new position. The design has been strongly influenced by the recent immobilization theory of Rimon and Burdick (1995, 1998). The theory dictates the minimum number of limbs such a spider can have, as well as the shape of the footpads. The class of tunnel geometries dictates other key parameters of the spider, such as limb dimensions and number of degrees of freedom of each limb. We review the relevant components of the immobilization theory, then describe the details of the spider design. The spider will initially move under a worst-case assumption of slippery tunnel walls, and we also describe a locomotion strategy under this assumption. The spider has been built and is currently undergoing locomotion experiments.

This paper presents an approach to planning compliant grasps and fixtures in which the object exhibits minimal deflection under external disturbances. The approach, which applies to general two- and three-dimensional grasps and fixtures represented by any quasi-rigid compliance model, employs a quality measure that characterises the grasped or fixtured object's worst-case deflection caused by disturbing wrenches lying in the unit wrench ball. To ensure well-defined notions of deflection and wrench balls, frame-invariant rigid body velocity and wrench norms are used. As illustrated by its application to fixtures of polygonal objects, our minimum-deflection approach can be effectively applied to planning grasps and fixtures where deflection significantly influences performance.

This paper presents a novel geometrical representation of the dynamical properties of two degrees-of-freedom mechanisms, as a surface called an isometric visualization of the mechanism. The kinematic properties of the mechanism are represented by the surface topology. The dynamical properties of the mechanism are represented by a metric induced on the surface by the mechanism's kinetic energy. Isometric visualization enables an intuitive study of the dynamical properties of a mechanism, since arc length on the isometric visualization surface is determined by the kinetic energy metric. In particular, free motions of the mechanism are represented by curves of minimal arc length in its isometric visualization surface, called geodesics. We consider two degrees of freedom open kinematic chain mechanisms, with prismatic and revolute joints. For these mechanisms, we present formulas for the isometric visualization of all planar mechanisms, and for two classes of spatial mechanisms. Then we render a catalog of isometric visualizations of several basic mechanisms, and present tools for extracting information on the mechanism's dynamics from its isometric visualization. These tools include a measure for the stability of a free motion, based on the Gaussian curvature of the mechanism's isometric visualization surface. This new representation of mechanism configuration spaces has potential uses in mechanism and controller design.

Presents an algorithm for minimizing the search effort of a mobile robot navigating in an unknown environment. First we describe a strategy for navigating a cylinder-shaped mobile robot in an area with unknown obstacles using range data. The strategy searches a graph which is constructed incrementally during the navigation process. Then we present a new algorithm for searching the graph which attempts to minimize the search effort, measured by the length of the path traveled by the robot. The algorithm, called A/sub /spl epsiv//*-DFS, combines features of the classical A* and DFS graph-search algorithms, and generates /spl epsiv/-optimal paths. Moreover, A/sub /spl epsiv//*-DFS is general and can be used by any online search strategy. The algorithm uses E as a parameter, where /spl epsiv/=0 corresponds to A* while /spl epsiv/=/spl infin/ corresponds to DFS. We study the performance of A/sub /spl epsiv//*-DFS for various values of /spl epsiv/ on simulated environments, and indicate how to best choose /spl epsiv/ for a given class of environments.

Using a configuration-space approach, the paper develops a 2nd-order mobility theory for rigid bodies in contact. A major component of this theory is a coordinate invariant 2nd-order mobility index for a body, B, in frictionless contact with finger bodies A/sub 1/,...A/sub k/. The index is an integer that captures the inherent mobility of B in an equilibrium grasp due to second order, or surface curvature, effects. It differentiates between grasps which are deemed equivalent by classical 1st-order theories, but are physically different. We further show that 2nd-order effects can be used to lower the effective mobility of a grasped object, and discuss implications of this result for achieving new lower bounds on the number of contacting finger bodies needed to immobilize an object. Physical interpretation and stability analysis of 2nd-order effects are taken up in the companion paper.

For part I, see ibid., p.696-708. The paper considers how forces are produced by compliance and surface curvature effects in systems where an object a is kinematically immobilized to second-order by finger bodies A/sub l/,...,A/sub k/. A class of configuration-space based elastic deformation models is introduced. Using these elastic deformation models, it is shown that any object which is kinematically immobilized to first or second-order is also dynamically locally asymptotically stable with respect to perturbations. Moreover, it is shown that for preloaded grasps kinematic immobility implies that the stiffness matrix of the grasp is positive definite. The stability result provides physical justification for using second-order effects for purposes of immobilization in practical applications. Simulations illustrate the concepts.

This paper presents a systematic approach for quantifying the quality of compliant grasps. Appropriate tangent and cotangent subspaces to the object's configuration space are studied, from which frame-invariant characteristic compliance parameters are defined. Physical and geometric interpretations are given to these parameters, and a practically meaningful method is proposed to make the parameters comparable. A frame-invariant quality measure is then defined, and grasp optimization using this quality measure is discussed with examples.

This paper presents a method to compute stiffness matrices for compliant grasps and fixtures. While the linear spring contact model has been widely used by robotics researchers, it is in general not accurate for practical applications. More realistic models, including the well-verified Hertz model, are incorporated by use of overlap functions. We derive a stiffness matrix formula that considers surface and material properties of the contacting bodies and applies to both planar and solid grasps. The effects of contact geometry are analyzed and illustrated with examples.

This paper considers the gravitational stability of a frictionless 3-dimensional object in contact with immovable objects. Arbitrarily curved objects are considered. This paper also shows how to determine the region over which the object's center of mass can move while the object maintains a given set of contacts and remains in stable equilibrium. We present symbolic solutions for up to three contacts and discuss numerical solutions for larger numbers of contacts. This analysis has application in planning the motions of quasi-statically walking robots over uneven terrain and the manipulation of heavy objects.

We present TangentBug, a new range-sensor based navigation algorithm for two degrees-of-freedom mobile robots. The algorithm combines local reactive planning with globally convergent behaviour. For the local planning, TangentBug uses the range data to compute a locally shortest path based on a novel structure, termed the local tangent graph (LTG). The robot uses the LTG for choosing the locally optimal direction while moving towards the target. The robot also uses the LTG in its other motion mode, where it follows an obstacle boundary. In this mode the robot uses the LTG for making local short-cuts and testing a leaving condition which allows the robot to resume its motion towards the target. We analyze the convergence and performance properties of TangentBug. We also present simulation results, showing that TangentBug consistently performs better than the classical VisBug algorithm. Moreover, TangentBug produces paths that in simple environments approach the globally optimal path as the sensor's maximal detection range increases.

This paper is concerned with the following caging problem. One wishes to surround an object B by a multi-fingered hand such that B has some freedom to move but still cannot escape the "cage" formed by the fingers. The authors introduce a new notion of caging set, which is based on the configuration-space representation of the free motions of the hand-system with respect to B. Using stratified Morse theory, the authors show that the hand's configuration at which the cage is broken corresponds to a frictionless equilibrium grasp. This allows the authors to formulate a technique for computing the caging set of a 2-fingered hand whose opening is controlled by a single parameter. The technique generalizes to 1-parameter gripping systems having higher number of fingers.

This paper considers the relationship between force and form closure. Based on a previously developed mobility theory, the authors give precise definitions for 1/sup st/ and 2/sup nd/ order form closure for frictionless grasps. The authors also introduce the new concept of 2/sup nd/ order force closure. The authors show for the case of frictionless contacts, a grasp is 1/sup st/ order force closure if and only if it is 1/sup st/ order form closure. The authors further show that a grasp is 2/sup nd/ order force closure if and only if it is also 2/sup nd/ order form closure.

In both robot grasping and robot locomotion, we wish to hold objects stably in the presence of gravity. We present a derivation of second-order stability conditions for a supported heavy object, employing the tool of Stratified Morse theory. We then apply these general results to the case of objects in the plane.

This paper develops new lower bounds on the number of frictionless fingers or fixtures which are required to immobilize planar objects. We study in detail the case of objects with smooth boundaries and polygonal objects. Analogous results for the case of piecewise smooth objects follow directly from the analysis presented herein. These results have obvious applications to fixture planning and grasp planning, as we show that it is possible to immobilize objects with fewer fingers than was previously thought possible.

Using a configuration-space approach, this paper develops a coordinate invariant 2nd order mobility index for a body, B, in frictionless contact with finger bodies A_1, ..., A_k. The index captures the inherent mobility of B in an equilibrium grasp due to 2nd order, or surface curvature, effects. It differentiates between grasps which are deemed equivalent by the classical 1st order theories, but are physically different. In a companion paper we discuss applications and provide physical justification for using 2nd order immobility effects.

We investigate the contact forces generated by 2/sup nd/ order effects for a body B, in frictionless contact with finger bodies A/sub 1/,..., A/sub k/. A simple paradox shows that rigid body models are inadequate to explain how contact forces are generated by 2/sup nd/ order effects. A class of configuration-space based elastic deformation models are introduced, and are shown to explain the restraining forces produced by surface curvature. Using these elastic deformation models, we prove that any object which is kinematically immobilized to 1/sup st/ or 2/sup nd/ order is also dynamically locally asymptotically stable with respect to perturbations.>

We propose a truly incremental exact navigation algorithm for general articulated robots: the robot may start with no apriori information about its environment, and is guaranteed to find the goal if it is reachable, or halt otherwise. The algorithm, termed the incremental roadmap algorithm, constructs a roadmap based on distance data collected online and encoded as repulsive potential field. The incremental behavior is achieved with two novel abstract sensors: a critical point detector and a minimum passage detector. We show by examples which environmental features must be measured by the detectors for a planar-body robot.>

A methodology for exact robot motion planning and control that unifies the purely kinematic path planning problem with the lower level feedback controller design is presented. Complete information about a freespace and goal is encoded in the form of a special artificial potential function, called a navigation function, that connects the kinematic planning problem with the dynamic execution problem in a provably correct fashion. The navigation function automatically gives rise to a bounded-torque feedback controller for the robot's actuators that guarantees collision-free motion and convergence to the destination from almost all initial free configurations. A formula for navigation functions that guide a point-mass robot in a generalized sphere world is developed. The simplest member of this family is a space obtained by puncturing a disk by an arbitrary number of smaller disjoint disks representing obstacles. The other spaces are obtained from this model by a suitable coordinate transformation. Simulation results for planar scenarios are provided.>

A provably correct navigation algorithm for a simple rigid body in a planar environment cluttered with disc obstacles is presented. The algorithm specifies a collision-free path by subjecting the robot to the influence of a navigation function, a special artificial potential function whose most crucial property is the absence of undesired local minima. Unlike other unknown algorithms, it specifies a feedback control law that is guaranteed to move the physical robot to the goal without it hitting obstacles, subject to the bounded-torque capability of the robot's actuators. Previous work has shown that navigation functions are guaranteed to exist. Construction of navigation functions for a realistic situation is proposed. The implementation of the algorithm reveals a numerical difficulty, which is effectively corrected by making a slight heuristic modification to the navigation function. This is discussed and illustrated.>

Navigation functions on forests of stars, geometrically complicated C-spaces (configuration spaces) that are topologically indistinguishable from a simple disc punctured by disjoint smaller discs representing model obstacles, are constructed. For reasons of mathematical tractability, each C-space obstacle is approximated by a Boolean combination of linear and quadratic polynomial inequalities (with sharp corners allowed), and a calculus of implicit representations is used to effectively represent such obstacles. Evidence is provided of the effectiveness of this technology of implicit representations in the form of several simulation studies.>

The authors consider the construction of navigation functions on configuration spaces whose geometric expressiveness is rich enough for navigation amidst real-world obstacles. They describe a general methodology which extends the construction of navigation functions on sphere worlds to any smoothly deformable space. According to this methodology, the problem of constructing a navigation function is reduced to the construction of a transformation mapping a given space into its model sphere world. The transformation must satisfy certain regularity conditions guaranteeing invariance of the navigation function properties. The authors demonstrate this idea by constructing navigation functions on star worlds: n-dimensional star shaped subsets of E/sup n/ punctured by any finite number of smaller disjoint n-dimensional stars. This construction yields automatically a bounded torque feedback control law which is guaranteed to guide the robot to destination point from almost every initial position without hitting any obstacle.>

The utility of artificial potential functions is explored as a means of translating automatically a robot task description into a feedback control law to drive the robot actuators. A class of functions is sought which will guide a point robot amid any finite number of spherically bounded obstacles in Euclidean n-space toward an arbitrary destination point. By introducing a set of additional constraints, the subclass of navigation functions is defined. This class is dynamically sound in the sense that the actual mechanical system will inherit the essential aspects of the qualitative behavior of the gradient lines of the cost function. An existence proof is given by constructing a one parameter family of such functions; the parameter is used to guarantee the absence of local minima.>