Selected Publications
For a full list of publications, see my google scholar page or my dblp page.
Filter by type:
Effective footstep planning using homotopy-class guidance
Abstract
Planning the motion for humanoid robots is a computationally-complex task due to the high dimensionality of the system. Thus, a common approach is to first plan in the low-dimensional space induced by the robot’s feet—a task referred to as footstep planning. This low-dimensional plan is then used to guide the full motion of the robot. One approach that has proven successful in footstep planning is using search-based planners such asA*and its many variants. To do so, these search-based planners have to be endowed with effective heuristics to efficiently guide them through the search space. However, designing effective heuristics is a time-consuming task that requires the user to have good domain knowledge. Thus, our goal is to be able to effectively plan the footstep motions taken by a humanoid robot while obviating the burden on the user to carefully design local-minima free heuristics. To this end, we propose to use user-defined homotopy classes in the workspace that are intuitive to define. These homotopy classes are used to automatically generate heuristic functions that efficiently guide the footstep planner. Additionally, we present an extension to homotopy classes such that they are applicable to complex multi-level environments. We compare our approach for footstep planning with a standard approach that uses a heuristic common to footstep planning. In simple scenarios, the performance of both algorithms is comparable. However, in more complex scenarios our approach allows for a speedup in planning of several orders of magnitude when compared to the standard approach.
Sampling-Based Robot Motion Planning
Abstract
In this article, I provide insight on why planning (high-quality) paths for complex robotic systems is computationally challenging. Specifically, after providing algorithmic background, we examine general computational challenges that arise in motion planning. This is done by examining sampling-based methods, a common approach to address the motion-planning problem, and considering the different algorithmic building blocks that are used to design such planners and their unique computational challenges. This article focuses on the simple problem of rigid-body planning, but highlights challenges and approaches that occur when extending such algorithms to more complex settings.
Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning
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
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.
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.
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%.
Research Challenges and Opportunities in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery Problems
Abstract
Recent years have shown a large increase in applications and research of problems that include moving a fleet of physical robots. One particular application that is currently a multi-billion industry led by tech giants such as Amazon robotics and Alibaba is warehouse robots. In this application, a large number of robots operate autonomously in the warehouse picking up, carrying, and putting down the inventory pods. In this paper, we outline several key research challenges and opportunities that manifest in this warehouse application. The first challenge, known as the Multi-Agent Path Finding (MAPF) problem, is the problem of finding a non-colliding path for each agent. While this problem has been well-studied in recent years, we outline several open questions, including understanding the actual hardness of the problem, learning the warehouse to improve online computations, and distributing the problem. The second challenge is known as the Multi-Agent Package and Delivery (MAPD) problem, which is the problem of moving packages in the warehouse. This problem has received some attention, but with limited theoretical understanding or exploitation of the incoming stream of requests. Finally, we highlight a third, often overlooked challenge, which is the challenge of designing the warehouse in a way that will allow efficient solutions of the two above challenges.
Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps
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
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
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
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
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.
Roadmaps
Roadmaps
In this essay we consider the problem of complete motion planning. Namely, we are interested in planners that are guaranteed to compute a solution, if one exists and to correctly report if no such solution exists otherwise. This is done by abstracting the continuous configuration space (C-space) into a discrete graph-like data structure embedded in Cfree. This is needed because reasoning over the continuous structure of the free space is highly non trivial. Throughout this article, we assume that we have access to an explicit representation of the C-space obstacles and that the C-space is $R^k$
Roadmap-based methods are some of the first complete techniques for motion planning. As we describe, they are usually limited (from a practical point of view) to low dimensions, but can be very powerful if used correctly. Moreover, this approach inspired modern state-of-the-art tools for robot motion planning such as sampling-based algorithms.
Effient high-quality motion planning in tight settings
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
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.