Motion Planning Methods PDF

# The World consists of... * Obstacles - Already occupied spaces of the world - In other words, robots can't go there * Free Space - Unoccupied space within the world - Robots "might" be able to go here - To determine where a robot can go, we need to discuss what a Configuratio...

# The World consists of... * Obstacles - Already occupied spaces of the world - In other words, robots can't go there * Free Space - Unoccupied space within the world - Robots "might" be able to go here - To determine where a robot can go, we need to discuss what a Configuration Space is ## Configuration Space **Notation:** * A: single rigid object (the robot) * W: Euclidean space where A moves; $W = R^2$ or $R^3$ * B1,... Bm: fixed rigid obstacles distributed in W * Fw - world frame (fixed frame) * FA - robot frame (moving frame rigidly associated with the robot) Configuration q of A is a specification of the physical state (position and orientation) of A w.r.t. a fixed environmental frame Fw. ## Configuration Space of A is the space (C) of all possible configurations of A. ### Point Robot (free-flying, no constraints) A diagram showing a point robot moving through 2-dimensional free space (Cfree), avoiding obstacle space (Cobs) and represented by a blue square. For a point robot moving in a 2-D plane, C-space is $R^2$. ### Point Robot (free-flying, no constraints) A diagram showing a point robot moving through 3-dimensional free space (Cfree), avoiding obstacle space (Cobs). For a point robot moving in a 3-D plane, C-space is $R^3$. ## Free Space The text originates from "Robot Motion Planning" by J.C. Latombe * Obstacles * C-obstacle * C-obstacle region **Cfree = C \UCB₁ = {q∈ C: A(q)NUCB₁ = $}** Free configuration q iff qe Ctree ## Motion Planning Methods The motion planning problem consists of the following: **Input** * Geometric descriptions of a robot and its environment (obstacles) * Initial and goal configurations **Output** * A path from start to finish (or the recognition that none exists) **Applications** * Robot-assisted surgery * Automated assembly plans * Drug-docking and analysis * Moving pianos around... **What to do?** ### Motion Planning Methods * **Roadmap approaches** - Goal: reduce the N-dimensional configuration space to a set of one-D paths to search * **Cell decomposition** - Goal: account for all of the free space * **Potential Fields** - Goal: Create local control strategies that will be more flexible than those above. * **Bug algorithms** - Limited knowledge path planning ## Roadmap: Visibility Graphs **Visibility graphs** - In a polygonal (or polyhedral) configuration space, construct all of the line segments that connect vertices to one another (and that do not intersect the obstacles themselves). Formed by connecting all "visible" vertices, the start point and the endpoint, to each other. For two points to be "visible" no obstacle can exist between them. Paths exist on the perimeter of obstacles. From Cfree, a graph is defined. This converts the problem into graph search using Dijkstra's algorithm O(N^2), where N = the number of vertices in C-space . ## The Visibility Graph in Action (Part 1) A diagram showing a visibility graph. First, draw lines of sight from the start and goal to all “visible" vertices and corners of the world. ## Visibility graph drawbacks Visibility graphs do not preserve their optimality in higher dimensions. A diagram showing the shortest path in 3 dimensions. In addition, the paths they find are “semi-free,” i.e. in contact with obstacles. ## Exact Cell Decomposition ### Trapezoidal Decomposition A diagram showing a trapezoidal decomposition of a free space and its connectivity graph. Decomposition of the free space into trapezoidal & triangular cells. The connectivity graph represents the adjacency relation between the cells. ### Trapezoidal Decomposition A diagram showing a connectivity graph and a trapezoidal decomposition. Search the graph for a path (sequence of consecutive cells). ### Trapezoidal Decomposition A diagram showing a trapezoidal decomposition. Transform the sequence of cells into a free path (e.g., connecting the mid-points of the intersection of two consecutive cells.) ## Optimality ### Trapezoidal Decomposition Two diagrams showing trapezoidal decompositions with different numbers of cells. Trapezoidal decomposition is exact and complete, but not optimal. Obtaining the minimum number of convex cells is NP-complete. There may be more details in the world than the task needs to worry about... ## Potential Field Method ### Potential Field (Working Principle) * The goal location generates an attractive potential - pulling the robot towards the goal * The obstacles generate a repulsive potential - pushing the robot far away from the obstacles. * The negative gradient of the total potential is treated as an artificial force applied to the robot. * Let the sum of the forces control the robot. ## Potential Field Method ### Sum of Potential A diagram showing a C-obstacle and the total potential. ### Potential Field Method * After get total potential, generate force field (negative gradient). * Let the sum of the forces control the robot. A diagram showing a total potential, equipotential contours and a negative gradient. To a large extent, this is computable from sensor readings. ## Potential Field Method **Pros:** * Spatial paths are not preplanned and can be generated in real time * Planning and control are merged into one function * Smooth paths are generated. * Planning can be coupled directly to a control algorithm. **Cons:** * Trapped in local minima in the potential field. * Because of this limitation, commonly used for local path planning * Use random walk, backtracking, etc to escape the local minima. ## Motion Planning Methods * **Roadmap approaches** - Visibility Graph * **Cell decomposition** - Trapezoidal decomposition * **Potential Fields** * **Bug algorithm** - Limited-knowledge path planning ## Bug Algorithms Path planning with limited knowledge - Insect-inspired "bug" algorithms. A diagram showing a start and goal position in a 2-D plane. * known direction to goal * only local sensing (walls/obstacles encoders) * "reasonable" world (1) finite obstacles in any finite range. (2) a line will intersect an obstacle finite times. ## Beginner Strategy Insect-inspired "bug" algorithms A diagram showing a start and goal position in a 2-D plane. Switching between two simple behaviors: * Moving directly towards the goal * Circumnavigating an obstacle ### Bug algorithm 1. head toward goal 2. follow obstacles until you can head toward the goal again. 3. continue. ## Summary * Configuration Space * **Motion Planning Methods** - Roadmap approaches - Cell decomposition - Potential Fields - Bug Algorithms ## References * G. Dudek, M. Jenkin, Computational Principles of Mobile Robots, MIT Press, 2000 (Chapter 5) * J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991. **Path Planning with A* algorithm** * S. Kambhampati, L. Davis, "Multiresolution Path Planning for Mobile Robots", IEEE Journal of Robotrics and Automation, Vol. RA-2, No.3, 1986, pp.135-145. **Potential Field** * O. Khatib, "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots", Int. Journal of Robotics Research, 5(1), pp.90-98, 1986. * P. Khosla, R. Volpe, "Superquadratic Artificial Potentials for Obstacle Avoidance and Approach" Proc. Of ICRA, 1988, pp.1178-1784. * B. Krogh, "A Generalized Potential Field Approach to Obstacle Avoidance Control" SME Paper MS84-484.