Rapidly-exploring random tree

from Wikipedia, the free encyclopedia
Rapidly-exploring Random Tree (RRT) 500x373

Rapidly exploring random tree (RRT) (dt. About fast erkundender random tree ) is a search algorithm (and the underlying tree data structure ), the high-dimensional search spaces scans random from possible paths. In robotics , the algorithm and variations of it are often used for motion planning , i.e. for planning efficient movements, e.g. B. of gripper arms.

history

In order to carry out path planning for robots around obstacles, the A * algorithm was developed relatively early in computer science (1960s). This searches in a graph for the shortest path from A to B. RRT expands A * by two essential elements: on the one hand, a Voronoi bias is used, which divides the problem space into even areas, and, on the other hand, the graph can add new nodes at any random point be expanded. The Voronoi bias is mainly used for geometric path planning problems. The goal is to expand the graph wherever the room has not been well lit up until now. This makes it possible to plan paths that first lead through a narrowing and then fork, as is the case with complicated labyrinths. The ability to add new nodes at any point is required for this.

RRT is considered to be one of the most efficient methods for planning paths in mazes and taking into account obstacles.

In addition to the original RRT algorithm, many extensions have been developed, of which RRTConnect is the best known. Although it is often efficient, in some cases RRT even performs worse than a classic Dijkstra algorithm .

Voronoi bias

The Voronoi bias is used to control the growth of the RRT tree and is therefore also referred to as "guided policy search" or "shaping". The playing area is divided into even boxes, the number of nodes in each quadrant is determined and the area with the fewest nodes is expanded by a new node.

Unfortunately, this possibility of increasing efficiency does not work with other problems from robotics such as B. Grass planning because there the problem area cannot be mapped as a 2D playing field, but a higher number of variables is available. In such cases, it is not possible to calculate which areas of the playing field are close to each other and which are far apart. In other words, there is no quality criterion for assessing the spread of the RRT tree.

DARRT

Diverse Action Rapidly-exploring Random Tree (DARRT) is a special RRT algorithm that combines motion primitives with an RRT solver. This enables complex robotics tasks such as gripping an object or walking in difficult terrain to be mastered.

description

The starting point for the development of DARRT was the question of how to achieve a certain target state in the C-Space (Configuration Space). Usually the problem space is too large to be tried out using brute force methods . In the past, every robot control system has failed because of this challenge. DARRT solves the problem by defining certain motion primitives in a first step (various actions). These motion primitives are tried out with the help of a solver in the form of a graph. Hence the addition RRT.

A motion primitive can be "walk forward", "grasp" or "reachpoint". The concept of motion primitives is derived from procedural animation where something like this has been used for a long time to realistically animate characters in computer games. The RRT sampling, on the other hand, is based on a graph-based search . Each node corresponds to a state of the physics engine from which sub-nodes are generated. In this way, a forward simulation of the physics engine only needs to be run for a small moment, which saves CPU time. RRT originally comes from pathplanning but is used at DARRT to sample instances of Box2D , ODE or other physics engines.

An implementation as an executable program by DARRT is available as OpenSource on the ROS project website. Gripping objects is explained here.

inventor

Jennifer L. Barry is the inventor of DARRT. She first described the process in 2013 in her dissertation. Jennifer L. Barry is employed by Boston Dynamics . She previously worked at Rethink Robotics and MIT . Their website is available on the MIT server, where DARRT and other projects are presented to the public.

Hybrid system

The reason why both Motion Primitive and RRT are used at DARRT has to do with the fact that both methods have strengths and weaknesses that complement each other optimally. RRT alone is considered too computationally expensive, but it is easy to implement in terms of programming. Motion primitives require only a small amount of CPU resources, but are difficult to program because manual C ++ source code has to be created which is heavily dependent on the specific problem. However, if you combine both methods, you get an algorithm that requires little CPU performance but is also very powerful.

generalization

DARRT is a so-called multi-modal planner. This term comes from the PDDL environment and defines macroactions to solve complex hierarchical problems. For example, a task in which a robot first has to fetch a key from a room in order to open a treasure chest with it. Such problems cannot be solved with conventional methods of artificial intelligence.

Possible applications

The DARRT algorithm was previously implemented on the ROS standard robot PR2. There are videos that show how he plans and executes a complex sequence of actions. First he drives to a table, then carries out a push action with a plate, grabs it on the edge of the table, drives the plate to a second table, puts the plate there and performs another push action. This process shows how DARRT works in practice. There are a number of predefined motion primitives that are executed one after the other. The more precise parameters as well as the order are determined by a planner.

Furthermore, DARRT was also used for "dexterous grasping" tasks as part of the DARPA ARM-S project. The task there was to write software for the " CMU Andy Robot" that picks up a tool from a table and puts it back in another place. DARRT was used to generate the behavior tree on the fly, which plans the sequence of actions.

Further applications in practice were:

  • on a Baxter robot from Rethink Robotics as part of a workshop
  • for sorting Lego bricks by a PR2 robot (a process related to the DARRT algorithm)
  • Control of robotic arms to move an object on the table

Individual evidence

  1. ^ Lavalle, SM: Rapidly-exploring random trees: A new tool for path planning . In: Computer Science Dept, Iowa State University, Tech. Rep. TR . 1998, pp. 98-11.
  2. ↑ Bertram Rohrmoser, Christopher Parlitz: Implementation of a movement planning for a robot arm Implementation of a path-planning algorithm for a robot arm . In: Fraunhofer IPA . 2002.
  3. ↑ Lukas KNispel, Radomil Matousek: A Performance Comparison of Rapidly-exploring Random Tree and Dijkstra's Algorithm for Holonomic Robot Path Planning . In: Institute of Automation and Computer Science, Faculty of Mechanical Engineering, Brno University of Technology . 2013.
  4. ↑ Chris Urmson, Raid G. Simmons: Approaches for heuristically biasing RRT growth . In: IROS . tape 2 , 2003, p. 1178-1183 .
  5. ↑ darrt Documentation , ROS.org, 2013, accessed December 21, 2016
  6. ↑ Leslie Kaelbling , Thomas Lozano-Perez: Intelligence in the Now: Robust Intelligence in Complex Domains . In: DTIC Document . 2015.
  7. ↑ a b Jennifer Lynn Barry: Manipulation with diverse actions . In: MIT . 2013.
  8. ↑ Jennifer Barry professional biography, LinkedIn, 2016
  9. ↑ Personal Website Jennifer Barry, CSAIL, MIT 2013 , accessed December 21, 2016
  10. ↑ Sören Jentzsch, Andre Gaschler, Oussama Khatib, Alois Knoll: MOPL: A multi-modal path planner for generic manipulation tasks . In: International Conference on Intelligent Robots and Systems (IROS) . 2015, p. 6208-6214 .
  11. ↑ Matt Klingensmith, Youtube Video: DARRT Tool Regrasp (4x) 2014
  12. ↑ Jennifer Barry: Planning and Manufacturing Robots . In: NSF Workshop on Robot Planning in the Real World . 2013.
  13. ↑ Megha Gupta, Jörg Müller, Gaurav Sukhatme: Using manipulation primitives for object sorting in cluttered environments . In: IEEE transactions on Automation Science and Engineering . tape 12 , no. 2 , 2015, p. 608-614 .
  14. ↑ Jennifer E. King, Joshua A. Haustein, Siddharta S. Srinivasa, Tamim Asfour: Nonprehensile whole arm rearrangement planning on physics manifolds . In: IEEE International Conference on Robotics and Automation (ICRA) . 2015, p. 2508-2515 .