Jur van den Berg

ICRA Conference 2015 Conference Paper

GP-GPIS-OPT: Grasp planning with shape uncertainty using Gaussian process implicit surfaces and Sequential Convex Programming

• Jeffrey Mahler
• Sachin Patil
• Ben Kehoe
• Jur van den Berg
• Matei Ciocarlie
• Pieter Abbeel
• Ken Goldberg

Computing grasps for an object is challenging when the object geometry is not known precisely. In this paper, we explore the use of Gaussian process implicit surfaces (GPISs) to represent shape uncertainty from RGBD point cloud observations of objects. We study the use of GPIS representations to select grasps on previously unknown objects, measuring grasp quality by the probability of force closure. Our main contribution is GP-GPIS-OPT, an algorithm for computing grasps for parallel-jaw grippers on 2D GPIS object representations. Specifically, our method optimizes an approximation to the probability of force closure subject to antipodal constraints on the parallel jaws using Sequential Convex Programming (SCP). We also introduce GPIS-Blur, a method for visualizing 2D GPIS models based on blending shape samples from a GPIS. We test the algorithm on a set of 8 planar objects with transparency, translucency, and specularity. Our experiments suggest that GP-GPIS-OPT computes grasps with higher probability of force closure than a planner that does not consider shape uncertainty on our test objects and may converge to a grasp plan up to 5. 7×faster than using Monte-Carlo integration, a common method for grasp planning under shape uncertainty. Furthermore, initial experiments on the Willow Garage PR2 robot suggest that grasps selected with GP-GPIS-OPT are up to 90% more successful than those planned assuming a deterministic shape. Our dataset, code, and videos of our experiments are available at http://rll.berkeley.edu/icra2015grasping/.

IROS Conference 2015 Conference Paper

Stochastic automatic collision avoidance for tele-operated unmanned aerial vehicles

• Daman Bareiss
• Jur van den Berg
• Kam K. Leang

This paper presents a stochastic approach for automatic collision avoidance for tele-operated unmanned aerial vehicles (UAVs). Collision detection and mitigation in the presence of uncertainty is an important problem to address because on-board sensing and state estimation uncertainties are inherent in real-world systems. A feedforward-based algorithm is described that continually extrapolates the future trajectory of the vehicle given the current operator control input for collision avoidance. If the predicted probability of a collision is greater than a user-defined confidence bound, the algorithm overrides the operator control input with the nearest, safe command signal to steer the robot away from obstacles, while maintaining user intent. The algorithm is implemented on a simulated quadrotor helicopter (quadcopter) with varying amounts of artificial uncertainty. Simulation results show that for a given confidence bound, the aerial robot is able to avoid collisions, even in a situation where the operator is deliberately attempting to crash the vehicle.

ICRA Conference 2015 Conference Paper

Toward asymptotically optimal motion planning for kinodynamic systems using a two-point boundary value problem solver

• Christopher Xie
• Jur van den Berg
• Sachin Patil
• Pieter Abbeel

We present an approach for asymptotically optimal motion planning for kinodynamic systems with arbitrary nonlinear dynamics amid obstacles. Optimal sampling-based planners like RRT*, FMT*, and BIT* when applied to kinodynamic systems require solving a two-point boundary value problem (BVP) to perform exact connections between nodes in the tree. Two-point BVPs are non-trivial to solve, hence the prevalence of alternative approaches that focus on specific instances of kinodynamic systems, use approximate solutions to the two-point BVP, or use random propagation of controls. In this work, we explore the feasibility of exploiting recent advances in numerical optimal control and optimization to solve these two-point BVPs for arbitrary kinodynamic systems and how they can be integrated with existing optimal planning algorithms. We combine BIT* with a two-point BVP solver that uses sequential quadratic programming (SQP). We consider the problem of computing minimum-time trajectories. Since the duration of trajectories is not known a-priori, we include the time-step as part of the optimization to allow SQP to optimize over the duration of the trajectory while keeping the number of discrete steps fixed for every connection attempted. Our experiments indicate that using a two-point BVP solver in the inner-loop of BIT* is competitive with the state-of-the-art in sampling-based optimal planning that explicitly avoids the use of two-point BVP solvers.

ICRA Conference 2014 Conference Paper

Automatic collision avoidance for manually tele-operated unmanned aerial vehicles

• Jason Israelsen
• Matt Beall
• Daman Bareiss
• Daniel Stuart
• Eric Keeney
• Jur van den Berg

In this paper we present an approach that aids the human operator of unmanned aerial vehicles by automatically performing collision avoidance with obstacles in the environment so that the operator can focus on the global direction of motion of the vehicle. As opposed to systems that override operator control as a last resort in order to avoid collisions (such as those found in modern automobiles), our approach is designed such that the operator can rely on the automatic collision avoidance, enabling intuitive and safe operator control of vehicles that may otherwise be difficult to control. Our approach continually extrapolates the future flight path of the vehicle given the current operator control input. If an imminent collision is predicted our algorithm will override the operator's control input with the nearest control input that will actually let the vehicle avoid collisions with obstacles. This ensures safe flight while simultaneously maintaining the intent of the human operator as closely as possible. We successfully implemented our approach on a physical quadrotor system in a laboratory environment. In all experiments the human operator failed to crash the vehicle into floors, walls, ceilings, or obstacles, even when deliberately attempting to do so.

ICRA Conference 2014 Conference Paper

Efficient exact collision-checking of 3-D rigid body motions using linear transformations and distance computations in workspace

• Liang He
• Jur van den Berg

This paper presents a new method for efficient and exact collision-checking of linear motions of 3-D rigid bodies. 3-D rigid bodies have 6-D configuration spaces (three degrees of freedom for position and three for orientation), and constitute an important subclass of motion planning problems. Our method can be used with any collision-checker that is capable of performing linear transformations and distance computations on 3-D geometry. As previous work has shown, computing the distance between the rigid body in some configuration and the workspace obstacles immediately determines the collision-status of surrounding configurations. Using a recursive procedure one can then determine exactly whether an entire motion of the rigid body is collision-free. In this paper, we will show that by performing an optimally selected linear transformation on the workspace, the collision-status of rigid body motions can be determined using significantly fewer (costly) distance computations. Since collision-checking is often the computational bottleneck in sampling-based motion planning, our approach allows for significant performance improvements of algorithms such as PRM and RRT when planning for 3-D rigid bodies. We demonstrate the benefit of our approach when used in combination with RRT to construct a planning tree in an illustrative benchmark motion planning scenario.

ICRA Conference 2014 Conference Paper

Online parameter estimation via real-time replanning of continuous Gaussian POMDPs

• Dustin J. Webb
• Kyle Lawson Crandall
• Jur van den Berg

An accurate dynamics model of a robot is an important ingredient of many algorithms used to solve robotics problems, including motion planning, control, localization, and mapping. Models derived from first principles often contain parameters (e. g. mass, moment of inertia, arm lengths, etc.) for which values are unknown. Those which cannot be easily measured must be estimated from the observed behavior of the robot. A good approach to address this problem is to plan control policies for the robot that elicit maximal amounts of information about the parameters of the system, while still achieving other objectives specified for the robot. In case of parameters subject to drift, this must be done continuously over the lifetime of the robot if costly re-calibrations are to be avoided. In this paper, we introduce a new method that formulates the parameter estimation problem as a continuous partially-observable Markov decision process (POMDP), which plans control policies that optimally trade-off the effort spent on learning parameters and effort spent on achieving regular robot objectives (exploration vs. exploitation), and allow for online, continual parameter estimation. While POMDPs have, until recently, been mostly of theoretical interest due to their inherent complexity, we build on recent advances that allow continuous, Gaussian POMDPs to be approximately-optimally solved in near-real-time rates. We show that the computed control policies lead to improved convergence of the belief of the parameters compared to system identification approaches based on applying random controls.

AIJ Journal 2014 Journal Article

Potential-based bounded-cost search and Anytime Non-Parametric A ⁎

• Roni Stern
• Ariel Felner
• Jur van den Berg
• Rami Puzis
• Rajat Shah
• Ken Goldberg

ICRA Conference 2013 Conference Paper

Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics

• Dustin J. Webb
• Jur van den Berg

We present Kinodynamic RRT*, an incremental sampling-based approach for asymptotically optimal motion planning for robots with linear dynamics. Our approach extends RRT*, which was introduced for holonomic robots [10], by using a fixed-final-state-free-final-time controller that optimally connects any pair of states, where the cost function is expressed as a trade-off between the duration of a trajectory and the expended control effort. Our approach generalizes earlier work on RRT* for kinodynamic systems, as it guarantees asymptotic optimality for any system with controllable linear dynamics, in state spaces of any dimension. In addition, we show that for the rich subclass of systems with a nilpotent dynamics matrix, closed-form solutions for optimal trajectories can be derived, which keeps the computational overhead of our algorithm compared to traditional RRT* at a minimum. We demonstrate the potential of our approach by computing asymptotically optimal trajectories in three challenging motion planning scenarios: (i) a planar robot with a 4-D state space and double integrator dynamics, (ii) an aerial vehicle with a 10-D state space and linearized quadrotor dynamics, and (iii) a car-like robot with a 5-D state space and non-linear dynamics.

ICRA Conference 2013 Conference Paper

Meso-scale planning for multi-agent navigation

• Liang He
• Jur van den Berg

We introduce a new concept; meso-scale planning in real-time multi-agent navigation. Whereas many traditional approaches to multi-agent navigation typically consist of two-levels — a macro-scale level providing agents with a global direction of motion around (large) static obstacles, and a micro-scale level in which agents seek to avoid collision with other agents — our approach adds a meso-scale level to give agents realistic behavior in scenarios where groups of other agents (e. g. families or crowds in a virtual world) form coherent entities. Rather than moving straight through such groups, our approach lets agents move around them. Our formulation considers each agent as an individual that may perceive sets of other agents as a group, and plans its motion accordingly. We base our approach on the velocity obstacle concept, and we show using simulation results that our method dramatically improves the quality of the trajectories computed for the agents.

ICRA Conference 2013 Conference Paper

Reciprocal collision avoidance for robots with linear dynamics using LQR-Obstacles

• Daman Bareiss
• Jur van den Berg

In this paper we present a formal approach to reciprocal collision avoidance for multiple mobile robots sharing a common 2-D or 3-D workspace whose dynamics are subject to linear differential constraints. Our approach defines a protocol for robots to select their control input independently (i. e. without coordination with other robots) while guaranteeing collision-free motion for all robots, assuming the robots can perfectly observe each other's state. To this end, we extend the concept of LQR-Obstacles (which is a generalization of Velocity Obstacles to robots with dynamics for collision avoidance among static obstacles) for reciprocal collision avoidance among multiple robots. We implemented and tested our approach in 3-D simulation environments for reciprocal collision avoidance of quadrotor helicopters, which have complex dynamics in 16-D state spaces. Our results show that our approach enables collision avoidance among over a hundred quadrotors in tight workspaces at real-time computation rates.

IROS Conference 2013 Conference Paper

Sigma hulls for Gaussian belief space planning for imprecise articulated robots amid obstacles

• Alex X. Lee
• Yan Duan
• Sachin Patil
• John Schulman
• Zoe McCarthy
• Jur van den Berg
• Ken Goldberg
• Pieter Abbeel

In many home and service applications, an emerging class of articulated robots such as the Raven and Baxter trade off precision in actuation and sensing to reduce costs and to reduce the potential for injury to humans in their workspaces. For planning and control of such robots, planning in belief ssigma hullpace, i. e. , modeling such problems as POMDPs, has shown great promise but existing belief space planning methods have primarily been applied to cases where robots can be approximated as points or spheres. In this paper, we extend the belief space framework to treat articulated robots where the linkage can be decomposed into convex components. To allow planning and collision avoidance in Gaussian belief spaces, we introduce the concept of sigma hulls: convex hulls of robot links transformed according to the sigma standard deviation boundary points generated by the Unscented Kalman filter (UKF). We characterize the signed distances between sigma hulls and obstacles in the workspace to formulate efficient collision avoidance constraints compatible with the Gilbert-Johnson-Keerthi (GKJ) and Expanding Polytope Algorithms (EPA) within an optimization-based planning framework. We report results in simulation for planning motions for a 4-DOF planar robot and a 7-DOF articulated robot with imprecise actuation and inaccurate sensors. These experiments suggest that the sigma hull framework can significantly reduce the probability of collision and is computationally efficient enough to permit iterative re-planning for model predictive control.

AAAI Conference 2012 Conference Paper

Efficient Approximate Value Iteration for Continuous Gaussian POMDPs

• Jur van den Berg
• Sachin Patil
• Ron Alterovitz

We introduce a highly efficient method for solving continuous partially-observable Markov decision processes (POMDPs) in which beliefs can be modeled using Gaussian distributions over the state space. Our method enables fast solutions to sequential decision making under uncertainty for a variety of problems involving noisy or incomplete observations and stochastic actions. We present an efficient approach to compute locally-valid approximations to the value function over continuous spaces in time polynomial (O[n4 ]) in the dimension n of the state space. To directly tackle the intractability of solving general POMDPs, we leverage the assumption that beliefs are Gaussian distributions over the state space, approximate the belief update using an extended Kalman filter (EKF), and represent the value function by a function that is quadratic in the mean and linear in the variance of the belief. Our approach iterates towards a linear control policy over the state space that is locally-optimal with respect to a user defined cost function, and is approximately valid in the vicinity of a nominal trajectory through belief space. We demonstrate the scalability and potential of our approach on problems inspired by robot navigation under uncertainty for state spaces of up to 128 dimensions.

ICRA Conference 2012 Conference Paper

Estimating probability of collision for safe motion planning under Gaussian motion and sensing uncertainty

• Sachin Patil
• Jur van den Berg
• Ron Alterovitz

We present a fast, analytical method for estimating the probability of collision of a motion plan for a mobile robot operating under the assumptions of Gaussian motion and sensing uncertainty. Estimating the probability of collision is an integral step in many algorithms for motion planning under uncertainty and is crucial for characterizing the safety of motion plans. Our method is computationally fast, enabling its use in online motion planning, and provides conservative estimates to promote safety. To improve accuracy, we use a novel method to truncate estimated a priori state distributions to account for the fact that the probability of collision at each stage along a plan is conditioned on the previous stages being collision free. Our method can be directly applied within a variety of existing motion planners to improve their performance and the quality of computed plans. We apply our method to a car-like mobile robot with second order dynamics and to a steerable medical needle in 3D and demonstrate that our method for estimating the probability of collision is orders of magnitude faster than naïve Monte Carlo sampling methods and reduces estimation error by more than 25% compared to prior methods.

ICRA Conference 2012 Conference Paper

LQG-obstacles: Feedback control with collision avoidance for mobile robots with motion and sensing uncertainty

• Jur van den Berg
• David Wilkie
• Stephen J. Guy
• Marc Niethammer
• Dinesh Manocha

This paper presents LQG-Obstacles, a new concept that combines linear-quadratic feedback control of mobile robots with guaranteed avoidance of collisions with obstacles. Our approach generalizes the concept of Velocity Obstacles [3] to any robotic system with a linear Gaussian dynamics model. We integrate a Kalman filter for state estimation and an LQR feedback controller into a closed-loop dynamics model of which a higher-level control objective is the “control input”. We then define the LQG-Obstacle as the set of control objectives that result in a collision with high probability. Selecting a control objective outside the LQG-Obstacle then produces collision-free motion. We demonstrate the potential of LQG-Obstacles by safely and smoothly navigating a simulated quadrotor helicopter with complex non-linear dynamics and motion and sensing uncertainty through three-dimensional environments with obstacles and narrow passages.

AAAI Conference 2011 Conference Paper

Anytime Nonparametric A*

• Jur van den Berg
• Rajat Shah
• Arthur Huang
• Ken Goldberg

Anytime variants of Dijkstra’s and A* shortest path algorithms quickly produce a suboptimal solution and then improve it over time. For example, ARA* introduces a weighting value (ε) to rapidly find an initial suboptimal path and then reduces ε to improve path quality over time. In ARA*, ε is based on a linear trajectory with ad-hoc parameters chosen by each user. We propose a new Anytime A* algorithm, Anytime Nonparametric A* (ANA*), that does not require ad-hoc parameters, and adaptively reduces ε to expand the most promising node per iteration, adapting the greediness of the search as path quality improves. We prove that each node expanded by ANA* provides an upper bound on the suboptimality of the current-best solution. We evaluate the performance of ANA* with experiments in the domains of robot motion planning, gridworld planning, and multiple sequence alignment. The results suggest that ANA* is as efficient as ARA* and in most cases: (1) ANA* finds an initial solution faster, (2) ANA* spends less time between solution improvements, (3) ANA* decreases the suboptimality bound of the current-best solution more gradually, and (4) ANA* finds the optimal solution faster. ANA* is freely available from Maxim Likhachev’s Search-based Planning Library (SBPL).

IROS Conference 2011 Conference Paper

EG-RRT: Environment-guided random trees for kinodynamic motion planning with uncertainty and obstacles

• Leonard Jaillet
• Judy Hoffman
• Jur van den Berg
• Pieter Abbeel
• Josep M. Porta
• Ken Goldberg

Existing sampling-based robot motion planning methods are often inefficient at finding trajectories for kinodynamic systems, especially in the presence of narrow passages between obstacles and uncertainty in control and sensing. To address this, we propose EG-RRT, an Environment-Guided variant of RRT designed for kinodynamic robot systems that combines elements from several prior approaches and may incorporate a cost model based on the LQG-MP framework to estimate the probability of collision under uncertainty in control and sensing. We compare the performance of EG-RRT with several prior approaches on challenging sample problems. Results suggest that EG-RRT offers significant improvements in performance.

ICRA Conference 2011 Conference Paper

Reciprocal collision avoidance with acceleration-velocity obstacles

• Jur van den Berg
• Jamie Snape
• Stephen J. Guy
• Dinesh Manocha

We present an approach for collision avoidance for mobile robots that takes into account acceleration constraints. We discuss both the case of navigating a single robot among moving obstacles, and the case of multiple robots reciprocally avoiding collisions with each other while navigating a common workspace. Inspired by the concept of velocity obstacles [3], we introduce the acceleration-velocity obstacle (AVO) to let a robot avoid collisions with moving obstacles while obeying acceleration constraints. AVO characterizes the set of new velocities the robot can safely reach and adopt using proportional control of the acceleration. We extend this concept to reciprocal collision avoidance for multi-robot settings, by letting each robot take half of the responsibility of avoiding pairwise collisions. Our formulation guarantees collision-free navigation even as the robots act independently and simultaneously, without coordination. Our approach is designed for holonomic robots, but can also be applied to kinematically constrained non-holonomic robots such as cars. We have implemented our approach, and we show simulation results in challenging environments with large numbers of robots and obstacles.

AAAI Conference 2011 Conference Paper

Self-Aware Traffic Route Planning

• David Wilkie
• Jur van den Berg
• Ming Lin
• Dinesh Manocha

One of the most ubiquitous AI applications is vehicle route planning. While state-of-the-art systems take into account current traffic conditions or historic traffic data, current planning approaches ignore the impact of their own plans on the future traffic conditions. We present a novel algorithm for self-aware route planning that uses the routes it plans for current vehicle traffic to more accurately predict future traffic conditions for subsequent cars. Our planner uses a roadmap with stochastic, timevarying traffic densities that are defined by a combination of historical data and the densities predicted by the planned routes for the cars ahead of the current traf- fic. We have applied our algorithm to large-scale traf- fic route planning, and demonstrated that our self-aware route planner can more accurately predict future traf- fic conditions, which results in a reduction of the travel time for those vehicles that use our algorithm.

AAMAS Conference 2010 Conference Paper

Independent Navigation of Multiple Robots and Virtual Agents

• Jamie Snape
• Stephen J. Guy
• Jur van den Berg
• Sean Curtis
• Sachin Patil
• Ming C. Lin
• Dinesh Manocha

We demonstrate an approach for collision- and oscillation-free navigation of multiple robots or virtual agents amongsteach other. Each entity acts independently and uses onlyboth the position and velocity of nearby entities to predicttheir future trajectories in order to avoid collisions. Entitiestake into account that the other entities are responding tothem likewise to prevent oscillations.

IROS Conference 2010 Conference Paper

Smooth and collision-free navigation for multiple robots under differential-drive constraints

• Jamie Snape
• Jur van den Berg
• Stephen J. Guy
• Dinesh Manocha

We present a method for smooth and collision-free navigation for multiple independent robots under differential-drive constraints. Our algorithm is based on the optimal reciprocal collision avoidance formulation and guarantees both smoothness in the trajectories of the robots and locally collision-free paths. We provide proofs of these guarantees and demonstrate the effectiveness of our method in experimental scenarios using iRobot Create mobile robots navigating amongst each other.

ICRA Conference 2010 Conference Paper

Superhuman performance of surgical tasks by robots using iterative learning from human-guided demonstrations

• Jur van den Berg
• Stephen Miller
• Daniel Duckworth
• Humphrey Hu
• Andrew Wan
• Xiao-Yu Fu
• Ken Goldberg
• Pieter Abbeel

In the future, robotic surgical assistants may assist surgeons by performing specific subtasks such as retraction and suturing to reduce surgeon tedium and reduce the duration of some operations. We propose an apprenticeship learning approach that has potential to allow robotic surgical assistants to autonomously execute specific trajectories with superhuman performance in terms of speed and smoothness. In the first step, we record a set of trajectories using human-guided backdriven motions of the robot. These are then analyzed to extract a smooth reference trajectory, which we execute at gradually increasing speeds using a variant of iterative learning control. We evaluate this approach on two representative tasks using the Berkeley Surgical Robots: a figure eight trajectory and a two handed knot-tie, a tedious suturing sub-task required in many surgical procedures. Results suggest that the approach enables (i) rapid learning of trajectories, (ii) smoother trajectories than the human-guided trajectories, and (iii) trajectories that are 7 to 10 times faster than the best human-guided trajectories.

IROS Conference 2009 Conference Paper

Developing visual sensing strategies through next best view planning

• Enrique Dunn
• Jur van den Berg
• Jan-Michael Frahm

We propose an approach for acquiring geometric 3D models using cameras mounted on autonomous vehicles and robots. Our method uses structure from motion techniques from computer vision to obtain the geometric structure of the scene. To achieve an efficient goal-driven resource deployment, we develop an incremental approach, which alternates between an accuracy-driven next best view determination and recursive path planning. The next best view is determined by a novel cost function that quantifies the expected contribution of future viewing configurations. A sensing path for robot motion towards the next best view is then achieved by a cost-driven recursive search of intermediate viewing configurations. We discuss some of the properties of our view cost function in the context of an iterative view planning process and present experimental results on a synthetic environment.

IROS Conference 2009 Conference Paper

Generalized velocity obstacles

• David Wilkie
• Jur van den Berg
• Dinesh Manocha

We address the problem of real-time navigation in dynamic environments for car-like robots. We present an approach to identify controls that will lead to a collision with a moving obstacle at some point in the future. Our approach generalizes the concept of velocity obstacles, which have been used for navigation among dynamic obstacles, and takes into account the constraints of a car-like robot. We use this formulation to find controls that will allow collision free navigation in dynamic environments. Finally, we demonstrate the performance of our algorithm on a simulated car-like robot among moving obstacles.

IROS Conference 2009 Conference Paper

Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles

• Jamie Snape
• Jur van den Berg
• Stephen J. Guy
• Dinesh Manocha

We present an approach for smooth and collision-free navigation of multiple mobile robots amongst each other. Each robot senses its surroundings and acts independently without central coordination or communication with other robots. Our approach uses both the current position and the velocity of other robots to predict their future trajectory in order to avoid collisions. Moreover, our approach is reciprocal and avoids oscillations by explicitly taking into account that the other robots also sense their surroundings and change their trajectories accordingly. We build on prior work related to velocity obstacles and reciprocal velocity obstacles and introduce the concept of hybrid reciprocal velocity obstacles for collision avoidance that takes into account the kinematics of the robots and uncertainty in sensor data. We apply our approach to a set of iRobot Create robots using centralized sensing and show natural, direct, and collision-free navigation in several challenging scenarios.

ICRA Conference 2008 Conference Paper

Reciprocal Velocity Obstacles for real-time multi-agent navigation

• Jur van den Berg
• Ming Lin 0003
• Dinesh Manocha

In this paper, we propose a new concept — the ‘Reciprocal Velocity Obstacle’— for real-time multi-agent navigation. We consider the case in which each agent navigates independently without explicit communication with other agents. Our formulation is an extension of the Velocity Obstacle concept [3], which was introduced for navigation among (passively) moving obstacles. Our approach takes into account the reactive behavior of the other agents by implicitly assuming that the other agents make a similar collision-avoidance reasoning. We show that this method guarantees safe and oscillation-free motions for each of the agents. We apply our concept to navigation of hundreds of agents in densely populated environments containing both static and moving obstacles, and we show that real-time and scalable performance is achieved in such challenging scenarios.

IROS Conference 2007 Conference Paper

Efficient path planning in changing environments

• Dennis Nieuwenhuisen
• Jur van den Berg
• Mark H. Overmars

This paper addresses the problem of path planning in environments in which some of the obstacles can change their positions. It uses the popular PRM method for navigating a robot through an environment. One of the key features of PRM is that it moves the major part of the calculations involved in the path planning process to the preprocessing phase. After that, paths can be extracted very quickly (in a query phase) usually without any noticeable delay. While very successful in many applications, doing most of the work in a preprocessing phase restricts the environment to be static i. e. obstacles are not allowed to change their configurations after the preprocessing phase. In this paper we describe and evaluate an algorithm based on PRM that does allow obstacles to change their configuration after preprocessing while still allowing for a quick query phase.

IROS Conference 2007 Conference Paper

Kinodynamic motion planning on roadmaps in dynamic environments

• Jur van den Berg
• Mark H. Overmars

In this paper we present a new method for kinodynamic motion planning in environments that contain both static and moving obstacles. We present an efficient two-stage approach: in the preprocessing phase, it constructs a roadmap that is collision-free with respect to the static obstacles and encodes the kinematic constraints on the robot. In the query phase, it plans a time-optimal path on the roadmap that obeys the dynamic constraints (bounded acceleration, curvature derivative) on the robot and avoids collisions with any of the moving obstacles. We do not put any constraints on the motions of the moving obstacles, but we assume that they are completely known when a query is performed. We implemented our method, and experiments confirm its good performance.

ICRA Conference 2006 Conference Paper

Anytime Path Planning and Replanning in Dynamic Environments

• Jur van den Berg
• Dave Ferguson 0001
• James J. Kuffner

We present an efficient, anytime method for path planning in dynamic environments. Current approaches to planning in such domains either assume that the environment is static and replan when changes are observed, or assume that the dynamics of the environment are perfectly known a priori. Our approach takes into account all prior information about both the static and dynamic elements of the environment, and efficiently updates the solution when changes to either are observed. As a result, it is well suited to robotic path planning in known or unknown environments in which there are mobile objects, agents or adversaries

IROS Conference 2005 Conference Paper

Creating robust roadmaps for motion planning in changing environments

• Jur van den Berg
• Dennis Nieuwenhuisen
• Leonard Jaillet
• Mark H. Overmars

In this paper we introduce a method based on the probabilistic roadmap (PRM) planner to construct robust roadmaps for motion planning in changing environments. PRM's are usually aimed at static environments. In reality though, many environments are not static, but contain moving obstacles as well. Often the motion of these obstacles is not unconstrained, but is restricted to some confined area, e. g. a door that can be open or closed or a chair which is bounded to a room. We exploit this observation by assuming that a moving obstacle has a predefined set of potential placements. We present a variant of PRM that is robust against placement changes of obstacles. Our method creates a roadmap that is guaranteed to contain a path for any feasible query when time goes to infinity, i. e. the method is probabilistically complete. Our implementation shows that after a roadmap is created in the preprocessing phase, queries can be solved instantaneously, thus allowing for on-the-fly replanning to anticipate changes in the environment.

IROS Conference 2005 Conference Paper

Prioritized motion planning for multiple robots

• Jur van den Berg
• Mark H. Overmars

In this paper we address the problem of motion planning for multiple robots. We introduce a prioritized method, based on a powerful method for motion planning in dynamic environments, recently developed by the authors. Our approach is generically applicable: there is no limitation on the number of degrees of freedom of each of the robots, and robots of various types - for instance free-flying robots and articulated robots - can be used simultaneously. Results show that high-quality paths can be produced in less than a second of computation time, even in confined environments involving many robots. We examine three issues in particular in this paper: the assignment of priorities to the robots, the performance of prioritized planning versus coordinated planning, and the influence of the extent by which the robot motions are constrained on the performance of the method. Results are reported in terms of both running time and the quality of the paths produced.

IROS Conference 2004 Conference Paper

Roadmap-based motion planning in dynamic environments

• Jur van den Berg
• Mark H. Overmars

In this paper a new method is presented for motion planning in dynamic environments, that is, finding a trajectory for a robot in a scene consisting of both static and dynamic, moving obstacles. We propose a practical algorithm based on a roadmap that is created for the static part of the scene. On this roadmap an approximate time-optimal trajectory from a start to a goal configuration is computed, such that the robot does not collide with any moving obstacle. The trajectory is found by performing a search for a shortest path on an implicit grid in state-time space. The approach is applicable to any robot type in configuration spaces with any dimension, and the motions of the dynamic obstacles are unconstrained, as long as they are known beforehand. The approach has been implemented for a free-flying robot in a three-dimensional workspace and experiments show that the method achieves interactive performance in complex environments.

ICRA Conference 2004 Conference Paper

Using Workspace Information as a Guide to Non-uniform Sampling in Probabilistic Roadmap Planners

• Jur van den Berg
• Mark H. Overmars

The probabilistic roadmap (PRM) planner is a popular method for robot motion planning problems with many degrees of freedom. However, it has been shown that the method performs less well in situations where the robot has to pass through a narrow passage in the scene. This is mainly due to the uniformity of the sampling used in the planner; it places many samples in large open regions and too few in tight passages. A technique based on a robot independent cell decomposition of the free workspace is proposed to guide the probabilistic sampling, such that the distribution of samples tends more toward the interesting regions in the scene. It is shown that this leads to improved performance on difficult planning problems in 2D and 3D workspaces.