This paper builds upon the well-established ML-based grasping technique, known as the Grasp-Rectangle (GR) method. The original GR method made two simplifying assumptions: it was designed exclusively for two-finger grippers, and it assumed that the gripper would approach objects solely from a top-down perspective on a horizontal surface. We have extended the GR method, for a multi-finger hand beyond these assumptions to (1) enable grasping from top and side views and (2) engage multiple points of contact, enhancing the algorithm’s overall performance. Our approach leverages geometric cues extracted from object images to calculate the optimal grasp pose and contact points, thereby enhancing grasp reliability. Extensive testing was conducted using a 7DOF robotic arm equipped with a 7-DOF 3-finger gripper. We achieved an accuracy of 98.6% on the Cornell Grasping Dataset with a processing time of 120 milliseconds. Furthermore, when assessing object grasping from both top and side perspectives, our algorithm delivered successful grasps at rates of 95% and 96%, respectively. These findings are rooted in a comprehensive series of tests performed across a diverse array of objects.

In the pursuit of object retrieval using an aerial manipulator, developing robust visual servoing techniques in the presence of projection and motion model uncertainties is paramount. This paper proposes a novel approach to conducting image-space planning within the controllable-space of the aerial manipulator. Our new strategy resolves the inherent challenge of adhering to a piecewise linear camera trajectory which is infeasible for an aerial manipulator due to the platform’s underactuation and presence of secondary tasks for visual servoing. Through this approach, we introduce center of gravity alignment and camera orientation potential fields without relying on specific degrees of freedom from the arm. Moreover, we introduce a new approach that utilizes an image-resolution scaling technique involving an adaptive virtual camera focal length, leading to a numerically well-conditioned image Jacobian. Our proposed framework maintains robustness to the uncertainty in the intrinsic parameters of the camera. We substantiate the efficacy of our methodology through experiments conducted in a realistic physics-based simulation environment.

Unmanned Aerial Manipulators (UAM) are gaining attention within the unmanned aerial systems research community. They can be used for aerial manipulation tasks such as object retrieval from confined and hard-to-reach spaces. The coupled dynamics between the arm and the base and also the limited flight time would require the development and implementation of optimal motion planning and robust flight control strategies. In this paper, we propose a novel integrated planning and control strategy for object retrieval. A new kinodynamic version of the Rapidly-exploring Random Tree (RRT*), called Lazy-Steering-RRT*, is developed for planning UAM’s motion from its start to a pre-grasp state, while keeping the motion of the arm to a minimum. This planning can be carried out on the fly by using Machine-Learning-based techniques to construct the edges in the search tree in a time-efficient way. This facilitates re-planning, as the environment is gradually sensed by limited-range sensors onboard. Once the UAM reaches the pre-grasp state at the end of the motion cycle, an RRT approach is then utilized, where motions of the base and the arm are coordinated for reaching and grasping the object. A novel partitioned control approach, composed of model predictive and PID controllers, is utilized for the UAM to track the planned trajectory. The overall motion planning and control algorithms have been implemented in simulation using Multibody Physics Engines and a number of representative simulation runs are presented. Our results show that the approach is effective in successfully executing the object retrieval task even in confined spaces.Note to Practitioners—This research was motivated by the problem of retrieving an object from a confined space such as that in a collapsed building using an unmanned aerial manipulator. Our approach has the following advantages over existing methods: a) Planning and re-planning can be carried out on the fly, b) No prior information about the environment is needed, c) High-frequency energy-optimal control of the UAM is carried out, and d) the planner and the controller are coupled. In this paper, we suggest some novel approaches on both planning and control aspects of the navigation and also on the integration of these two modules to provide a navigation package that meets all the requirements in the retrieval task. Furthermore, our algorithm is computationally-light, therefore, well suited for on the fly planning and control.

The past decade has amply demonstrated the remarkable functionality that can be realized by learning complex input/output relationships. Algorithmically, one of the most important and opaque relationships is that between a problem's structure and an effective solution method. Here, we quantitatively connect the structure of a planning problem to the performance of a given sampling-based motion planning (SBMP) algorithm. We demonstrate that the geometric relationships of motion planning problems can be well captured by graph neural networks (GNNs) to predict SBMP runtime. By using an algorithm portfolio we show that GNN predictions of runtime on particular problems can be leveraged to accelerate online motion planning in both navigation and manipulation tasks. Moreover, the problem-to-runtime map can be inverted to identify subproblems easier to solve by particular SBMPs. We provide a motivating example of how this knowledge may be used to improve integrated task and motion planning on simulated examples. These successes rely on the relational structure of GNNs to capture scalable generalization from low-dimensional navigation tasks to high degree-of-freedom manipulation tasks in 3d environments.

We present an integrated grasping system for a mobile manipulator to grasp an unknown object of interest (OI) in an unknown environment. The system autonomously scans its environment, models the OI, plans and executes a grasp, while taking into account base pose uncertainty. Due to inherent line of sight limitations in sensing, a single scan of the OI often does not reveal enough information to complete grasp analysis; as a result, our system autonomously builds a model of an object via multiple scans from different locations until a grasp can be performed. A volumetric next-best-view (NBV) algorithm is used to model an arbitrary object and terminates modeling when force closure for the gripper is satisfied. Two experiments are presented: i) modeling and registration error is reduced by selecting viewpoints with more scan overlap, and ii) model reconstruction and grasps are successfully achieved while experiencing base pose uncertainty.

During a robot to human object handover task, several intended or unintended events may occur with the object - it may be pulled, pushed, bumped or simply held - by the human receiver. We show that it is possible to differentiate between these events solely via tactile sensors. Training data from tactile sensors were recorded during interaction of human subjects with the object held by a 3-finger robotic hand. A Bag of Words approach was used to automatically extract effective features from the tactile data. A Support Vector Machine was used to distinguish between the four events with over 95 percent average accuracy.

We present a localization aware efficient sampling strategy for sampling-based motion planning under uncertainty that uses a new notion of localization ability of a sample. It puts more samples in regions where sensor data is able to achieve higher uncertainty reduction while maintaining adequate samples in regions where uncertainty reduction is poor. This leads to a less dense roadmap and hence results in significant time savings in the path search phase. We provide simulation results that show stochastic planners with our sampling strategy place less samples and find a well-localized path in shorter time with little compromise on the quality of path as compared to existing sampling techniques. We also show that a stochastic planner that uses our sampling strategy is probabilistically complete under some reasonable conditions on parameters.

We present a planning algorithm for a mobile robot in unknown indoor dynamic environments. The algorithm takes into account the robot's own dynamics and the dynamic obstacles’ future behavior in a safety hierarchy. It also uses an appropriate time horizon for planning and respects the timing constraints on various modules of the planner that are imposed by interleaving of planning and execution. We provide a formulation of this safety hierarchy in a single step via a composite costmap. The planning algorithm has been implemented in Player/Stage. We have run extensive simulations and compared the performance of the full safety hierarchy with various permutations of safety levels, as well as with some baseline algorithms over three different performance measures. We show that our safety hierarchy performs statistically significantly better across most performance measures and most simulation scenarios.

We incorporate a randomized kinodynamic path planning approach with image-based control of a robotic arm equipped with an in-hand camera. The proposed approach yields continuously differentiable camera trajectories by taking camera dynamics into account, while accounting for a critical set of image and physical constraints at the planning stage. The proposed planner explores the camera state space for permissible trajectories by iteratively extending a search tree in this space and simultaneously tracking these trajectories in the robot configuration space. The planned camera trajectories are projected into the image space to obtain desired feature trajectories which are then tracked using an image-based visual servoing scheme. We validate the effectiveness of the proposed framework in incorporating the aforementioned constraints through a number of visual servoing experiments on a six-degree-of-freedom robotic arm. We also provide empirical results that demonstrate its performance in the presence of uncertainties, and accordingly suggest additional planning strategies to increase robustness with respect to possible deviations from planned trajectories.

We address the problem of incorporating path planning with image-based control of a wheeled mobile manipulator (WMM) performing visually-guided tasks in complex environments. The WMM consists of a wheeled (non-holonomic) mobile platform and an on-board robotic arm equipped with a camera mounted at its end-effector. The visually-guided task is to move the WMM from an initial to a desired location while respecting image and physical constraints. We propose a kinodynamic planning approach that explores the camera state space for permissible trajectories by iteratively extending a search tree in this space and simultaneously tracking these trajectories in the WMM configuration space. We utilize weighted pseudo-inverse Jacobian solutions combined with a null space optimization technique to effectively coordinate the motion of the mobile platform and the arm. We also present the preliminary results obtained by executing the planned trajectories on a real WMM system via a decoupled control scheme where the on-board arm is servo controlled along the planned feature trajectories while the mobile platform is simultaneously controlled along its trajectory using a state feedback tracking method.

This video presents an autonomous 9-DOF mobile-manipulator system for 3D modeling of objects in situ. The system consists of a mobile manipulator - a powerbot mobile base with a six degrees of freedom (DOF) powercube arm mounted on it. The arm is equipped with a wrist mounted line-scan range sensor, and the powerbot also has a line scan range sensor mounted on it. The task is to autonomously build 3D model of an object in situ. The system assumes no knowledge of either the object or the rest of the workspace of the robot. The overall planner integrates two next best view (NBV) algorithms, one for modeling and the other for exploration, along with a sensor-based roadmap planner for the manipulator and costmap-based planner for the mobile base. We have implemented the system and this video show that system is able to autonomously build a 3D point cloud model of an object in an unknown environment.

In this paper we incorporate a randomized kinodynamic path planning approach with image-based control for a robotic arm equipped with an in-hand camera in a servoing task. The proposed approach yields C2-smooth camera trajectories by taking camera dynamics into account while accounting for a critical set of image and physical constraints. The proposed planner explores the camera state space (i.e., a space of camera poses and velocities) for permissible trajectories by iteratively extending a search tree in this space and simultaneously tracking these trajectories in the robot configuration space (i.e., joint space). The planned camera trajectories are then projected into the image space to obtain desired feature trajectories. In the execution stage an image-based visual servoing scheme is then adopted to track the feature trajectories. The effectiveness of the proposed approach has been experimentally demonstrated on a robotic arm with an in-hand camera executing servoing tasks in complex environments.

In this paper, we consider the problem where a point robot in a 2D or 3D environment equipped with an omnidirectional range sensor of finite range D is asked to cover a set of surface patches, while minimizing the sum of view cost, proportional to the number of viewpoints planned, and the travel cost, proportional to the length of path traveled. We call it the Metric View Planning Problem with Traveling Cost and Visibility Range or Metric TVPP in short. We present a complexity result for the problem, i.e., we show that the Metric TVPP cannot be approximated within O(log m) ratio by any polynomial algorithm, where m is the number of surface patches to cover. We then analyze a variant of an existing decoupled two-level algorithm of first solving the view planning problem to get an approximate solution, and then solving, again using an approximation algorithm, the Metric traveling salesman problem to connect the planned viewpoints. We then present performance bounds for this two-level decoupled algorithm, i.e., we show that it has an approximation ratio of O(log m). Thus, it asymptotically achieves the best approximation ratio one can hope for.

This paper studies a distributed path-planning problem: How can a sensor network help navigate a nontrial robot to its desired goal in a distributed manner? We consider the case where each sensor node is equipped with sophisticated sensors capable of giving a map for its sensing region. We propose a distributed sampling-based planning algorithm, where every sensor node creates a local roadmap in its locally sensed environment; these local roadmaps are “stitched” together by passing messages among nodes and forming a larger implicit roadmap without having a global representation. Based on the implicit roadmap, a feasible path is computed in a distributed manner, and the robot moves along the path by interacting with sensor nodes, each of which giving a portion of the path within the local environment of the node. Simulations show that the algorithm is able to solve the path-planning problem with low communication overhead.

This paper studies a distributed path planning problem: how can a sensor network help to navigate a robot to its desired goal in a distributed manner. We consider the case where each sensor node is equipped with sophisticated sensors capable of giving a map for its sensing region. We propose a distributed sampling based planning framework (Distributed PRM), where every sensor node creates a local roadmap in its locally-sensed environment; these local roadmaps are “stitched” together by passing messages among nodes and form a larger implicit roadmap without having a global representation. Based on the implicit roadmap, a feasible path is computed in a distributed manner, and the robot moves along the path by interacting with sensor nodes, each of which gives a portion of the path within the local environment of the node. Preliminary simulations show the proposed framework is able to solve path planning problem with low communication overhead.

We present an integrated and fully autonomous eye-in-hand system for 3D object modeling. The system hardware consists of a laser range sensor mounted on a six-DOF manipulator arm and the task is to autonomously build 3D model of an object in-situ, i.e., the object may not be moved and must be scanned in its original location. Our system assumes no knowledge of either the object or the rest of the workspace of the robot. The overall planner integrates a next best view (NBV) algorithm along with a sensor-based roadmap planner. Our NBV algorithm while considering the key constraints such as FOV, viewing angle, overlap and occlusion, efficiently searches the five-dimensional view space to determine the best modeling view configuration. The sensor-based roadmap planner determines a collision-free path, to move the manipulator so that the wrist mounted scanner is at the view configuration. If the desired view configurations are not collision free, or there is no free path to reach them, the planner explores the workspace such that facilitates the modeling. This is repeated until the entire object is scanned. We have implemented the system and our results show that system is able to autonomously build a 3D model of an object in an unknown environment.

We incorporate sampling-based global path planning with Visual Servoing (VS) for a robotic arm equipped with an in-hand camera. The path planning accounts for a number of constraints: 1) maintaining continuous visibility of the target within the camera's field of view, 2) avoiding visual occlusion of target features caused by the workspace obstacles, robot's body, or the target itself, 3) avoiding collision with physical obstacles or self collision, and 4) joint limits. Incorporating these constraints enhances the applicability of VS to significantly more complex environments/tasks, thereby making the resulting VS much more robust. The proposed planner explores the camera space, i.e. 3D Cartesian space, for permissible camera paths satisfying the aforementioned constraints by iteratively extending a search tree in camera space and simultaneously tracking these paths in the robot's joint space using a local planner. The planned camera path is then projected into the image space and tracked using an image-based visual servoing scheme. The validity and effectiveness of the proposed approach in accomplishing VS tasks in complex environments are demonstrated through a number of simulations on a 6-dof robot arm moving among obstacles.

While a network of autonomous mobile agents is capable of performing spatially distributed tasks, communication between agents imposes a class of constraints over the corresponding task. This paper proposes a distributed paradigm to deal with a critical communication constraint, connectedness constraint, where a group of mobile agents are required to remain connected while performing a task (e.g., formation control, consensus, etc.). The proposed method adaptively extracts communication backbone of the group, which is formed by a subset of agents, and thus partitions the group into backbone agents and non-backbone agents. The connectedness of the system is maintained at two levels: motion of backbone agents is controlled to maintain existing connections in the backbone; motion of non-backbone agents is determined via a leader-follower formation control method with backbone agents as the leaders. Key advantages of the proposed approach are that it can deal with arbitrary system topologies, it is a distributed method, it uses only two-hop neighbor information, and has low communication cost.

We address the motion planning problem for a manipulator system with base pose uncertainty, e.g., when the manipulator is mounted on a mobile base. Using a particle based representation for the uncertainty, we extend the PRM (probabilistic roadmap) approach to deal with this base uncertainty. Because of the uncertainty, a path for the manipulator is associated with a probability of being collision-free, which fundamentally changes the nature of the PRM's query phase. We plan for a shortest path such that the probability of the manipulator being collision-free is higher than a user defined threshold, were the manipulator to follow the path. The path query problem becomes a collision probability constrained shortest path problem (CP-CSPP), and is shown as NP-hard w.r.t. the number of the particles. We then present a lazy query algorithm, called Lazy-CPC-PRM (collision probability constrained LazyPRM), based on a k-shortest path algorithm in conjunction with a labeling algorithm. Lazy-CPC-PRM exploits a key insight that if a portion of a path considered by the algorithm is invalid (the probability of it being collision-free is less than a threshold) or is dominated by another sub-path, then all the longer paths containing this portion can not be the solution path. This leads to significant efficiency gains in practice. Although, worst case complexity is exponential in the number of particles, we empirically show the effectiveness of our query algorithm with 30 particles for a simulated 3-dof manipulator mounted on a mobile base.

In this paper, we propose a distributed path planning method for robot navigation amidst a wireless sensor network. Our method uses communication backbone as a roadmap. In building and maintaining the roadmap, it takes path safety and network longevity into account, and therefore the roadmap adapts to dynamic dangers and evolves over time to increase network longevity. To find a safe path, a navigation field is propagated over the roadmap and the shortest path is computed. Simulation results show that as compared to existing methods our method finds a safe path with less communication cost, and in dense networks it generates smaller roadmaps. We also provide theoretical bounds on the path quality in terms of path length.

We address the motion planning (MP) subproblem that arises in a robotic exploration and mapping task. We consider sensing, localization and mapping uncertainties in the motion planning subproblem. The robot is holonomic with known size and shape, and is equipped with a laser range sensor. We use a rapidly exploring randomized tree (RRT) in conjunction with a simulated particle based Simultaneous Localization and Mapping (SLAM) algorithm to expand the tree. The simulated SLAM explicitly accounts for sensor, localization and mapping uncertainty in the planning stage. Moreover, the RRT itself is represented in the augmented configuration space where an extra dimension of uncertainty is used. The collision likelihood along a planned path is explicitly computed and is used to select a planned path. Preliminary simulations show the effectiveness and benefits of our integrated approach.

We present a novel approach for real-time motion planning of multiple formations in virtual environments with dynamic obstacles. Our algorithm is based on the continuum model for crowd simulation and our flexible virtual structure approach for formation control in virtual environments. Simulations created with our algorithm run at interactive rates in quite complex environments. In addition, each formation can be deformed in real-time and the deformation is triggered either automatically (e.g., when the formationpsilas path is blocked by dynamic obstacles) or manually. Via simulations, we show that we can plan at least four formations, each with tens of agents, in real-time on a PC.

We proposed in a previous paper (2006) a hybrid two-layered approach for motion planning of multiple agents in static virtual environments, consisting of open spaces connected by multiple narrow passages. The discrete generalized Voronoi diagram (GVD) of the environment is used to identify narrow passages, and plan the global path of each agent independently of other agents' global paths. As each agent moves along its global path, the agent's path is locally modified using the hybrid technique of combining steering behaviors with Coordination Graphs (CG), where coordination graphs are used for deadlock avoidance in the narrow passages. The planner in the previous paper was single threaded, and it was able to plan the motions of 30 agents moving around in a simple virtual environment with 3 narrow passages. If more agents are moving in a more complex virtual environment (i.e., with more narrow passages), we may not be able to construct and process all the coordination graphs in real-time. In this paper, we parallelize the single threaded planner in a supervisor-worker paradigm with Unix processes who communicate with each other using System V interprocess communication (IPC) mechanism. We show that significant, scalable speedups are obtained by constructing and processing coordination graphs in parallel on a symmetric multiprocessing (SMP) system.

In this paper, we introduce the problem of view planning with combined view and traveling cost, denoted by traveling VPP. It refers to planning a sequence of sensing actions with minimum total cost by a robot-sensor system to completely inspect the surfaces of objects in a known workspace. The cost to minimize is a combination of the view cost, proportional to the number of viewpoints planned, and the traveling cost for the robot to realize them. First, we formulate traveling VPP as an integer linear program (ILP). The focus of this paper is to design an approximation algorithm that guarantees worst-case performance (w.r.t. the optimal solution cost). We propose a linear program based rounding algorithm that achieves an approximation ratio of the order of view frequency, defined to be the maximum number of viewpoints that see a single surface patch of the object. Together with the result we showed (2006), the best approximation ratio for Traveling VPP is either the order of view frequency or a poly-log function of the input size, whichever is smaller. Motivated from the robot motion planning techniques, where the graph built for robot traveling is a tree, we then consider the corresponding special case of traveling VPP, and give a polynomial sized LP formulation. We conclude with a discussion of realistic issues and constraints towards implementing our algorithm on real robot-sensor systems.

In this paper, we consider the problem where a point robot in a 2D or 3D environment equipped with an omnidirectional range sensor of finite range D is asked to inspect a set of surface patches, while minimizing the sum of view cost, proportional to the number of viewpoints planned, and the travel cost, proportional to the length of path traveled. We call it the metric view planning problem with traveling cost and visibility range or metric TVPP in short. Via an L-reduction from the set covering problem to a two-dimensional metric TVPP, we show that the metric TVPP cannot be approximated within O(log m) ratio by any polynomial algorithm, where m is the number of surface patches to cover. We then analyze the natural two-level algorithm, presented by Danner and Kavraki (2002), of solving first the view planning problem to get an approximate solution, and then solving, again using an approximation algorithm, the Metric traveling salesman problem to connect the planned viewpoints. We show this greedy algorithm has the approximation ratio of O(log m). Thus, it asymptotically achieves the best approximation ratio one can hope for.

The concept of C-space entropy for sensor-based exploration and view planning for general robot-sensor systems has been introduced in [?], [?], [?], [?]. The robot plans the next sensing action (also called the next best view) to maximize the expected C-space entropy reduction, (known as Maximal expected Entropy Reduction, or MER). It gives priority to those areas that increase the maneuverable space around the robot, taking into account its physical size and shape, thereby facilitating reachability for further views. However, previous work had assumed a Poisson point process model for obstacle distribution in the physical space, a simplifying assumption. In this paper we derive an expression for MER criterion assuming an occupancy grid map, a commonly used representation for workspace representation in much of the mobile robot community. This model is easily obtained from typical range sensors such as laser range finders, stereo vision, etc., and furthermore, we can incorporate occlusion constraints and their effect in the MER formulation, making it more realistic. Simulations show that even for holonomic mobile robots with relatively simple geometric shapes (such as a rectangle), the MER criterion yields improvement in exploration efficiency (number of views needed to explore the C-space) over physical space based criteria.

We consider the problem of planning collision-free paths for a redundant robot manipulator whose end-effector must travel along a specified path. A probabilistic method has been proposed for the problem, which does not allow self-motions of the robot as it moves along the end-effector path. In this paper, we propose an enhancement, which allows such self-motions. This is primarily accomplished by explicitly representing self-motions for a certain pose as a self-motion graph, which is explored with probabilistic techniques for closed-chain robots. Computer simulations show that this enhancement improves performance in most cases. Depending on the limits set on the run-time (always needed in practice for probabilistic sampling methods), the planner with self-motion enhancement will find a path where the original algorithm without self-motion may not

We proposed in a previous paper a hybrid technique, combining local steering behaviors and coordination graphs (CG), that allows real-time motion planning of multiple agents in a narrow passage. This hybrid technique not only avoids deadlocks, but also exhibits other interesting behaviors such as leader following, even though they are not explicitly coded in the algorithm. In this paper, we build upon the earlier result, and propose a two-layered approach to motion planning of multiple agents in virtual environments, consisting of open spaces connected by multiple narrow passages. The discrete generalized Voronoi diagram (GVD) of the static environment is used to identify all narrow passages automatically. The global path of each agent is also planned using the GVD. As each agent moves along its global path, it is locally modified using the hybrid technique combining steering behaviors with coordination graphs. Experimental results show that the resulting planner is able to plan motions of 30 agents in a virtual environment with three narrow passages in real-time, and the pre-processing phase of our approach is extremely fast. Since all planning is done in real-time, the approach allows an agent to change its final destination at runtime

For sensor-based robot motion planning, view planning problem refers to planning the next sensing action to further facilitate the motion planning task. In Y. Yu and K. Gupta (2004), C-space entropy was introduced as a measure of knowledge of robot configuration space, or C-space. The robot plans the next sensing action to maximally reduce the expected C-space entropy, also called the maximal expected entropy reduction, or MER criterion. It was shown that MER criterion resulted in much more efficient C-space exploration performance than physical space based view planning criteria, such as to maximize unknown physical volume in each view. From a C-space perspective, MER criterion consists of two important aspects: sensing actions are evaluated in C-space (geometric aspect); these effects are evaluated in an information theoretical sense (stochastic aspect). In this paper, we investigate how much of this better performance is attributable to the paradigmatic shift to evaluating the sensor action in C-space, i.e., the pure geometric component of MER, and how much is attributable to the stochastic aspect of MER. We propose C-space based pure geometric criteria (which are essentially geometric aspect of MER) for view planning and compare them with the MER criterion. We empirically show that a great deal of efficiency is attributable to the pure geometric aspect; however, we also show that the stochastic aspect, despite being based on simple assumptions, result in moderately more efficient C-space exploration over the pure geometric component of MER. We outline explanations for our findings

A new hybrid motion planning technique based on Harmonic Functions (HF) and Probabilistic Roadmaps (PRM) is presented. The proposed approach consists of incrementally building a Probabilistic Roadmap using information obtained about the workspace topology through the Fluid Dynamic (FD) paradigm based on HFs. The crux of our approach is to identify narrow passages using FD paradigm and pass the information obtained over to a PRM method to build a roadmap to capture the connectivity of free configuration space (C-space) especially in narrow regions. As an extension to our recent works on using Harmonic Function-based Probabilistic Roadmaps (HFPRM) for robotic navigation [1], we propose an Incremental HFPRM (IHFPRM) technique which is more general and can be applied to virtually any type of robot. Simulation results presented in this paper show that the combination of the HF and the PRM works better than each individual in terms of finding a collision free path in environments where narrow passages exist. This technique can be extended to the sensor-based motion planning of robots (mobile and/or articulated) which is the long-term objective in carrying out this research.

Motion planning of multiple mobile agents in virtual environments is a very challenging problem, especially if one wants to plan the motions of these agents in real-time. We propose a two layered approach to plan motions of multiple mobile agents in real-time. The mobile agents are moving in a 2-dimensional static environment with open spaces connected to each other by narrow corridors. The global path of each agent is computed by a decoupled planner during the preprocessing process with minimum delay. Each agent’s local path is generated in real-time by combining steering behaviors and a new, principled and efficient AI technique for decision making and planning cooperative multi-agent dynamic systems, Coordination Graph (CG). With CG, we can not only avoid deadlocks in narrow corridors, but also achieve more complicated behavior such as leader-and-followers behavior. We show, via some preliminary examples, real-time performance of our approach, for instance, several robots avoiding deadlocks and successfully navigating a corridor.

We consider the view planning problem, also called, next best view (NBV) problem for sensor based exploration for general robot-sensor systems, where a range scanner is mounted on a robot with non-trivial kinematics, e.g., an eye-in-hand system. Earlier approaches to NBV had considered purely work-space (we also use the term physical-space) based criteria, such as select the view that maximizes the unknown physical-space volume. While this works well for mobile robots (often modeled as point or circle, thereby having trivial geometry and kinematics), it ignores a critical aspect, i.e., to give priority to exploring "manoeuvrable" space around the robot so that it can move to better viewing configurations. Proposed C-space based view planning criteria address this problem. However, C-space criteria (assuming the robot has enough manoeuvrable space) may sacrifice efficiency in work-space volume coverage. For inspection or environment modeling tasks, efficient workspace volume coverage is important. In this paper, we propose an adaptive algorithm that biases the search toward C-space or toward work-space, as needed. We call it adaptive viewpoint candidates entropy (VCE) criterion. Results with different simulated scenes show the effectiveness of this criterion in efficient (in that it needs less scans) exploration of the workspace.

In this paper, we address the path planning problem with general end-effector constraints (PPGEC) for robot manipulators. Two approaches are proposed. The first approach is adapted from an existing randomized gradient descent (RGD) method for closed-chain robots. The second approach is radically different. We call it ATACE alternate task-space and configuration-space exploration. Unlike the first approach which searches purely in C-space, ATACE works in both task space and C-space. It explores the task space for end-effector paths satisfying given constraints, and utilizes trajectory tracking technique(s) as a local planner(s) to track these paths in the configuration space. We have implemented both approaches and compare their relative performances in different scenarios. ATACE outperforms RGD in majority (but not all) of the scenarios. We outline intuitive explanations for the relative performances of these two approaches.

In this article, we revisit one of the key issues, i.e., node connection, in probabilistic roadmap (PRM) planners, which have been shown effective in high dimensional motion planning problems. We propose a new method of neighborhood selection strategy based on certain empirically observed properties of Delaunay triangulation of a random uniformly distributed point set. Our method allows a node in the network to have neighbors that are close to itself in the sense of Delaunay neighborhood. The algorithm introduced in this article is easy to implement and we show the boost in performance with the idea proposed in some preliminary experiments.

The concept of C-space entropy as a measure of knowledge of C-space for sensor-based path planning and exploration for general robot-sensor systems was introduced in Yu, Y. and Gupta, K. (2000). The robot plans the next sensing action to maximally reduce the expected C-space entropy, also called the maximal expected entropy reduction, or MER criterion. The expected C-space entropy computation, however, made an idealized assumption. The sensor was assumed to measure exact data, i.e., it was not subject to noise. In this paper we extend this approach by using a real noisy sensor model. Sensing actions can then be compared on the basis of their uncertainty models. This offers the ability for using more than one principle sensor (multisensory exploration), because sensor readings can be weighted by evaluating the expected measurement quality. Additionally, it makes robot motion planning viable for tasks such as object surface inspection, which require the robot to come very close to the obstacles to achieve high sensing accuracy.

We have recently introduced the concept of C-space entropy as a measure of knowledge of C-space for sensor-based path planning and exploration for general robot-sensor systems. The robot plans the next sensing action to maximally reduce the expected C-space entropy, also called the maximal expected entropy reduction, or MER criterion. The expected C-space entropy computation, however, made two idealized assumptions. The first was that the sensor field of view (FOV) is a point; and the second was that no occlusion (or visibility) constraints are taken into account, i.e., as if the obstacles are transparent. We extend the expected C-space entropy formulation where these two assumptions are relaxed, and consider a generic range sensor with non-zero volume FOV and occlusion constraints, thereby modelling a real range sensor. Planar simulations show that: (1) MER criterion results in significantly more efficient exploration than the naive physical space based criterion (such as maximize the unknown physical space volume), and (2) the new formulation with non-zero volume FOV results in further improvement over the point FOV based MER formulation. Preliminary experiments with the SFU eye-in-hand system, a PUMA 560 equipped with a wrist mounted range scanner corroborate the simulation results, however, for lack of space they are not reported here.

This paper deals with sensor-based path planning and exploration for robots (with non-trivial geometry and kinematics, such as a manipulator arm) moving in unknown environments. The manipulator (with many degrees of freedom) is assumed to be equipped with two sensing modalities: (i) a large number of proximity sensors mounted on its body (the "skin" sensor) and (ii) a range sensor mounted on its wrist (an "eye" sensor). The task for the robot is to move around and explore its (initially) unknown environment while avoiding collisions with obstacles that are (initially) unknown to the robot. We present a sensor-based planning algorithm that utilizes information from these two drastically different sensing modalities, the "eye" and the "skin". Planar simulations show that combining use of eye and skin sensors leads to more efficient and more extensive exploration than with eye sensing modality alone.

This paper addresses a general class of problems for sensor-based path planning and exploration for robots moving in unknown environments. The robot is assumed to be equipped with a large number of proximity sensors mounted on its body (a "skin" sensor). Robot's own motion is used to sense the free space, analogous to a blind person "groping and exploring" using his sense of touch. This sensed free space can be memorized and used to further plan the robot's motion. Using this key idea, we propose a general framework for such skin sensor based motion planning that is valid for robots with large degrees of freedom. The specific motion-planning algorithm developed uses a variant of the probabilistic roadmap method. A novel "metric" based on the notion of C-zone map for robot's movement that results in efficient exploration of configuration space is proposed and implemented. Planar simulations demonstrate our results.

The concept of C-space entropy was recently introduced by the authors (2000, 2001), as a measure of knowledge of C-space for sensor-based path planning and exploration for general robot-sensor systems. The robot plans the next sensing action to maximally reduce the expected C-space entropy, also called the maximal expected entropy reduction, or MER criterion. The expected C-space entropy computation, however, made two idealized assumptions. The first was that the sensor field of view (FOV) is a point; and the second was that no visibility (or occlusion) constraints are taken into account, i.e., as if the obstacles are transparent. We extend the expected C-space entropy formulation where the sensor FOV is a beam and furthermore, it is subject to visibility constraints, as is the case with real range sensors. Planar simulations show that this new formulation results in more efficient exploration.

We formally pose and explore some novel issues that arise for eye-sensor based motion planning for robots with non-trivial geometry/kinematics. The key issue is that while the sensor senses in physical space, the planning takes place in configuration space, and the two spaces are distinctly different for robots with nontrivial geometry/kinematics. This lends to some very interesting, fundamental yet novel issues. In particular, we introduce several novel notions: notion of s-reachability, notion of s-completeness that characterizes completeness for sensor-based planning algorithms, notion of explorability of configuration space, and notion of observability of physical space. We give sufficient conditions for a (discrete) eye-sensor based planner to be s-complete.

We consider the view planning problem where the sensor, a range scanner, is mounted on a robot mechanism with non-trivial geometry and kinematics. The robot+sensor system is required to explore the environment (obstacle/free space). We present a novel information theoretical approach in which the sensing action is viewed as reducing ignorance of the planning space, the C-space of the robot. The concept of C-space entropy is introduced as a measure of this ignorance. The next view in the planning process is determined by maximizing the expected reduction of C-space entropy, called maximal entropy reduction (MER) criterion. A computational tool to implement MER is the notion of information gain density function. Experimental results with a real PUMA robot with a wrist-mounted range scanner and a simulated robot show the effectiveness of the MER criterion in efficient exploration of environments for motion planning problems.

Jung and Gupta reported (1996) a representation, called octree distance map (ODM), for efficient collision detection in static environments. ODM captured partial distance information in a hierarchical manner and traded some memory (2 bytes per white node) for speed gains (as compared to an octree) in collision detection. In this paper, we propose a much more complete and systematic hierarchical representation for distance maps, the extended octree distance map (EODM). Like ODM, it utilizes an octree as the base representation. Along the perimeter of each white node in the octree, it stores a distance function that represents the distance of each boundary point of the white node to the obstacle closest to that point. As a result, EODM is more memory intensive than an ODM (and an octree), however, it would significantly decrease the collision detection time compared to either a conventional octree or the ODM. EODM is computed once and then repeatedly used for collision detection queries. We present algorithms for creating the EODM and use it for collision detection. Our preliminary experiments in 2D show that while EODM requires about three to five times more memory than an octree and four to five times extra memory than an ODM, it speeds up collision detection by a factor of three to six compared to an octree and by a factor of three to four as compared to an ODM.

We propose a mode-sequential task sharing-for co-operating robot manipulators carrying out a pick-and-place task sharing in a common workspace. As the name implies, in this mode, each individual robot completes part of the same task. The first manipulator picks up the part(s) and directly passes it over to the second manipulator (like a baton being passed from one runner to the other in a relay race), which completes the task by placing the part at its desired goal location. The point at which the transition, i.e., passing over the part, occurs is the rendezvous point. We analyse this approach to minimize the total task time subject to dynamic constraints of the robots. A key step is to determine the optimal rendezvous point (ORP) that results in the optimal task time. We present an algorithm to determine the ORP and show that our approach results in a speed up by a factor of more than two over the conventional single manipulator case.

We propose a novel and global algorithm to solving the point-to-point inverse kinematics problem for redundant manipulators. Given an initial configuration of the robot, the problem is to find a reachable (path-connected) configuration that corresponds to a desired position and orientation of the end-effector. Our approach was inspired by recent motion planning research and explicitly takes into account constraints due to joint limits, self-collisions and static obstacles in the environment. The problem is posed as an optimization problem. Central to solving this optimization problem is a novel representation, the kinematic roadmap of a manipulator. The kinematic roadmap captures the connectivity of the connected component of the free configuration space of the manipulator in a finite graph like structure. The point-to-point inverse kinematics problem is then solved (with a local planner) using this roadmap. In this paper, we provide completeness results for our algorithm.

This paper examines sensor-based orientation of polygonal shaped objects using a 6-axis force/torque sensor which is used to supply rotation and force information during the orientation process. Sensor-based algorithms utilizing rotation sense and force information are presented which offer improvements over the best sensorless orienting techniques, and are shown to be better than previous sensor-based techniques for parts with the same diameter value for every stable edge. Plans generated by our algorithm were tested and verified using a unique conveyor/robotic car testbed.

We present a real implemented "eye-in-hand" test-bed system for sensor-based collision-free motion planning for articulated robot arms. The system consists of a PUMA 560 with a triangulation based area-scan laser range finder (the eye) mounted on its wrist. The framework for our planning approach was presented in Yu and Gupta (1998). It is inspired by motion planning research and incrementally builds a roadmap that represents the connectivity of the free configuration space, as it senses the physical environment. We present some experimental results with our sensor-based planner running on this real test-bed. The robot is started in completely unknown and cluttered environments. Typically, the planner is able to reach (planning as it senses) the goal configuration in about 7-25 scans (depending on the scene complexity), while avoiding collisions with the obstacles throughout.

This paper proposes a novel and global approach to solving the point-to-point inverse kinematics problem for highly redundant manipulators. Given an initial configuration of the robot, the problem is to find a reachable configuration that corresponds to a desired position and orientation of the end-effector. Central to our approach is the novel notion of kinematic roadmap for a manipulator. The kinematic roadmap captures the connectivity of the connected component of the free configuration space of the manipulator in a finite graph like structure. The point-to-point inverse kinematics problem is then solved using this roadmap. We provide completeness results for our algorithm. Our implementation of SEARCH is an efficient closed form solution, albeit local, to inverse kinematics that exploits the serial kinematic structure of serial manipulator arms. Initial experiments with a 7-DOF manipulator have been extremely successful.

We address the global motion planning aspects of dexterous manipulation by a multifingered robotic hand. The specific task we address is: starting from a given initial grasp of a three-dimensional (3-D) object O, find feasible quasistatic trajectories (rolling/sliding motions and forces) for the fingertips to move O to a desired final configuration. We call this the reconfiguration problem. Our planner is based on a two-level algorithm combining a graph search on the configuration space of the object and a local planner that solves for instantaneous quasistatic motions of the entire manipulation system. The planner is used for simulating several complex reconfiguration tasks for smooth objects demonstrating the promise of our approach.

This paper examines a sensor based technique for determining the orientation of a polygon on a horizontal surface by pushing with a force/torque sensor equipped fence. Using an exploratory process, the resulting algorithm can determine the orientation, to symmetry, of the sub-class of polygons that are stable on all edges, in at most two pushes.

We present an algorithm for direct octree construction from range images. It uses a key property of most range sensors that all the voxels on sensed object surfaces are "visible" from the sensor. This enables us to define a projection map for range images. The projection map is used for efficiently checking if a given voxel is in the free region. Furthermore, this key property also reduces the number of faces to be checked for the nodes when constructing octrees. The algorithm is efficient in both memory space and run time, and is useful for sensor-based articulated robot motion planning, which is the main motivation for this work.

We propose an algorithm for sensorless reorientation of 3D convex polyhedral parts through a sequence of step devices. Part is assumed to arrive in an arbitrary orientation and is being translated forward (e.g., on a conveyor belt) at slow speed. After precomputing, our algorithm produces a sequence of O(n) distinct steps, where n is the number of faces in the polyhedral part. As the part passes (drops) through the steps, it successively changes orientation. At the output end, the part will be oriented (for most initial orientations) to a pose such that its center-of-mass is the lowest possible.

This paper describes a global motion planner for dextrous manipulation of 3D objects by a multifingered robotic hand. We focus on the reconfiguration problem: find a feasible quasi-static trajectory (motions and contact forces) that moves a hand-object system from an initial grasp to a final desired configuration of the object. The planner is designed as a two-level process: a global level that expands a tree of sub-goals in the configuration space of the object, and a local level that searches for feasible quasi-static trajectories of the entire manipulation system between adjacent sub-goals. A key feature of the planner is that it exploits the redundancy of the system by using, in a complementary way, different canonical manipulation modes and tackles the high dimensionality of the solution space (configuration and control spaces) by making use, instantaneously, of a random search over it. The planner is applied in simulation for achieving several nontrivial reconfiguration tasks for (piecewise-) smooth convex objects demonstrating the promise of our approach.

This paper re-examines a part orienting technique that orients polygonal shaped parts with a series of fences suspended above a conveyor belt. We examine the effect of uncertainty in the coefficient of friction as well as the typical size of the final assembly. The search technique in the original work although resolution complete, was inefficient, so we offer a heuristic search method that offers good performance. Several fence sequences generated by our algorithm were tested on real polygonal objects.

We present a general framework for sensor-based motion planning for an articulated robot arm with many degrees of freedom. We assume a sensor that measures distances in physical space (a range sensor). Inspired by recent work in classical motion planning, the crux of our framework is to represent the connectivity of the configuration space (C-space) with a graph structure, the roadmap. This roadmap is then incrementally built. We have performed some simulations that show the promise of our approach.

In this paper, we describe a framework for predicting future positions and orientation of moving obstacles in a time-varying environment using autoregressive model (ARM) with conditional maximum likelihood estimate of the model parameters. No constraints are placed on the obstacles motion. The proposed algorithm can be used in a variety of applications, one of which is robot motion planning in time varying environments.

We propose a new approach to solving the point-to-point inverse kinematics problem for highly redundant manipulators. It is inspired by recent motion planning research and explicitly takes into account constraints due to joint limits and self-collisions. Central to our approach is the novel notion of kinematic roadmap for a manipulator. The kinematic roadmap captures the connectivity of the configuration space of a manipulator in a finite graph like structure. The standard formulation of inverse kinematics problem is then solved using this roadmap. Our current implementation, based on Ariadne's clew algorithm, is composed of two sub-algorithms: EXPLORE, a simple algorithm that builds the kinematic roadmap by placing landmarks in the configuration space; and SEARCH, a local planner that uses this roadmap to reach the desired end-effector configuration. Our implementation of SEARCH is an extremely efficient closed form solution, albeit local, to inverse kinematics that exploits the serial kinematic structure of serial manipulator arms. Initial experiments with a 7-DOF manipulator have been extremely successful.

We propose an approach for investigating the shape properties of objects with curved surfaces using tactile sensing by a dexterous robot hand. Our proposed exploratory procedure (EP) uses multiple fingers to slide along a surface while sensing contact points and surface normals. Our approach incorporates the surface normal information into a B-spline surface fit of the data gathered from this EP. This additional surface normal information was found to improve the approximation of the surface. The shape properties of this B-spline surface are analyzed to recognize the shape of the object. A confidence estimate of the estimated shape is also calculated.

We address the global motion planning aspects of dextrous manipulation by a multifingered robotic hand. The specific task we address is: starting from a given initial grasp of a 3D object O, find feasible quasi-static trajectories (rolling/sliding motions and forces) for the fingertips to move O to a desired final configuration. We call this the re-configuration problem. Our planner is based on a two-level algorithm combining a graph search on the configuration space of the object and a local planner that solves for instantaneous quasi-static motions of the entire manipulation system. The planner is used for several complex re-configuration tasks-for polyhedral and smooth objects. These experiments show the practicality of our approach.

This paper addresses the motion planning problem for dextrous manipulation by an artificial multifingered hand. We focus on the task of re-orienting polyhedral objects and present a practical motion planner for achieving quasistatic manipulations by a four-fingered hand. The planner makes use of a simple manipulation strategy in which a single finger is moved and the other three are fixed. We describe how this scenario is exploited for reducing the space of trajectory solutions and used within a two-level incremental process to search for global re-orientation motions. The planner has been implemented and used for achieving several complex re-orientation tasks with frictional and frictionless contacts that show the practicality of our approach.

Proposes an approach-"Blind Man's" approach-to shape description in which tactile information is sensed from the fingertips of a dexterous hand. Using this contact information, we investigate two complementary methods for curvature estimation. The first method is based on rolling one finger to estimate curvature at a point on the surface. We use Montana's equations for estimating curvature at a point using simulations and analyze the sensitivity of the approach to noise. The second method uses multiple fingers to slide along a surface while sensing contact points and surface normals. We present a method to extract the shape properties of a patch obtained by fitting a B-spline surface to this multi-fingered sweep across the surface of the object. The method enables us to extract higher level shape information based on the curvature properties of patch.

In this paper, we propose a novel hierarchical representation for discretized distance maps commonly used in robotics for path planning and collision detection applications. We augment the well-known octree structure for representing distance maps in a hierarchical manner. Our augmented octree based representation drastically reduces the expensive memory requirement compared to voxel-based distance maps while providing substantially better collision-detection performance than by using unaugmented octrees. Although our main motivation has been collision detection in robotics, similar octree distance maps will have wide applications in many other areas including machine vision, computer graphics and so on.

In this paper, we study the following motion planning problem for dexterous manipulation: devise a global plan that a dexterous hand can use to actively manipulate an object from a given initial orientation to a desired final orientation. We propose an approach that uses a local planner to search the orientation state space (S0(3)/spl times//spl Omega/) of the object by placing random landmarks in it. The local planner used in our implementation is a trajectory generator on SO(3) along with the finger tracking strategy proposed by Rus (1992). We report initial experiments that indicate the promise of our approach.

Gupta (1990) presented a sequential framework to develop practical motion planners for manipulator arms with many degrees of freedom. The crux of this framework is to sequentially plan the motion of each link, starting from the base link, thereby solving n single-link problems (each of which is solved as a 2-D planning problem) instead of one n-dimensional problem. The solution of each single-link problem is based on the search of a visibility graph (Vgraph) constructed from a polygonal representation of forbidden regions as seen in successive 2-D t/sub i//spl times/q/sub i/ spaces. In this paper, the authors present a backtracking mechanism within this sequential framework to make it more effective in planning collision-free paths in cluttered situations. The essence of the backtracking mechanism is based on an edge deletion mechanism that modifies the Vgraph in t/sub i-1//spl times/q/sub i-1/ space if no path is found in t/sub i//spl times/q/sub i/ space. The level of backtracking, b, i.e., the number of links the planner backtracks is an adjustable parameter that can trade off computational speed versus the relative completeness of the planner. Incorporating such a backtracking mechanism has significantly improved the performance of planners developed within this framework. The authors present extensive experimental results with up to eight degree-of-freedom manipulators in quite cluttered 3-D environments. Although the planner is not complete, the authors' empirical results are very encouraging. These empirical results indicate that b can be chosen small-typically 2 or 3-in over 90% of the cases. These results show that the authors' approach would be useful in practice.

In this paper, we present a novel approach within the sequential framework to develop practical motion planners for many degrees of freedom (DOF) arms. In this approach, each of the sub-problem is solved by using numerical potential fields defined over bitmap-based representations of the 2-dimensional sub-spaces. Furthermore, an efficient backtracking mechanism based on a novel notion of virtual forbidden regions in these 2-dimensional subspaces is presented. This novel approach leads to much more efficient and robust motion planners than a previously reported visibility graph (in the 2-dimensional subspaces) based implementation. We have conducted extensive experiments for planar arms with up to 8-DOF among randomly placed obstacles. Although it is not complete, the planner never failed for the examples in hundreds of simulations, and very small backtracking levels were needed. We have implemented the planner for 3-dimensional workspaces and an illustrative example for a 7-DOF manipulator shows the promise of our approach.>

A sequential framework that allows planners for manipulator arms with many degrees of freedom to be developed is addressed. The essence of this framework is to exploit the serial structure of manipulator arms and decompose the n-dimensional problem of planning collision-free motions for an n-link manipulator into a sequency of smaller m-dimensional subproblems, each of which corresponds to planning the motion of a subgroup of m-1 links. Extensive experimental results within the sequential framework are presented for a variety of manipulators. A main goal of these simulations (1) to show the effectiveness of the sequential approach with the backtracking mechanism, and (2) to quantify the improvement of the backtracking mechanism and the trade-off between the number of backtrackings and the execution time of the planner. The experiments show that the sequential framework with the backtracking mechanism is quite efficient for manipulator arms with many degrees of freedom.

Motion planners for highly redundant arms are discussed. The crux of the approach is to plan the motion of each link, starting from the base link, sequentially, thereby solving n single-link problems. The authors present a backtracking mechanism for the motion planner to make it more effective in planning collision-free paths in cluttered situations. The level of backtracking k is an adjustable parameter. The time complexity of the algorithm is exponential in k, but is polynomial for a given k. In k, the level of backtracking, a user-determined parameter is provided, that can trade off computational speed versus the completeness of the planner. Experiments were conducted with up to ten degree-of-freedom manipulators in quite cluttered environments, and the planner successfully generated a collision-free path in the order of a few minutes.>

A sequential strategy is presented for planning collision-free motions for a manipulator arm. The basic idea behind the approach is to plan the motion of each link successively, starting from the base link. Suppose that the motion of links to link i (including link i) has been planned. This already determines the path of one end (the proximal end) of link i+1. The motion of link i+1 is now planned along this path by controlling the degree of freedom associated with it, which is a 2-D motion planning problem. This strategy results in one 1-D (the first link is degenerate) and (n-1) 2-D planning problems. The 2-D motion planning problem is to plan the motion of a single link as one end of this link moves along a fixed path. This problem is posed in t* theta space, where t is the parameter along the path and theta the angle to be planned. The obstacles in t* theta space are approximated by discretizing t. Fast and efficient techniques are then used to plan a path in t* theta space. Thus, the strategy leads to fast and efficient algorithms and is especially suited for highly redundant arms.>

A novel sequential strategy is presented to plan collision-free motions for a manipulator arm (such as PUMA 260). The basic idea behind the approach is to plan the motion of each link successively, starting from the base link. Suppose that the motion of links until link i (including link i) has been planned. This already determines the path of one end (the proximal end) of link i+1. The motion of link i+1 is now planned along this path by controlling the degree of freedom associated with it-a two-dimensional motion planning problem. This strategy results in one one-dimensional (the first link is degenerate) and n-1 two-dimensional problems instead of one n-dimensional problem for an n-link manipulator arm. In most reasonable cases, the strategy should quickly find a path. At the very least, it will form a front end to a more complete planner.>