Recent advancements in local methods have significantly improved the collision avoidance behavior of virtual characters. However, existing methods fail to take into account that in real life pedestrians tend to walk in small groups, consisting mainly of pairs or triples of individuals. We present a novel approach to simulate the walking behavior of such small groups. Our model describes how group members interact with each other, with other groups and individuals. We highlight the potential of our method through a wide range of test-case scenarios. We evaluate the results from our simulations using a number of quantitative quality metrics, and also provide visual and numerical comparisons with video footages of real crowds.

Recent advancements in local methods have significantly improved the collision avoidance behaviour of virtual characters. However, existing methods fail to take into account that in real-life pedestrians tend to walk in small groups, consisting mainly of pairs or triples of individuals. We present a novel approach to simulate the walking behaviour of such small groups. Our model describes how group members interact with each other, with other groups and individuals. We highlight the potential of our method through a wide range of test-case scenarios. A number of metrics are also proposed to quantitatively evaluate the quality of our proposed model.

Abstract Virtual humans are employed in many interactive applications using 3D virtual environments, including (serious) games. The motion of such virtual humans should look realistic (or ‘natural’) and allow interaction with the surroundings and other (virtual) humans. Current animation techniques differ in the trade‐off they offer between motion naturalness and the control that can be exerted over the motion. We show mechanisms to parametrize, combine (on different body parts) and concatenate motions generated by different animation techniques. We discuss several aspects of motion naturalness and show how it can be evaluated. We conclude by showing the promise of combinations of different animation paradigms to enhance both naturalness and control.

An important challenge in virtual environment applications is to steer virtual characters through complex and dynamic worlds. The characters should be able to plan their paths and move toward their desired locations, avoiding at the same time collisions with the environment and with other moving entities. In this paper we propose a general method for realistic path planning, the Indicative Route Method (irm). In the irm, a so-called indicative route determines a global route for the character, whereas a corridor around this route is used to handle a broad range of other path planning issues, such as avoiding characters and computing smooth paths. As we will show, our method can be used for real-time navigation of many moving characters in complicated environments. It is fast, flexible and generates believable paths.

This issue contains a selection of the best papers of the workshop Motion in Games that was held in Utrecht last June.It contains also a regular paper on Combined Compression and Simplification of Dynamic 3D Meshes by Libor Vasa and Vaklav Scala from the University of West Bohemia in Pilsen in Czech Republic.The paper deals with a new approach to dynamic mesh compression, which combines compression with simplification to achieve improved compression results, a natural support for incremental transmission and level of detail.The algorithm allows fast progressive transmission of dynamic 3D content.

Abstract Path planning in computer games, whether these are serious or entertainment games, plays an important role in the immersion of a player. Recently, the concept of path planning inside corridors has been introduced and a novel approach under the name Corridor Map Method (CMM) has been proposed. In this paper, we extend the original CMM by creating alternative paths that a character can follow within a corridor. This not only presents a more challenging and less predictable opponent for the player, but also enhances the realism of the gaming and/or training experience. We also discuss how variation in the speed of the animated characters can be integrated into our extended framework, leading to convincing characters that exhibit human like path planning. Copyright © 2008 John Wiley & Sons, Ltd.

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.

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.

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.

Abstract In many virtual environment applications, paths have to be planned for characters to traverse from a start to a goal position in the virtual world while avoiding obstacles. Contemporary applications require a path planner that is fast (to ensure real‐time interaction with the environment) and flexible (to avoid local hazards such as small and dynamic obstacles). In addition, paths need to be smooth and short to ensure natural looking motions. Current path planning techniques do not obey these criteria simultaneously. For example, A* approaches generate unnatural looking paths, potential field‐based methods are too slow, and sampling‐based path planning techniques are inflexible. We propose a new technique, the Corridor Map Method (CMM), which satisfies all the criteria. In an off‐line construction phase, the CMM creates a system of collision‐free corridors for the static obstacles in an environment. In the query phase, paths can be planned inside the corridors for different types of characters while avoiding dynamic obstacles. Experiments show that high‐quality paths for single characters or groups of characters can be obtained in real‐time. Copyright © 2007 John Wiley & Sons, Ltd.

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 areas, we also allow it to use compliance, e.g., allowing it to slide along obstacle boundaries. Using compliance has a number of advantages: it extends the number of situations in which a manipulation plan can be found, it allows for simpler (i.e., less complicated) paths in many cases, and it often helps solving narrow-passage problems. Here, we present an approach based on rapidly-exploring random trees. Our approach yields paths through the open space, but also exploits the power of compliance.

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

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

Computer games play an increasingly important role, both in entertainment and in serious applications, like education, training, communication, decision support, and marketing. Games use the most modern technology (both in hardware and in software) and future games will greatly benefit from new developments in such technology.After an introduction into games and their future use, we will discuss the scientific challenges future games pose to researchers. Typical areas that will be treated are new modeling techniques, the design and behavior of virtual characters and avatars, simulating virtual worlds, and new interaction and interface techniques.

Let S be a set of n points in $\reals^2$. Given an integer $1 \le k \le n$, we wish to find a maximally separated subset $I \subseteq S$ of size k; this is a subset for which the minimum among the ${k\choose 2}$ pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists $I\subseteq S$, $|I|=k$, so that all ${k\choose 2}$ pairwise distances in I are at least 2. This problem can also be formulated in terms of disk‐intersection graphs: Let D be the set of unit disks centered at the points of S. The disk‐intersection graph G of D has as edges all pairs of disks with nonempty intersection. Any set I with the above properties is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NP‐complete if k is part of the input. In this paper we first present a linear‐time $\eps$‐approximation algorithm for any constant k. Next we give exact algorithms for the cases $k=3$ and $k=4$ that run in time $O(n^{4/3}\polylog(n))$. We also present a simpler $n^{O(\sqrt{k})}$‐time exact algorithm (as compared with the recent algorithm in [J. Alber and J. Fiala, J. Algorithms, 52 (2004), pp. 134–151]) for arbitrary values of k.

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.

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.

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.

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.

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).

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 approximately 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 two-level search for a shortest path. On the local level, trajectories on single edges of the roadmap are found using a depth-first search on an implicit grid in state-time space. On the global level, these local trajectories are coordinated using an A/sup */-search to find a global trajectory to the goal configuration. 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 both free-flying and articulated robots in three-dimensional workspaces, and it has been applied to multirobot motion planning, as well. Experiments show that the method achieves interactive performance in complex environments.

info:eu-repo/semantics/published

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Geometric algorithms have successfully been applied to solve or give insight into problems in robotic manipulation. In this paper, we present a framework to filter polygonal parts on a track. The filter consists of a polygonal hole in the track; we refer to the filters as traps. For an n-sided polygonal part and an m-sided polygonal trap, we give an O((nm(n + m)) 1+ffl ) algorithm to decide whether the part in a specific orientation will safely move across the trap or will fall through the trap and thus be filtered out. Furthermore, we show how to design various parameterized traps, ranging from simple gaps to arbitrary polygons which will filter out all but one of the different stable orientations of a given part. 1 Introduction Geometric algorithms are important tools to solve or give insight into real world problems. In this paper, we transform the problem of designing traps into geometric problems, which are then solved with the use of techniques from computational geometry. ...

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.

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.

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.

A common task in automated manufacturing processes is to orient parts prior to assembly. We consider sensorless orientation of a polygonal part by a sequence of push actions. We show that any polygonal part can be oriented by a sequence of fences placed along a conveyor belt, thereby settling a conjecture by Wiegley et al. [25], and present the first polynomial-time algorithm to compute the shortest such sequence. The algorithm is simple and runs in time O(n 3 log n), where n is the number of vertices of the part. Even though pathological parts can be constructed that require \\Omega\\Gamma n) push actions, it turns out that almost all parts can be oriented using a small number of pushes. We deduce a new bound on the length of the shortest push plan that depends on the thinness -- or eccentricity -- of the part. The bound shows that only O(1) pushes are required for the large class of parts with non-square minimum-width bounding boxes. 1 Introduction Many automated manufacturing pro...

In this paper we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack. We do this by performing a depth-first search on the subdivision, using local criteria for deciding what is the next cell to visit. Our method is extremely simple and provably correct. The algorithm has applications in the field of geographic information systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible. We show how to adapt our algorithm to answer related queries, such as windowing queries and reporting connected subsets of cells that have a common attribute. Finally, we show how to extend our algorithm such that it can handle convex threedimensional subdivisions.

The motion planning problem requires that a collision-free path be determined for a robot moving amidst a fixed set of obstacles. Most neural network approaches to this problem are for the situation in which only local knowledge about the configuration space is available. The main goal of the paper is to show that neural networks are also suitable tools in situations with complete knowledge of the configuration space. In this paper we present an approach that combines a neural network and deterministic techniques. We define a colored version of Kohonen's self-organizing map that consists of two different classes of nodes. The network is presented with random configurations of the robot and, from this information, it constructs a road map of possible motions in the work space. The map is a growing network, and different nodes are used to approximate boundaries of obstacles and the Voronoi diagram of the obstacles, respectively. In a second phase, the positions of the two kinds of nodes are combined to obtain the road map. In this way a number of typical problems with small obstacles and passages are avoided, and the required number of nodes for a given accuracy is within reasonable limits. This road map is searched to find a motion connecting the given source and goal configurations of the robot. The algorithm is simple and general; the only specific computation that is required is a check for intersection of two polygons. We implemented the algorithm for planar robots allowing both translation and rotation and experiments show that compared to conventional techniques it performs well, even for difficult motion planning scenes.

In this note we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack.We do this by performing a depth-first search on the subdivision, using local criteriafor deciding what is the next cell to visit.Our method is extremely simple.The algorithm has applications in the field of Geographic Information Systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible.We can adapt our algorithm to answer related queries, such as windowing queries, reporting connected subsets of cells that have a common attribute, and reporting in 3-dimensional convex subdivisions.

A new motion planning method for robots in static workspaces is presented. This method proceeds in two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace. But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (/spl ap/150 MIPS), after learning for relatively short periods of time (a few dozen seconds).

No abstract available.

A familiar task in inclu.striala~)l>lications is gras~jing

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.

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region Rα(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of Rα(S) is O(nα5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

We devise techniques to manipulate a collection of loosely interpenetrating spheres in three-dimensional space. Our study is motivated by the representation and manipulation of molecular configurations, modeled by a collection of spheres. We analyze the sphere model and point to its favorable properties that make it more easy to manipulate than an arbitrary collection of spheres. For this special sphere model we present efficient algorithms for computing its union boundary and for hidden surface removal. The efficiency and practicality of our approach are demonstrated by experiments on actual protein data.

We present an efficient and simple paradigm for motion planning amidst fat obstacles. The paradigm fits in the cell decomposition approach to motion planning and exploits workspace properties that follow from the fatness of the obstacles. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same (expectedly small) size. The approach applies to robots with any fixed number of degrees of freedom and turns out to be successful in many cases: it leads to nearly optimal O(nlogn) algorithms for motion planning in 2D, and for motion planning in 3D amidst obstacles of comparable size. In addition, we obtain algorithms for planning 3D motions among polyhedral obstacles, running in O(n2logn) time, and among arbitrary obstacles, running in time O(n3).

A depth order on a set of line segments in 3-space is an order such that line segment a comes before line segment $a'$ in the order when a lies below $a'$ or, in other words, when there is a vertical ray that first intersects $a'$ and then intersects a. Efficient algorithms for the computation and verification of depth orders of sets of n line segments in 3-space are presented. The algorithms run in time $O(n^{{4 / 3} + \varepsilon } )$, for any fixed $\varepsilon > 0$. If all line segments are axis-parallel or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in $O(n\log ^3 n)$, for any fixed $\varepsilon > 0$ time and the verification takes $O(n\log ^2 n)$ time. The algorithms can be generalized to handle triangles and other polygons instead of line segments. They are based on a general framework for computing and verifying linear orders extending implicitly defined binary relations.

A new data structure-the union-copy structure -is introduced, which generalizes the well-known union-find structure.Besides the usual union and find operations, the new structure also supports a copy operation, that generates a duplicate of a given set.The structure can enumerate a given set, find all sets that contain a given element, insert and delete elements, etc.All these operations can be performed very efficiently.The structure can be tuned as to obtain different trade-offs in the efficiency of the different operations.As an application of the union-copy structure, we give a dynamic version of the segment tree.Contrary to the classical semi-dynamic segment trees, the dynamic segment tree is not restricted to a fixed universe, from which the endpoints of the segments must be chosen.The tree allows for insertions, splits, and concatenations in O(log n)-time each.Deletions can be performed in slightly more time.

A depth order on a set of objects is an order such that object a comes before object a′ in the order when a′ lies behind a′, or, in other words, when a is (partially) hidden by a′ by a′. We present efficient algorithms for the computation and verification of depth orders of sets of n rods in 3–space. Our algorithms run in time O(n4/3+ε), for any fixed ε > 0). If all rods are axis-parallel, or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in O(n log2 n) time. The algorithms can be generalized to handle triangles and other polygons instead of rods. They are based on a general framework for computing and verifying linear extensions of implicitly defined binary relations.

An algorithm that solves the following motion-planning problem is presented. Given an L-shaped body L and a two-dimensional region with n point obstacles, decide whether there is a continuous motion connecting two given positions and orientations of L during which L avoids collision with the obstacles. The algorithm requires $O(n^2 \log ^2 n)$ time and $O(n^2 )$ storage. The algorithm is a variant of the cell-decomposition technique of the configuration space [D. Leven and M. Sharir, J. Algorithms, 8 (1987), pp. 192–215], [J. T. Schwartz and M. Sharir, Comm. Pure Appl. Math., 36 (1983), pp. 345–398], but it employs a new and efficient technique for obtaining a compact representation of the free space, which results in a saving of nearly an order of magnitude. The approach used in our algorithm is also applicable to motion planning of certain robotic arms whose spaces of free placements have a structure similar to that of the L-shaped body.

We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If k is the combinatorial complexity of the output visibility map , the method runs in time O(n √k log n). The method is extended to work for other classes of objects as well, sometimes with even improved time bounds. For example, we obtain an algorithm that performs hidden surface removal for n (nonintersecting) balls in time O(n 3/2 log n + k).

The following class of query problems is studied: Given a set of n arcs (disks, circles, circular arcs, Jordan arcs) in the plane, preprocess it into a data structure, such that for a query line (or segment) 1, one can quickly (i) report all arcs intersecting /?, or (ii) count the number of arcs intersecting L We also stud y the ray shooting problem for disjoint Jordan arcs and for circular arcs.Most of the data structures presented here use linear or near to linear space and have query time near to 0(/E+K) or 0(n2/3+K), where K is the size of the output.The query time of some of our algorithms can be improved by allowing more space.

No abstract available.

methods also apply to computing the vi;lbility map for a polyhedral terrain viewed from a fixed point, and yield O((rm(n) + k) log n) algorithms.

New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An $O(n^{d / 2} \log n,n)$ time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on a new data structure, which is called an orthogonal partition tree. This structure has other applications as well.

Let V be a set of objects in space for which we want to determine the portions visible from a particular point of view υ. Assume V is subdivided in subsets V1,…, Vz and the visibility maps Μ1, … Μz of these subsets from point ugr; are known. We show that the visibility map Μ for V can be computed by merging Μ1, … Μz in time Ο((n + κ)z log2 n) where n is the total size (number of edges, vertices and faces) of the visibility maps Μ1,…, Μz and κ is the size of Μ.

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.>

We present an algorithm that solves the following motion-planning problem. Given an L-shaped body L and a 2-dimensional region with n point obstacles, decide whether there is a continuous motion connecting two given positions and orientations of L during which L avoids collision with the obstacles. The algorithm requires Ο(n2 log2 n) time and Ο(n2) storage. The algorithm is a variant of the cell-decomposition technique of the configuration space ([SS, LS]) but it employs a new and efficient technique for obtaining a compact representation of the free space, which results in a saving of an order of magnitude. The approach used in our algorithm seems applicable to motion-planning of certain robotic arms whose spaces of free placements have a structure similar to that of the L-shaped body.

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).>

A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r > 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.

Let S be a set of n non-intersecting line segments in the plane. The visibility graph GS of S is the graph that has the endpoints of the segments in S as nodes and in which two nodes are adjacent whenever they can “see” each other (i.e., the open line segment joining them is disjoint from all segments or is contained in a segment). Two new methods are presented to construct GS. Both methods are very simple to implement. The first method is based on a new solution to the following problem: given a set of points, for each point sort the other points around it by angle. It runs in time Ο(n2). The second method uses the fact that visibility graphs often are sparse and runs in time Ο(m log n) where m is the number of edges in GS. Both methods use only Ogr;(n) storage.

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.>

First, we propose a general framework that captures many of the variations on visibility found in the literature. Second, we investigate two specific variations: rectangular and square visibility.

The range searching (or windowing) problem asks for an accommodation of a set of objects such that those objects that lie (partially) in a given axis-parallel rectangle can be reported efficiently. We solve the range searching problem for a set of n non-intersecting, but possibly touching, line segments in the plane and give a data structure that allows for range queries in Ο(k+ log2 n) time, where k is the number of reported answers. The structure is dynamic and allows for insertions and deletions of line segments in Ο(log2 n) time. The structure uses Ο(n log n) storage. The related problem of moving the window (range) parallel to one of the coordinate-axes, determining the first line segment that will become visible or stops being visible, is treated as well and similar bounds are obtained.

See figure1.1.for an example of a cut.A cut-3 sequence is a sequence of cuts such that, after the last cut we end with a piece that is the polygon P.

For a number of common configurations of points (lines) in the plane, we develop datastructures in which insertions and deletions of points (or lines, respectively) can be processed rapidly without sacrificing much of the efficiency of query answering of known static structures for these configurations. As a main result we establish a fully dynamic maintenance algorithm for convex hulls that can process insertions and deletions of single points in only O(log3n) steps or less per transaction, where n is the number of points currently in the set. The algorithm has several intriguing applications, including that one can “peel” a set of n points in only O(log3n) steps and that one can maintain two sets at a costs of only O(log3n) or less per insertion and deletion such that it never takes more than O(log2n) steps to determine whether the two sets are separable by a straight line. Also efficient algorithms are obtained for dynamically maintaining the common intersection of a set of half-spaces and for dynamically maintaining the maximal elements of a set of plane points. The results are all derived by means of one master technique, which is applied repeatedly and which seems to capture an appropriate notion of “decomposability” for configurations.