Motion Planning in Environments with Low Obstacle Density

We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for such environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free configuration space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same size. The approach leads to nearly optimal O(n \log n) motion planning algorithms for free-flying robots with any fixed number of degrees of freedom in workspaces with low obstacle density. Received October 17, 1995, and in revised form July 8, 1997, and February 23, 1998.     

Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

Topological Complexity of Motion Planning

Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Topological Complexity of Motion Planning

   Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Connectivity graphs on two-dimensional surfaces and their application in robotics

The problem of robot motion planning in an environment with obstacles can often be reduced to the study of connectivity of the robot's free configuration space. In turn, space connectivity can be analysed via the corresponding connectivity graph. For two-degree-of-freedom robots, the free configuration space presents a two-dimensional (2D) surface—a compact subspace of a 2D orientable compact manifold. This paper addresses the following abstract problem: given a compact 2D surface bounded by simple closed curves and lying in an orientable 2D manifold (a sphere, a torus, etc.) and given two points in the subspace, suggest a systematic way of defining the connectivity graph in the subspace, based on its topological properties. The use of space topology results in powerful, from the robotics standpoint, provable algorithms capable of on-line motion planning in an environment with unknown obstacles of arbitrary shapes. This makes the method distinct from other techniques, which require complete information, algebraic representation of space geometry, and off-line computation.     

On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles

This paper, a fifth in a series, solves some additional 3-D special cases of the ?piano movers”? problem, which arises in robotics. The main problem solved in this paper is that of planning the motion of a rod moving amidst polyhedral obstacles. We present polynomial-time motion-planning algorithms for this case, using the connectivity-graph technique described in the preceding papers. We also study certain more general polyhedral problems, which arise in the motion planning problem considered here but have application to other similar problems. Application of these techniques to the problem of planning the motion of a general polyhedral body moving in 3-space amidst polyhedral obstacles is also described.     

Instabilities of robot motion

Instabilities of robot motion are caused by topological reasons. In this paper we find a relation between the topological properties of a configuration space (the structure of its cohomology algebra) and the character of instabilities, which are unavoidable in any motion planning algorithm. More specifically, let X denote the space of all admissible configurations of a mechanical system. A motion planner is given by a splitting X×X=F₁F₂F_k (where F₁,…,F_k are pairwise disjoint ENRs, see below) and by continuous maps s_j :F_j→PX, such that Es_j=1_Fj. Here PX denotes the space of all continuous paths in X (admissible motions of the system) and E :PX→X×X denotes the map which assigns to a path the pair of its initial–end points. Any motion planner determines an algorithm of motion planning for the system. In this paper we apply methods of algebraic topology to study the minimal number of sets F_j in any motion planner in X. We also introduce a new notion of order of instability of a motion planner; it describes the number of essentially distinct motions which may occur as a result of small perturbations of the input data. We find the minimal order of instability, which may have motion planners on a given configuration space X. We study a number of specific problems: motion of a rigid body in R³, a robot arm, motion in R³ in the presence of obstacles, and others.     

An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space

We present an efficient algorithm for planning the motion of a convex polygonal bodyB in two-dimensional space bounded by a collection of polygonal obstacles. Our algorithm extends and combines the techniques of Leven and Sharir and of Sifrony and Sharir used for the case in whichB is a line segment (a ladder). It also makes use of the results of Kedem and Sharir on the planning of translational motion ofB amidst polygonal obstacles, and of a recent result of Leven and Sharir on the number of free critical contacts ofB with such polygonal obstacles. The algorithm runs in timeO(kn ₆(kn) logkn), wherek is the number of sides ofB, n is the number of obstacle edges, and ,(q) is an almost linear function ofq yielding the maximal number of connected portions ofq continuous functions which compose the graph of their lower envelope, where it is assumed that each pair of these functions intersect in at mosts points.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

基于模糊传感器的机器人动态障碍环境中的运动控制

对自主式机械手在动态和部分已知且存在运动障碍环境中的运动规划和控制进行了研究,解决了自由碰撞运动控制中具有普遍意义的问题。利用人工势能场的机器人导航控制技术由模糊控制实现,系统的稳定性由李雅普诺夫原理保证。模糊控制器为机器人伺服提供控制指令,使机器人在不可预知的环境中能实时地、自主地选择到达目标的路径和方向。在动态环境的实时控制中,基于传感器的运动控制是处理未知模型和障碍物的重要控制方式。     

A genetic-fuzzy approach for mobile robot navigation among moving obstacles

In this paper, a genetic-fuzzy approach is developed for solving the motion planning problem of a mobile robot in the presence of moving obstacles. The application of combined soft computing techniques — neural network, fuzzy logic, genetic algorithms, tabu search and others — is becoming increasingly popular among various researchers due to their ability to handle imprecision and uncertainties that are often present in many real-world problems. In this study, genetic algorithms are used for tuning the scaling factors of the state variables (keeping the relative spacing of the membership distributions constant) and rule sets of a fuzzy logic controller (FLC) which a robot uses to navigate among moving obstacles. The use of an FLC makes the approach easier to be used in practice. Although there exist many studies involving classical methods and using FLCs they are either computationally extensive or they do not attempt to find optimal controllers. The proposed genetic-fuzzy approach optimizes the travel time of a robot off-line by simultaneously finding an optimal fuzzy rule base and optimal scaling factors of the state variables. A mobile robot cant then use this optimal FLC on-line to navigate in presence of moving obstacles. The results of this study on a number of problem scenarios show that the proposed genetic-fuzzy approach can produce efficient knowledge base of an FLC for controlling the motion of a robot among moving obstacles.     

Parallel computing in combinatorial optimization

This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods.     

Dynamic contact of a beam against rigid obstacles: Convergence of a velocity-based approximation and numerical results

Motivated by the study of vibrations due to looseness of joints, we consider the motion of a beam between rigid obstacles. Due to the non-penetrability condition, the dynamics is described by a hyperbolic fourth order variational inequality. We build a family of fully discretized approximations of this problem by combining some classical space discretizations with velocity based time-stepping algorithms for discrete mechanical systems subjected to unilateral constraints. We prove the stability and the convergence of these numerical methods. Finally we propose some examples of implementation using either Hermite or B-spline finite element approximations.     

Search space pruning and global optimisation of multiple gravity assist spacecraft trajectories

We introduce and describe the Multiple Gravity Assist problem, a global optimisation problem that is of great interest in the design of spacecraft and their trajectories. We discuss its formalization and we show, in one particular problem instance, the performance of selected state of the art heuristic global optimisation algorithms. A deterministic search space pruning algorithm is then developed and its polynomial time and space complexity derived. The algorithm is shown to achieve search space reductions of greater than six orders of magnitude, thus reducing significantly the complexity of the subsequent optimisation. This work was partially funded under the Ariadna scheme of the European Space Agency, contract number 18138/04/NL/MV.     

Feasibility of motion planning on acyclic and strongly connected directed graphs

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time.     

Algorithmic and complexity issues of robot motion in an uncertain environment

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

Simplified Voronoi diagrams

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in anr-dimensional space may be simplified to a search on an (r–1)-dimensional Voronoi diagram. We define a Voronoi diagramV based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion-planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K-0334. John Canny was supported by an IBM fellowship. Bruce Donald was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory.     

Pseudo Approximation Algorithms with Applications to Optimal Motion Planning

We introduce a technique for computing approximate solutions to optimization problems. If $X$ is the set of feasible solutions, the standard goal of approximation algorithms is to compute $x\in X$ that is an $\varepsilon$-approximate solution in the following sense: $$d(x) \leq (1+\varepsilon)\, d(x^*),$$ where $x^* \in X$ is an optimal solution, $d\colon\ X\rightarrow {\Bbb R}_{\geq 0}$ is the optimization function to be minimized, and $\varepsilon>0$ is an input parameter. Our approach is first to devise algorithms that compute pseudo $\varepsilon$-approximate solutions satisfying the bound $$d(x) \leq d(x_R^*) + \varepsilon R,$$ where $R>0$ is a new input parameter. Here $x^*_R$ denotes an optimal solution in the space $X_R$ of $R$-constrained feasible solutions. The parameter $R$ provides a stratification of $X$ in the sense that (1) $X_R \subseteq X_{R}$ for $R < R$ and (2) $X_R = X$ for $R$ sufficiently large. We first describe a highly efficient scheme for converting a pseudo $\varepsilon$-approximation algorithm into a true $\varepsilon$-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than $\varepsilon$-approximation algorithms. Another benefit is that our algorithm is automatically precision-sensitive. We apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in three dimensions, and (B) $d_1$-optimal motion for a rod moving amidst planar obstacles (1ORM). Previously, no polynomial time $\varepsilon$-approximation algorithm for (B) was known. For (A), our new solution is simpler than previous solutions and has an exponentially smaller complexity in terms of the input precision.     

Maximum thick paths in static and dynamic environments

We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem.Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion.Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1.     

SOKOBAN and other motion planning problems

We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and extending (and also simplifying) a previous NP-hardness result of Wilfong. The family considered includes a motion planning problem which forms the basis of a popular computer game called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems considered are related to the “warehouseman's problem” considered by Hopcroft, Schwartz and Sharir, and to geometric versions of the motion planning problem on graphs considered by Papadimitriou, Raghavan, Sudan and Tamaki.     

A framework and a mean-field algorithm for the local control of spatial processes

The Markov Decision Process (MDP) framework is a tool for the efficient modelling and solving of sequential decision-making problems under uncertainty. However, it reaches its limits when state and action spaces are large, as can happen for spatially explicit decision problems. Factored MDPs and dedicated solution algorithms have been introduced to deal with large factored state spaces. But the case of large action spaces remains an issue. In this article, we define graph-based Markov Decision Processes (GMDPs), a particular Factored MDP framework which exploits the factorization of the state space and the action space of a decision problem. Both spaces are assumed to have the same dimension. Transition probabilities and rewards are factored according to a single graph structure, where nodes represent pairs of state/decision variables of the problem. The complexity of this representation grows only linearly with the size of the graph, whereas the complexity of exact resolution grows exponentially. We propose an approximate solution algorithm exploiting the structure of a GMDP and whose complexity only grows quadratically with the size of the graph and exponentially with the maximum number of neighbours of any node. This algorithm, referred to as MF-API, belongs to the family of Approximate Policy Iteration (API) algorithms. It relies on a mean-field approximation of the value function of a policy and on a search limited to the suboptimal set of local policies. We compare it, in terms of performance, with two state-of-the-art algorithms for Factored MDPs: SPUDD and Approximate Linear Programming (ALP). Our experiments show that SPUDD is not generally applicable to solving GMDPs, due to the size of the action space we want to tackle. On the other hand, ALP can be adapted to solve GMDPs. We show that ALP is faster than MF-API and provides solutions of similar quality for most problems. However, for some problems MF-API provides significantly better policies, and in all cases provides a better approximation of the value function of approximate policies. These promising results show that the GMDP model offers a convenient framework for modelling and solving a large range of spatial and structured planning problems, that can arise in many different domains where processes are managed over networks: natural resources, agriculture, computer networks, etc.