Mark H. Overmars

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 2007 Conference Paper

The Corridor Map Method: Real-Time High-Quality Path Planning

• Roland Geraerts
• Mark H. Overmars

A central problem in robotics is planning a collision-free path for a moving object in an environment with obstacles. Contemporary applications require a path planner that is fast (to ensure real-time interaction with the environment) and flexible (to avoid local hazards). In addition, paths need to be smooth and short. We propose a new framework, the corridor map method, which meets these requirements.

IROS Conference 2006 Conference Paper

Creating High-quality Roadmaps for Motion Planning in Virtual Environments

• Roland Geraerts
• Mark H. Overmars

Our goal is to create road maps that are particularly suited for motion planning in virtual environments. We use our reachability roadmap method to compute an initial, resolution complete roadmap. This roadmap is small which keeps query times and memory consumption low. However, for use in virtual environments, there are additional criteria that must be satisfied. In particular, we require that the roadmap contains useful cycles. These provide short paths and alternative routes which allow for variation in the routes a moving object can take. We will show how to incorporate such cycles. In addition, we provide high-clearance paths by retracting the edges of the roadmap to the medial axis. Since all operations are performed in a preprocessing phase, high-quality paths can be extracted in real-time as is required in interactive applications

ICRA Conference 2006 Conference Paper

Pushing using Compliance

• Dennis Nieuwenhuisen
• A. Frank van der Stappen
• Mark H. Overmars

This paper addresses the problem of maneuvering an object by pushing it through an environment with obstacles. Instead of only pushing the object through open spaces, we also allow it to use compliance, e. g. allowing it to slide along obstacle boundaries. The advantage of using compliance is twofold: compliance does not only extend the number of situations in which a push plan can be found, it also allows for simpler (i. e. less complicated) paths in many cases. Here, we present an approach based on the rapidly-exploring random tree (RRT) algorithm that, besides paths through the open space, exploits the power of compliance

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

On improving the clearance for robots in high-dimensional configuration spaces

• Roland Geraerts
• Mark H. Overmars

In robot motion planning, many algorithms have been proposed that create a path for a robot in an environment with obstacles. Since it can be hard to create such paths, most algorithms are aimed at finding a solution. However, for most applications the paths must be of a good quality as well. That is, paths should preferably be short, be smooth, and should preserve some clearance from the obstacles. In this paper, we focus on improving the clearance of paths. Existing methods only extract high clearance paths for rigid, translating bodies. We present an algorithm that improves the clearance along paths of a broader range of robots which may reside in arbitrary high-dimensional configuration spaces. Examples include planar, free-flying and articulated robots.

IROS Conference 2005 Conference Paper

Path planning for pushing a disk using compliance

• Dennis Nieuwenhuisen
• A. Frank van der Stappen
• Mark H. Overmars

We consider the path planning problem for a robot that pushes a disk shaped object in an environment among obstacles. Instead of only allowing the object to move through the free space, we also allow the object to slide along the boundaries of the environment using compliance, extending the possibilities for the robot to find a push path. We present an exact algorithm that, given a path for the object consisting of k sections, preprocesses the environment consisting of n non-intersecting line segments in O(n/sup 2/ log n) and reports a push path in O(kn log n) time or reports failure if no path exists. Under the weak assumption of low obstacle density, the query time is reduced to O((k + n) log n).

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.

ICRA Conference 2005 Conference Paper

Reachability Analysis of Sampling Based Planners

• Roland Geraerts
• Mark H. Overmars

The last decade, sampling based planners like the Probabilistic Roadmap Method have proved to be successful in solving complex motion planning problems. We give a reachability based analysis for these planners which leads to a better understanding of the success of the approach and enhancements of the techniques suggested. This also enables us to study the effect of using new local planners.

ICRA Conference 2004 Conference Paper

Clearance based Path Optimization for Motion Planning

• Roland Geraerts
• Mark H. Overmars

Many motion planning techniques, like the probabilistic roadmap method (PRM), generate low quality paths. In this paper, we study a number of different quality criteria on paths in particular length and clearance. We describe a number of techniques to improve the quality of paths. These are based on a new approach to increase the path clearance. Experiments showed that the heuristics were able to generate paths of a much higher quality than previous approaches.

SODA Conference 2004 Conference Paper

Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks

• Pankaj K. Agarwal
• Mark H. Overmars
• Micha Sharir

ICRA Conference 2004 Conference Paper

Motion Planning for Camera Movements

• Dennis Nieuwenhuisen
• Mark H. Overmars

Moving a camera through a (virtual or real) environment is a complicated task. Often a user is given direct control of the camera. Such direct control is difficult for inexperienced users and results in rather ugly camera motions that easily lead to motion sickness. In this paper we describe a new technique for automatic generation of camera motion using motion planning techniques from robotics. We focus here on motion in virtual environments. In our approach the user simply specifies a required goal position (and orientation) using e. g. a map, and the system automatically computes a smooth, collision free motion from the current position and orientation to the required position (and orientation) that can be used by the camera. As preprocessing, the approach uses the probabilistic roadmap method to compute a roadmap through the environment. When a motion is required, a path is obtained from the roadmap which is then improved by various smoothing techniques to satisfy constraints from cinematography.

ICRA Conference 2004 Conference Paper

Motion Planning for Coherent Groups of Entities

• Arno Kamphuis
• Mark H. Overmars

Motion planning for multiple entities is a challenging problem in today's virtual environments. In this paper we develop an innovative approach to motion planning for groups of entities, where coherence is taken into account. We model the group by a deformable shape. Next, we use the Probabilistic Roadmap Method to plan the (global) motion of the shape. For this, we, develop new sampling techniques and local planners. A new approach, called Group Potential Fields, is also introduced as a means to determine the local motions of the entities inside the deformable shape. Global and local motions are then combined to find the required paths for the entities. Experiments show that the approach is able to find paths for groups of varying sizes, after limited preprocessing time, where the groups stay coherent.

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

Useful Cycles in Probabilistic Roadmap Graphs

• Dennis Nieuwenhuisen
• Mark H. Overmars

Over the last decade, the probabilistic road map method (PRM) has become one of the dominant motion planning techniques. Due to its random nature, the resulting paths tend to be much longer than the optimal path despite the development of numerous smoothing techniques. Also, the path length varies a lot every time the algorithm is executed. We present a new technique that results in higher quality (shorter) paths with much less variation between the executions. The technique is based on adding useful cycles to the roadmap graph.

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.

ICRA Conference 2002 Conference Paper

Fixturing Hinged Polygons

• Jae-Sook Cheong
• Ken Goldberg
• Mark H. Overmars
• A. Frank van der Stappen

We study the problem of fixturing a chain of hinged objects in a given placement with frictionless point contacts. We define the notions of immobility and robust immobility - which are comparable to the second and first order immobility for a single object - to capture the intuitive requirement for the fixture of a chain of hinged objects. Robust immobility differs from immobility in that it additionally requires insensitivity to small perturbations of contacts. We show that (p+2) frictionless point contacts can immobilize any chain of p/spl ne/3 polygons without parallel edges; six contacts can immobilize any chain of three such polygons. Any chain of p arbitrary polygons can be immobilized with at most (p+4) contacts. We also show that /spl lceil/(6/5)(p+2)/spl rceil/ contacts suffice to robustly immobilize p polygons without parallel edges, and that /spl lceil/(5/4)(p+2)/spl rceil/ contacts can robustly immobilize p/spl ne/3 arbitrary polygons, and eight contacts can robustly immobilize three polygons.

ICRA Conference 2002 Conference Paper

Sensorless Orientation of 3D Polyhedral Parts

• Robert-Paul Berretty
• Mark H. Overmars
• A. Frank van der Stappen

A common task in automated manufacturing processes is to orient parts prior to assembly. We consider sensorless orientation of an asymmetric polyhedral part by a sequence of push actions, and show that is it possible to move any such part from an unknown initial orientation into a known final orientation if these actions are performed by a jaw consisting of two orthogonal planes. We also show how to compute an orienting sequence of push actions. We propose a three-dimensional generalization of conveyor belts with fences consisting of a sequence of tilted plates with curved tips; each of the plates contains a sequence of fences. We show that it is possible to compute a set-up of plates and fences for any given asymmetric polyhedral part such that the part gets oriented on its descent along plates and fences.

ICRA Conference 2001 Conference Paper

Motion Planning in Environments with Dangerzones

• Danielle Sent
• Mark H. Overmars

This paper addresses the problem of path planning for a free-flying object in a (three-dimensional) environment that contains both obstacles and so-called danger zones. The path should (obviously) avoid collisions with the obstacles. The path is allowed to intersect with the danger zones, but this should be avoided as much as possible. We show that under some mild conditions, a path always exists in which the moving object never completely penetrates the danger zones. Based on this result we present a probabilistically complete roadmap method that finds such paths. The methods has been implemented and some experimental results are given.

ICRA Conference 2001 Conference Paper

Orienting Parts by Inside-out Pulling

• Robert-Paul Berretty
• Ken Goldberg
• Mark H. Overmars
• A. Frank van der Stappen

A common task in automated manufacturing processes is that of orienting (or feeding) parts prior to assembly. We propose a new type of feeder. We consider sensorless orientation of polygonal parts with elevated edges by pull actions with an overhead finger. We show that any asymmetric convex polygonal part can be oriented by a sequence of pull operations. We give an O(n/sup 3/) algorithm to compute the shortest sequence of pull operations to orient a convex polygonal part with n vertices, if such a sequence exists. We also show that there exist non-convex parts that cannot be fed by a sequence of pull operations.

ICRA Conference 2000 Conference Paper

The Toppling Graph: Designing Pin Sequences for Part Feeding

• Mike Tao Zhang
• Gordon Smith
• Robert-Paul Berretty
• Mark H. Overmars
• Ken Goldberg

We consider a sensorless approach to feeding parts on a conveyor belt using pins (rigid barriers) to topple parts into desired orientations. Given the 2D projection of an n-sided convex polyhedral part, its center of mass, and coefficients of friction, we give an O(n/sup 2/) algorithm to compute the "toppling graph", a new data structure that represents the mechanics of toppling, including rolling and jamming. The toppling graph can be used to identify critical pin heights that permit toppling. We compare pin heights predicted by the graph with physical experiments, and give a complete O(n/sup 3n/) algorithm for designing pin sequences.

ICRA Conference 1999 Conference Paper

Computing Form-Closure Configurations

• A. Frank van der Stappen
• Chantal Wentink
• Mark H. Overmars

We present the first output-sensitive algorithm for computing all placements of four (frictionless) points that put a polygonal part in form closure. Our efficient algorithm runs in O(n/sup 2+/spl epsiv//+K) time, where n is the number of vertices of the polygon, K is the description size of the set of form closure placements, and /spl epsiv/ is an arbitrarily small constant. The basis of our algorithm is a translation of the problem into geometric searching problems, which are solved with the use of efficient data structures. Our results can be extended to the problem of computing all placements of a line and two points that put a polygonal part in form closure. The resulting algorithm runs in O(n/sup 2/ log/sup 2/ n+K) time, where K is again the description size of the output.

SODA Conference 1999 Conference Paper

Locked and Unlocked Polygonal Chains in 3D

• Therese C. Biedl
• Erik D. Demaine
• Martin L. Demaine
• Sylvain Lazard
• Anna Lubiw
• Joseph O'Rourke
• Mark H. Overmars
• Steve Robbins

ICRA Conference 1999 Conference Paper

The Gaussian Sampling Strategy for Probabilistic Roadmap Planners

• Valérie Boor
• Mark H. Overmars
• A. Frank van der Stappen

Probabilistic roadmap planners (PRMs) form a relatively new technique for motion planning that has shown great potential. A critical aspect of PRM is the probabilistic strategy used to sample the free configuration space. In this paper we present a new, simple sampling strategy, which we call the Gaussian sampler, that gives a much better coverage of the difficult parts of the free configuration space. The approach uses only elementary operations which makes it suitable for many different planning problems. Experiments indicate that the technique is very efficient indeed.

ICRA Conference 1999 Conference Paper

Trap Design for Vibratory Bowl Feeders

• Robert-Paul Berretty
• Ken Goldberg
• Lawrence Cheung
• Mark H. Overmars
• Gordon Smith
• A. Frank van der Stappen

The vibratory bowl feeder is the oldest and still most common approach to the automated feeding (orienting) of industrial parts. We consider a class of vibratory bowl filters that can be described by removing polygonal sections from the track; we refer to this class of filters as traps. For an n-sided convex polygonal part and m-sided convex polygonal trap, we give an O((n+m)log(n+m)) algorithm to decide if the part will be rejected by the trap, and an O((nm(n+m))/sup 1+/spl epsiv//) algorithm which deals with non-convex parts and traps. We then consider the problem of designing traps for a given part, and consider two rectilinear subclasses, balconies and gaps. We give linear and O(n/sup 2/) algorithms for designing feeders and have tested the results with physical experiments using a commercial inline vibratory feeder.

ICRA Conference 1995 Conference Paper

Coordinated Motion Planning for Multiple Car-Like Robots Using Probabilistic Roadmaps

• Petr Svestka
• Mark H. Overmars

Presents a new approach to the multi-robot path planning problem, where a number of robots are to change their positions through feasible motions in the same static environment. The approach is probabilistically complete. That is, any solvable problem is guaranteed to be solved within a finite amount of time. The method, which is an extension of previous work on probabilistic single-robot planners, is very flexible in the sense that it can easily be applied to different robot types. In this paper the authors apply it to non-holonomic car-like robots, and present experimental results which show that the method is powerful and fast.

FOCS Conference 1990 Conference Paper

Hidden Surface Removal for Axis-Parallel Polyhedra (Extended Abstract)

• Mark de Berg
• Mark H. Overmars

An efficient, output-sensitive method for computing the visibility map of a set of axis-parallel polyhedra (i. e. polyhedra with their faces and edges parallel to the coordinate axes) as seen from a given viewpoint is introduced. For nonintersecting polyhedra with n edges in total, the algorithm runs in time O((n+k)log n), where k is the complexity of the visibility map. The method can handle cyclic overlap of the polyhedra and perspective views without any problem. For c-oriented polyhedra (with faces and edges in c orientations, for some constant c) the method can be extended to run in the same time bound. The method can be extended even further to deal with intersecting polyhedra with only a slight increase in the time bound. >

FOCS Conference 1989 Conference Paper

Output-Sensitive Hidden Surface Removal

• Mark H. Overmars
• Micha Sharir

Several output-sensitive algorithms for hidden surface removal in a collection of n horizontal triangles, viewed from a point at z=- infinity, are derived. If k is the combinatorial complexity of the output visibility map, then the result is a simple (deterministic) algorithm that runs in time O(n square root k log n) and several improved and more sophisticated algorithms that use randomization. One of these algorithms runs in time O(n/sup 4/3/log /sup gamma /n+k/sup 3/5/n/sup 4/5+ delta /) for any delta >0, where gamma is some constant less than 3. The performance of the other algorithms is potentially even faster; it depends on other parameters of the structure of the given triangles, as well as on the output size. A variant of the simple algorithm performs hidden surface removal for n (nonintersecting) balls in time O(n/sup 3/2/log n+k). >

FOCS Conference 1988 Conference Paper

New upper bounds in Klee's measure problem (extended abstract)

• Mark H. Overmars
• Chee-Keng Yap

New upper bounds are given for the measure problem of V. Klee (1977) that significantly improve the previous bounds for dimensions greater than 2. An O(n/sup d/2/ log n, n) time-space upper bound to compute the measure of a set of n boxes in Euclidean d-space is obtained. The solution requires several novel ideas including application of the inclusion/exclusion principle, the concept of trellises, streaming, and a partition of d-space. >

MFCS Conference 1981 Invited Paper

The Art of Dynamizing

• Jan van Leeuwen
• Mark H. Overmars

Abstract A few years ago J. Bentley initiated a general approach to searching problems and their solution by means of dynamic data structures. As it is often easier to find a static solution first, his goal was to obtain efficient dynamic data structures by applying transformations to static data structures. This approach has become a paradigm (known as "dynamization") in current research in the design of efficient algorithms. We shall outline a number of general techniques that were developed for dynamizing decomposable searching problems and will discuss a recent solution to Bentley's original question to devise a dynamization method for such problems with worst-case optimal insertion and deletion routines.

STOC Conference 1980 Conference Paper

Dynamically Maintaining Configurations in the Plane (Detailed Abstract)

• Mark H. Overmars
• Jan van Leeuwen