Filter by type:

Sort by year:

Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning

Kiril Solovey, Oren Salzman, Dan Halperin
Journal Paper The International Journal of Robotics Research (IJRR), Volume 35, Issue 5, Pages 501-513, 2016

Abstract

We present a sampling-based framework for multi-robot motion planning. which combines an implicit representation of roadmaps for multi-robot motion planning with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of the tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios that involve as many as 60 degrees of freedom and on scenarios that require tight coordination between robots. On most of these scenarios our algorithm is faster by a factor of at least 10 when compared to existing algorithms that we are aware of.

Motion Planning for Multi-Link Robots by Implicit Configuration-Space Tiling

Oren Salzman, Kiril Solovey, Dan Halperin
Journal Paper IEEE Robotics and Automation Letters (RA-L), Volume 1, Issue 2, Pages 760-767, 2016

Abstract

We study the problem of motion-planning for free-flying multi-link robots and develop a sampling-based algorithm that is specifically tailored for the task. Our approach exploits the fact that the set of configurations for which the robot is self-collision free is independent of the obstacles or of the exact placement of the robot. This allows for decoupling between costly self-collision checks on the one hand, which we do off-line (and can even be stored permanently on the robot’s controller), and collision with obstacles on the other hand, which we compute in the query phase. In particular, given a specific robot type our algorithm precomputes a tiling roadmap, which efficiently and implicitly encodes the self-collision free (sub-)space over the entire configuration space, where the latter can be infinite for that matter. To answer a query, which consists of a start position, a target region, and a workspace environment, we traverse the tiling roadmap while only testing for collisions with obstacles. Our algorithm suggests more flexibility than the prevailing paradigm in which a precomputed roadmap depends both on the robot and on the scenario at hand. We demonstrate the effectiveness of our approach on open and closed-chain multi-link robots, where in some settings our algorithm is more than fifty times faster than commonly used, as well as state-of-the-art solutions.

Asymptotically Near-Optimal RRT for Fast, High-Quality Motion Planning.

Oren Salzman, Dan Halperin
Journal Papers IEEE Transactions on Robotics, Volume: 32 Issue: 3, Pages 473 - 483, 2016

Abstract

We present lower bound tree-RRT (LBT-RRT), a single-query sampling-based motion-planning algorithm that is asymptotically near-optimal. Namely, the solution extracted from LBT-RRT converges to a solution that is within an approximation factor of $1 + \eps$ of the optimal solution. Our algorithm allows for a continuous interpolation between the fast RRT algorithm and the asymptotically optimal RRT* and RRG algorithms when the cost function is the path length. When the approximation factor is 1 (i.e., no approximation is allowed), LBT-RRT behaves like RRG. When the approximation factor is unbounded, LBT-RRT behaves like RRT. In between, LBT-RRT is shown to produce paths that have higher quality than RRT would produce and run faster than RRT* would run. This is done by maintaining a tree that is a subgraph of the RRG roadmap and a second, auxiliary graph, which we call the lower-bound graph. The combination of the two roadmaps, which is faster to maintain than the roadmap maintained by RRT*, efficiently guarantees asymptotic near-optimality. We suggest to use LBT-RRT for high-quality anytime motion planning. We demonstrate the performance of the algorithm for scenarios ranging from 3 to 12 degrees of freedom and show that even for small approximation factors, the algorithm produces high-quality solutions (comparable with RRG and RRT*) with little running-time overhead when compared with RRT.

Sparsification of motion-planning roadmaps by edge contraction.

Oren Salzman, Doron Shaharabani, Pankaj K. Agarwal, Dan Halperin
Journal Paper The International Journal of Robotics Research, Volume: 33 Issue: 14, Pages 1711-1725, 2014

Abstract

Roadmaps constructed by the recently introduced PRM* algorithm for asymptotically-optimal motion planning encode high-quality paths yet can be extremely dense. We consider the problem of sparsifying the roadmap, i.e. reducing its size, while minimizing the degradation of the quality of paths that can be extracted from the resulting roadmap. We present a simple, effective sparsifying algorithm, called roadmap sparsification by edge contraction (RSEC). The primitive operation used by RSEC is edge contraction—the contraction of a roadmap edge (v',v'') to a new vertex v and the connection of the new vertex v to the neighboring vertices of the contracted edge’s vertices (i.e. to all neighbors of v' and v''). For certain scenarios, we compress more than 97% of the edges and vertices of a given roadmap at the cost of degradation of average shortest path length by at most 4%.

Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps

Shushman Choudhury, Oren Salzman, Sanjiban Choudhury, Siddhartha S. Srinivasa
Conference Paper IEEE International Conference on Robotics and Automation (ICRA), 2017 (to appear)

Abstract

We consider the problem of computing shortest paths in a dense motion-planning roadmap $G$. We assume that $n$, the number of vertices of $G$, is very large. Thus, using any path-planning algorithm that directly searches $G$, running in $O(n^2)$ time, becomes unacceptably expensive. We are therefore interested in anytime search algorithms that obtain successively shorter feasible paths and converge to the shortest path in $G$. Our key insight is to leverage existing path-planning algorithms and provide them with a sequence of subgraphs of $G$. To do so, we study the space of all ($r$-disk) subgraphs of $G$. We then formulate and present two densification strategies for traversing this space which exhibit complementary properties with respect to problem difficulty. This inspires a third, hybrid strategy which has favorable properties regardless of problem difficulty. This general approach is then demonstrated and analyzed using the specific case where a low-dispersion deterministic sequence is used to generate the samples used for $G$. Finally we empirically evaluate the performance of our strategies for random scenarios in $R^2$ and $R^4$ and on manipulation planning problems for a 7 DOF robot arm, and validate our analysis.

New perspective on sampling-based motion planning via random geometric graphs

Kiril Solovey, Oren Salzman, Dan Halperin
Conference Paper Robotics: Science and Systems (RSS), 2016

Abstract

We study a path-planning problem amid a set $O$ of obstacles in $R^2$, in which we wish to compute a short path between two points while also maintaining a high clearance from $O$; the clearance of a point is its distance from a nearest obstacle in $O$. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let $n$ be the total number of obstacle vertices and let $\eps \in (0, 1]$. Our algorithm computes in time $O((n/\eps)^2 \log (n/\eps)) a path of total cost at most (1 + \eps) times the cost of the optimal path.

New perspective on sampling-based motion planning via random geometric graphs

Kiril Solovey, Oren Salzman, Dan Halperin
Conference Paper Robotics: Science and Systems (RSS), 2016

Abstract

We study a path-planning problem amid a set $O$ of obstacles in $R^2$, in which we wish to compute a short path between two points while also maintaining a high clearance from $O$; the clearance of a point is its distance from a nearest obstacle in $O$. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let $n$ be the total number of obstacle vertices and let $\eps \in (0, 1]$. Our algorithm computes in time $O((n/\eps)^2 \log (n/\eps)) a path of total cost at most (1 + \eps) times the cost of the optimal path.

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles

Pankaj K. Agarwal, Kyle Fox, Oren Salzman
Conference Paper ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1179-1192, 2016

Abstract

We study a path-planning problem amid a set $O$ of obstacles in $R^2$, in which we wish to compute a short path between two points while also maintaining a high clearance from $O$; the clearance of a point is its distance from a nearest obstacle in $O$. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let $n$ be the total number of obstacle vertices and let $\eps \in (0, 1]$. Our algorithm computes in time $O((n/\eps)^2 \log (n/\eps)) a path of total cost at most (1 + \eps) times the cost of the optimal path.

Algorithmic Motion Planning

Dan Halperin, Oren Salzman, Micha Sharir
Book Chapter In third edition of the “Handbook of Discrete and Computational Geometry” edited by Csaba Toth, to appear.
image

Algorithmic Motion Planning

Motion planning is a fundamental problem in robotics. It comes in a variety of forms, but the simplest version is as follows. We are given a robot system $B$, which may consist of several rigid objects attached to each other through various joints, hinges, and links, or moving independently, and a 2D or 3D environment $V$ cluttered with obstacles. We assume that the shape and location of the obstacles and the shape of $B$ are known to the planning system. Given an initial placement $Z_1$ and a final placement $Z_2$ of $B$, we wish to determine whether there exists a collision-avoiding motion of $B$ from $Z_1$ to $Z_2$, and, if so, to plan such a motion. In this simplified and purely geometric setup, we ignore issues such as incomplete information, nonholonomic constraints, control issues related to inaccuracies in sensing and motion, nonstationary obstacles, optimality of the planned motion, and so on.

Since the early 1980s, motion planning has been an intensive area of study in robotics and computational geometry. In this chapter we will focus on algorithmic motion planning, emphasizing theoretical algorithmic analysis of the problem and seeking worst-case asymptotic bounds, and only mention briefly practical heuristic approaches to the problem. The majority of this chapter is devoted to the simplified version of motion planning, as stated above. Section 50.1 presents general techniques and lower bounds. Section 50.2 considers efficient solutions to a variety of specific moving systems with a small number of degrees of freedom. These efficient solutions exploit various sophisticated methods in computational and combinatorial geometry related to arrangements of curves and surfaces. Section 50.3 then briefly discusses various extensions of the motion planning problem such as computing optimal paths with respect to various quality measures, computing the path of a tethered robot, incorporating uncertainty, moving obstacles, and more.

Effient high-quality motion planning in tight settings

Oren Salzman
Dissertation PhD thesis, Tel Aviv University, July 2016, Advisor: Prof. Dan Halperin.

Abstract

In recent years, robots play an active role in everyday life: medical robots assist in complex surgeries, search and rescue robots are employed in mining accidents and urban disasters and low-cost commercial robots clean houses. There is a growing need for more sophisticated algorithmic tools enabling stronger capabilities for these robots. One fundamental problem that robotic researchers grapple with is motion planning. Motion planning deals with planning a collision-free path for a moving creature in an environment cluttered with obstacles. Motion planning is not limited to robotics, it has applications in diverse domains such as computer games and computational biology. Typically, a high-quality path is desired where quality can be measured in terms of, e.g., path length, clearance (distance from nearest obstacle at any given time) smoothness or energy consumption along the path, to mention a few criteria.

The complexity of a motion-planning problem is primarily governed by two factors: (i) The dimension of the configuration space-a space defined by the parameters needed to describe the robot's position and orientation and (ii) the tightness of the environment-informally, an environment is said to be tight if the robot is required to move with little or no clearance from the obstacles.

State-of-the-art motion-planning algorithms can efficiently construct paths for low-complexity problems (i.e., either of low-dimensional configuration spaces or of scenarios that do not contain narrow passages). However, as the complexity increases, their running-time may grow in an exponential fashion (exponential in the dimension of the configuration space or in the clearance of the path that the robot needs to move along). Moreover, algorithms that produce high-quality paths with optimality guarantees require additional overhead both in terms of running times and memory consumption when compared to the basic version of these algorithms.

In this dissertation we (i) describe efficient algorithms to produce paths in highly complex scenarios and (ii) provide effiient algorithms that produce high-quality paths. As such, the main body of this dissertation is subdivided into two parts. Each part includes the collection of articles published during the dissertation relevant to that specific topic.

Specifically, in the first part we describe two planners that are concerned with efficiently finding a solution (and not necessarily a high-quality one). The first planner is concerned with planning paths for two polygonal robots translating and rotating in the plane while in the second, we study the problem of motion-planning for free flying multi-link robots. Each planner uses conceptually different tools: The first planner combines geometric methods for the exact and complete analysis of low-dimensional spaces with sampling-based approaches that are appropriate for higher dimensions. In the second planner we exploit the structure of the problem to devise a data-structure that efficiently represents the search space. We analyze each planner theoretically and show in experiments that both planners outperform state-of-the art algorithms by several orders of magnitude in running time in certain scenarios.

In the second part of the dissertation, which is concerned with high-quality planning, we describe a series of data structures and algorithms that allow to significantly increase the computational efficiency of high-quality sampling-based algorithms with respect to computation time and space requirements. The first work adapts surface-simplification techniques to produce sparse data structures that allow to obtain high-quality paths after preprocessing a given settings. The second and third use efficient graph-search algorithms to significantly speed up computation time of planners using algorithmic approaches such as relaxing optimality to near optimality and lazy computation. We conclude with two specific instances of high-quality planning in the plane. In the first we study a path-planning problem in which we wish to compute a short path between two points while also maintaining a high clearance from the obstacles. In the second we study the problem of planning the shortest path for a polygonal robot anchored to a fixed base point by a finite tether.

Motion Planning via Manifold Samples

Oren Salzman
Dissertation Master's thesis, Tel Aviv University, September 2011, Advisor: Prof. Dan Halperin.

Abstract

We present a general and modular algorithmic framework for path planning of robots. Our framework combines geometric methods for exact and complete analysis of low-dimensional configuration spaces, together with sampling-based approaches that are appropriate for higher dimensions. We suggest taking samples that are entire low-dimensional manifolds of the configuration space. These samples capture the connectivity of the configuration space much better than isolated point samples. Geometric algorithms then provide powerful primitive operations for complete analysis of the low-dimensional manifolds. We have implemented our framework for the concrete case of a polygonal robot translating and rotating amidst polygonal obstacles. To this end, we have developed a primitive operation for the analysis of an appropriate set of manifolds using arrangements of curves of rational functions. This modular integration of several carefully engineered components has led to a significant speedup over a careful implementation of the PRM (Probabilistic Roadmap Planner) algorithm, which represents the sampling-based approach that is prevalent in practice. For example, in a tight passage scenario we demonstrate a 27-fold speedup in running time. We prove that a specific instance of the framework is probabilistically complete. We believe that this proof is an intermediate stage towards a general proof of the entire framework. As part of the implementation, we construct a set of critical curves to decompose manifolds representing the motion of a robot free to rotate while translating along a fixed segment. The curves, which are rational functions, are passed on to the Cgal (the Computational Geometry Algorithms Library) arrangement package in order to decompose the space into free and forbidden cells; thus the implementation requires the arrangement package to handle such curves. We therefore developed a C++ traits class to facilitate the implementation. We include experimental results and comparisons with similar traits classes which demonstrate the efficiency of our traits class and note that it is integrated into Cgal 3.9.