We consider the problem of planning the motion of a drone equipped with a robotic arm, tasked with bringing its end-effector up to many (150+) targets in a fruit tree; to inspect every piece of fruit, for example. The task is complicated by the intersection of a version of Neighborhood TSP (to find an optimal order and a pose to visit every target), and a robotic motion-planning problem through a planning space that features numerous cavities and narrow passages that confuse common techniques. In this contribution, we present a framework that decomposes the problem into two stages: planning approach paths for every target, and quickly planning between the start points of those approach paths. Then, we compare our approach by simulation to a more straightforward method based on multiquery planning, showing that our approach outperforms it in both time and solution cost.

We present a data-driven gaze animation method using recurrent neural networks. The neural network is trained with motion capture data including different poses such as standing, sitting, and lying down and is able to learn the constraints related with each particular pose. A simplified version of the neural network is also presented for Level of Detail (LOD) animation. We compare various neural network architectures and show that our method produces natural gaze motion in real-time. Results from a user study conducted among game industry professionals shows that our method has better perceived naturalness compared to the procedural gaze animation system of a well-known game company. Our approach is the first one to show the feasibility of gaze motions using deep neural networks.

Abstract We present a procedural audio‐driven speech animation method for interactive virtual characters. Given any audio with its respective speech transcript, we automatically generate lip‐synchronized speech animation that could drive any three‐dimensional virtual character. The realism of the animation is enhanced by studying the emotional features of the audio signal and its effect on mouth movements. We also propose a coarticulation model that takes into account various linguistic rules. The generated animation is configurable by the user by modifying the control parameters, such as viseme types, intensities, and coarticulation curves. We compare our approach against two lip‐synchronized speech animation generators. Our results show that our method surpasses them in terms of user preference.

Abstract With the growth in available computing power, we see increasingly crowded virtual environments. In densely crowded situations, collisions are likely to occur, and the choice in collision detection technique can impact the perceived realism of a real‐time crowd. This paper presents an investigation into the accuracy of human observers with regard to the recognition of collisions between virtual characters. We show the result of two user studies, where participants classify scenarios as “colliding” or “not colliding”; a pilot study investigates the perception of static images, whereas the main study expands on this by employing animated videos. In the pilot experiment, we investigated the effect of two variables on the ability to recognize collisions: distance between the character meshes and visibility of the inter‐character gap. In the main experiment, we investigate the angle between the character paths and the severity of the (near) collision. On average, respondents correctly classified 72% (static) and 68% (animated) of the scenarios. A notable result is that the maximum uncertainty in determining existence of collisions occurs when the characters are overlapping and that there is a significant bias towards answering “not colliding.” We also discuss differences in bias in the recognition of upper‐ and lower‐body collisions.

We study the problem of orienting a part with given admitted shape variations by means of pushing with a single frictionless jaw. We use a very general model for shape variations that is defined by two given convex polygons PI ⊆ PE. In this model, any valid instance must contain PI while it must be contained in PE. The problem that we solve is to determine, for a given h, the sequence of h push actions that puts all valid instances of a part with given shape variation into the smallest possible interval of final orientations. The resulting algorithm runs in O(hn) time, where n=|PI|+|PE|.

We present a novel dense crowd simulation method. In real crowds of high density, people manoeuvring the crowd need to twist their torso to pass between others. Our proposed method does not use the traditional disc-shaped agent, but instead employs capsule-shaped agents, which enables us to plan such torso orientations. Contrary to other crowd simulation systems, which often focus on the movement of the entire crowd, our method distinguishes between active agents that try to manoeuvre through the crowd, and passive agents that have no incentive to move. We introduce the concept of a focus point to influence crowd agent orientation. Recorded data from real human crowds are used for validation, which shows that our proposed model produces equivalent paths for 85 percent of the validation set. Furthermore, we present a character animation technique that uses the results from our crowd model to generate torso-twisting and side-stepping characters.

The papers included in this special section were presented at the 11th Workshop on the Algorithmic Foundations of Robotics (WAFR), which was held at Boğaziçi University, Istanbul, Turkey, during August 3–5, 2014.

In this paper we describe a novel technique for solving the inverse kinematics problem for human fingers. We derive a closed-form solution that places the fingertips precisely in the desired location by allowing minor deviations in the rotations of the Proximal Interphalangeal and Distal Interphalangeal joints compared to the fixed ratio that is known to exist between them. The obvious advantage is that with our approach there is no need to iterate until the distance between the fingertips and the desired locations is small enough. We show that this method is reliable and exact while showing minimal differences to the finger poses generated by the original closed-form solution. In our experiments we found the positions of the intermediate joints of the finger to deviate only around 1.5 mm in the worst case from those resulting from a numerical approximation of the original closed-form solution. On average the deviation is less than 0.5 millimeter.

In high-density crowds, one can observe torso twists; people rotate their upper body to decrease their width perpendicular to the motion path, in order to squeeze through narrow spaces between other crowd members. In this paper we investigate such behaviour, by recording and analysing dense crowds. Apart from the common approach, where only the position of each person in the crowd is recorded, we also record and analyse the torso orientations. To the best of our knowledge, this has not been done before in the context of dense crowds. We show that the paths chosen by the participants can be predicted by Generalized Voronoi Diagrams based on line segment representations of the participants' torsos, and attest that the medial axis of a capsule-shaped representation of the torso is a good choice for such line segments.

Metrology, the theoretical and practical study of measurement, has applications in automated manufacturing, inspection, robotics, surveying, and healthcare. The geometric probing problem considers how to optimally use a probe to measure geometric properties. In this paper, we consider a proximity probe which, given a point, returns the distance to the boundary of the nearest object. When there is an unknown convex polygon P in the plane, the goal is to minimize the number of probe measurement needed to exactly determine the shape and location of P. We present an algorithm with upper bound of 3.5n + k + 2 probes, where n is the number of vertices and k ≤ 3 is the number of acute angles of P. The algorithm requires constant time per probe, and hence, O(n) time to determine P. We also address the related problem where the unknown polygon is a member of a known finite set Γ and the goal is to efficiently determine which polygon is present. When m is the size of Γ and n' is the maximum number of vertices of any member of Γ, we present an algorithm with an upper bound of 2n + 2 probes with O(1) computations per probe and a O(n'm) preprocessing phase (depending only on Γ).

The papers in this special section were presented at the 11th Workshop on the Algorithmic Foundation of Robotics (WAFR), which was held at Boğaziçi University, Istanbul, Turkey, during August 3–5, 2014. WAFR is a prestigious biennial single-track workshop on algorithms for robotics and automation. It features cutting-edge research in a broad range of planning problems (such as manipulation, motion, path, multi-robot, and kynodynamic planning), geometric and topological computation, and novel applications like surgical planning, active sensing, and informative path planning.

The shape and center of mass of a part are crucial parameters to algorithms for planning automated manufacturing tasks. As industrial parts are generally manufactured to tolerances, the shape is subject to variations, which, in turn, also cause variations in the location of the center of mass. Planning algorithms should take into account both types of variation to prevent failure when the resulting plans are applied to manufactured incarnations of a model part. We study the relation between variation in part shape and variation in the location of the center of mass for a part with uniform mass distribution. We consider a general model for shape variation that only assumes that every valid instance contains a shape PIwhile it is contained in another shape PE. We characterize the worst-case displacement of the center of mass in a given direction in terms of PIand PE. The characterization allows us to determine an adequate outer approximation of the locus of the center of mass. We also show that the worst-case displacement is small if PIis convex and fat (that is, not long and thin) and the distance between the boundaries of PEand PIis bounded.

ABSTRACT Simulating a crowded scene like a busy shopping street requires tight packing of virtual characters. In such cases, collisions are likely to occur, and the choice in collision detection shape will influence how characters are allowed to intermingle. Full collision detection is too expensive for crowds, so simplifications are needed. The most common simplification, the fixed‐width, pose‐independent cylinder, does not allow intermingling of characters, as it will either cause too much empty space between characters or undetected penetrations. As a possible solution to this problem, we introduce the bounding cylinder hierarchy (BCH), a bounding volume hierarchy that uses vertical cylinders as bounding shapes. Because the BCH is a generalization of the single cylinder, we expect that this representation can be easily integrated with existing crowd simulation systems. We compare our BCH with commonly used collision shapes, namely the single cylinder and oriented bounding box tree, in terms of query time, construction time, and represented volume. To get an indication of possible crowd densities, we investigate how close characters can be before collision is detected and finally propose a critical maximum depth for the BCH. Copyright © 2014 John Wiley & Sons, Ltd.

A grasp g is said to achieve local force closure with respect to a given external wrench wext if g can resist wext as well as any wrench in some neighborhood of wext, with grasp quality no less than some threshold Q. Such grasps are particularly useful for tasks that do not require an object to be completely restrained: such as holding an object so that it does not fall, or picking up objects and dropping them into a container. If we allow the use of disc-fingers in contact with convex vertices of a polygonal object P, then any given wext acting on P can be resisted by a 2-finger grasp. We show how to compute the set of all 2-finger grasp configurations with contacts on given boundary features of P that are capable of resisting a given wext with quality at least Q. We also show that any grasp in the interior of such a grasp set achieves local force closure with respect to wext. By finding the largest square contained in such a grasp set we can obtain maximal independent contact regions for local force closure grasps of P with contacts on a given pair of features.

We present a muscle-based control method for simulated bipeds in which both the muscle routing and control parameters are optimized. This yields a generic locomotion control method that supports a variety of bipedal creatures. All actuation forces are the result of 3D simulated muscles, and a model of neural delay is included for all feedback paths. As a result, our controllers generate torque patterns that incorporate biomechanical constraints. The synthesized controllers find different gaits based on target speed, can cope with uneven terrain and external perturbations, and can steer to target directions.

We introduce the concept of Local Force Closure. We define a local force closure grasp as a grasp which is capable of resisting some given external wrench as well as (through local variation in contact wrenches) any wrench in some neighborhood of the given wrench, with grasp quality exceeding some given threshold. Local force closure is useful in applications where a grasp only needs to resist some given external wrench, rather than fully constraining object, but where there is some uncertainty regarding the exact external wrench that needs to be resisted, or where there is a possibility of having to cope with some (relatively small) unknown disturbance forces. We show that by allowing disc-shaped fingers in contact with convex vertices of a polygonal object, any given wrench can be resisted by just two frictionless fingers. For a given polygonal object with n vertices and an external wrench wext, we show how to find all pairs of features of P, that admit grasps capable of resisting wextwith grasp quality greater or equal to some threshold Q, in O(n3/2+ε+ K) time, where K is the number of pairs in the output and ε is some arbitrarily small, positive constant. We then show how to adapt our algorithm to guarantee that the features reported, admit local force closure grasps.

The immobilization of nonrigid objects is a relatively unexplored area in grasp mechanics. In this paper, we consider the immobilization of freely moving serial chains ofnhinged polygons using frictionless point fingers. We first set this problem in the context of classical grasping theory by showing that chain immobilization can only be achieved with equilibrium grasps. Then, we describe two immobilization approaches based on first- and second-order geometric effects. Based on curvature effects, chains ofn≠ 3 hinged polygons with nonparallel edges can be immobilized byn+ 2 frictionless point fingers. Serial chains of three hinged polygons form an exception to this rule. Based on first-order geometric effects, we describe how to immobilize any chain ofnhinged polygons with only one extra contact for the entire chain, using a total ofn+ 3 frictionless point fingers. Moreover, the immobilizing grasps are robust with respect to small contact placement errors. The results are illustrated with examples and described as readily implementable procedures.

We extend the notion of grasp metrics to partial force-closure grasps. We describe two metrics which measure the maximum and sum, respectively, of the forces that need to be applied at the contacts involved in a grasp, in order to exert some given unit wrench on the grasped object. For a given object P of complexity O(n) and a pure force T, we describe efficient algorithms which compute all combinations of m features (edges of polygons or facets of polyhedra) that admit grasps capable of exerting T such that the value of our metric is greater than some threshold. In particular, we show that if P is a polygon, all pairs of edges that admit frictionless two-finger grasps capable of exerting T can be computed in O(n log2n+K) time, where K is the number of pairs of edges in the output. Also, all two-finger grasps with friction of a polyhedral object can be computed in O(n3/2+ε+ K') time and all frictionless three-finger grasps of a polyhedron can be computed in O(n5/2+ε+ K') time, where K0is the number of pairs or triples of facets that satisfy some slightly weaker condition and ε is some arbitrarily small, positive constant.

We propose a technique which significantly simplifies the computation of frictionless force-closure grasps of a curved planar part$P$. We use a colored projection scheme from the three-dimensional wrench space to two-dimensional screens, which allows us to reduce the problem of identifying combinations of arcs and concave vertices of$P$that admit frictionless force-closure grasps, to colored intersection searching problems in the screens. We show how to combine this technique with existing intersection searching algorithms to obtain efficient, output-sensitive algorithms to compute all force-closure grasps of$P$, where at most four hard, frictionless point contacts exert exactly four wrenches on$P$. If the boundary of$P$consists of$n$algebraic arcs of constant complexity and$m$concave vertices, we show how to compute all force-closure grasps with:four contacts along four arcs in$O(n^{8/3}\log ^{1/3}n+K)$time;

The immobilization of non-rigid objects is a relatively unexplored area in grasp mechanics. This paper considers the immobilization of 2D serial chains of n hinged polygons at a given placement using frictionless point fingers. The paper sets the problem in the context of classical grasping theory by showing that chain immobilization can only be achieved with equilibrium grasps. In earlier work we described an immobilization procedure for serial chains of n≠3 polygons using n+2 frictionless point fingers. However, the immobilization of three-link chains remained an open problem. This paper establishes that three-link chains can usually be immobilized with five point fingers, but certain three-link chains can only be immobilized with six point fingers. The paper then considers the robust immobilization of serial chains under small contact placement errors. We describe a procedure for robust immobilization of n-link chains that requires only one extra contact for the entire chain, using a total of n+3 frictionless point fingers. The immobilization procedures and the exceptional three-link chains are illustrated with example.

This paper considers robotic automation of a common surgical retraction primitive of exposing an underlying area by grasping and lifting a thin, 3D, possibly inhomogeneous layer of tissue. We present an algorithm that computes a set of stable and secure grasp-and-retract trajectories for a point-jaw gripper moving along a plane, and runs a 3D finite element (FEM) simulation to certify and assess the quality of each trajectory. To compute secure candidate grasp locations, we use a continuous spring model of thin, inhomogeneous deformable objects with linear energy potential. Experiments show that this method produces many of the same grasps as an exhaustive optimization with an FEM mesh, but is orders of magnitude cheaper: our method runs in O(v log v) time, where v is the number of veins, while the FEM computation takes O(pn3) time, where n is the number of nodes in the FEM mesh and p is the number of nodes on its perimeter. Furthermore, we present a constant tissue curvature (CTC) retraction trajectory that distributes strain uniformly around the medial axis of the tissue. 3D FEM simulations show that the CTC achieves retractions with lower tissue strain than circular and linear trajectories. Overall, our algorithm computes and certifies a high-quality retraction in about one minute on a PC.

In the context of automated feeding (orienting) of industrial parts, we study the algorithmic design of traps in the bowl feeder track that filter out all but one orientation of a given polyhedral part. We propose a new class of traps that removes a V-shaped portion of the track. The proposed work advances the state-of-the-art in algorithmic trap design by extending earlier work [1], [3], [11]—which focuses solely on 2D parts—to 3D parts, and by incorporating a more realistic part motion model in the design algorithm. The presented complete design algorithm takes as input any polyhedral part, along with its center of mass, and reports all valid trap designs that feed the given part.

We report our algorithmic development of the pframe problem that addresses the need of coordinating a set of p networked robotic pan-tilt-zoom cameras for n, (n ≫ p), competing polygonal requests. We assume that the p frames have almost no overlap on the coverage between frames and a request is satisfied only if it is fully covered. We then propose a Resolution Ratio with Non-Partial Coverage (RRNPC) metric to quantify the satisfaction level for a given request with respect to a set of p candidate frames. We propose a latticebased approximation algorithm to search for the solution that maximizes the overall satisfaction. The algorithm builds on an induction-like approach that finds the relationship between the solution to the (p — 1)-frame problem and the solution to the p-frame problem. For a given approximation bound ε, the algorithm runs in O(n/ε3+p2/ε6) time. We have implemented the algorithm and experimental results are consistent with our complexity analysis.

We study three-finger caging grasps of convex polygons. A grasp is said to cage a part when the fingers make it impossible for the part to move to a distant location-and, hence, escape the grasp-without penetrating a finger. We build a data structure in polynomial time for a given convex polygon with n edges that allows us to solve two problems. (1) For a given grasp, we give an algorithm that determines in O(log n) time whether the grasp cages the polygon. (2) For a given placement of two fingers we give an algorithm that outputs in O(n4log n + K) time all placements of the third finger such that the three fingers together constitute a caging grasp of the polygon, in which K is proportional to the complexity of the output description.

Object immobilization is important to robot hand grasping and to many manufacturing processes. A huge number of existing papers considered issues such as the analysis of grasps, the existence of immobilizing grasps for various classes of objects, and the synthesis of immobilizing grasps for twoand three-dimensional objects. However, no algorithm has been proposed to efficiently enumerate all form-closure grasps for any class of three-dimensional objects. As an initial step towards a general solution to this complex problem, we propose the first efficient algorithm for computing all form-closure grasps of a rectilinear polyhedron. Our approach is based on a decomposition of the original problem in the abstract sixdimensional wrench space into closely related subproblems in three-dimensional subspaces, and a subsequent transformation of these subproblems into two-color intersection problems on planar screens in these spaces. We then use techniques from computational geometry to efficiently solve the planar intersection problems. The resulting algorithm reports all K sets of six to seven faces of a rectilinear polyhedron that yield at least one form-closure grasp in O(n2K′log4n + K) time, where n is the number of the faces, and K′ is the size of an intermediate output. We show that K = Ω (n2K′) in the worst case.

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.

We study worst-case complexities of visibility and distance structures on terrains under realistic assumptions on edge length ratios and the angles of the triangles. We show that the visibility map of a point for a realistic terrain with n triangles has complexity Θ(n√n). We also prove that the shortest path between two points p and q on a realistic terrain passes through Θ(√n) triangles, and that the bisector between p and q has complexity O(n √n). We use these results to show that the shortest path map for any point on a realistic terrain has complexity Θ(n√n), and that the Voronoi diagram for any set of m points on a realistic terrain has complexity Ω(n + m√n) and O((n+m)√n). Our results immediately imply more efficient algorithms for computing the various structures on realistic terrains.

The vibratory bowl feeder remains the most common approach to the automated feeding (orienting) of industrial parts. We study the algorithmic design of devices on the bowl feeder track that filter out all but one orientation of a given polyhedral part. In this context, we propose a simple new primitive, consisting of one horizontally mounted convex polygonal metal "blade", that can feed a broad class of three-dimensional parts by reorienting and rejecting all but those in a desired orientation. This powerful new 3D geometric feeding primitive combines the reorientation functionality of fences with the rejection functionality of traps. Due to its simplicity, the proposed primitive allows for the development of methods to automate its design process. We present a complete procedure that takes as input any polyhedral part along with its center of mass. Given this input, the procedure identifies all single blade solutions that feed the part. The output is either the set of all valid blade designs or a notification that the part cannot be fed using a single blade

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

New multi-axis satellites allow camera imaging parameters to be set during each time slot based on competing demand for images, specified as rectangular requested viewing zones over the camera's reachable field of view. The single frame selection (SFS) problem is to find the camera frame parameters that maximize reward during each time window. We formalize the SFS problem based on a new reward metric that takes into account area coverage and image resolution. For a set of n client requests and a satellite with m discrete resolution levels, we give an algorithm that solves the SFS problem in time O(n/sup 2/m). For satellites with continuously variable resolution (m=/spl infin/), we give an algorithm that runs in time O(n/sup 3/). We have implemented all algorithms and verify performance using random inputs. Note to Practitioners-This paper is motivated by recent innovations in earth imaging by commercial satellites. In contrast to previous methods that required waits of up to 21 days for desired earth- satellite alignment, new satellites have onboard pan-tilt-zoom cameras that can be remotely directed to provide near real-time response to requests for images of specific areas on the earth's surface. We consider the problem of resolving competing requests for images: Given client demand as a set of rectangles on the earth surface, compute camera settings that optimize the tradeoff between pan, tilt, and zoom parameters to maximize camera revenue during each time slot. We define a new quality metric and algorithms for solving the problem for the cases of discrete and continuous zoom values. These results are a step toward multiple frame selection which will be addressed in future research. The metric and algorithms presented in this paper may also be applied to collaborative teleoperation of ground-based robot cameras for inspection and videoconferencing and for scheduling astronomic telescopes.

We propose the first efficient output-sensitive algorithms for computing all form-closure grasps of a planar curved part P with at most four frictionless point contacts. The boundary of P consists of m concave vertices and n algebraic arcs with a constant degree. All our algorithms are output-sensitive, which means that their running times largely depend on the actual output size K rather than the (often much larger) maximum size of the output. More specifically, we show how to determine • all form-closure grasps with four points along four arcs in O(n8/3log1/3n + K) time, • all form-closure grasps with four points along three arcs in O(n5/2+ε+ K) time, • all form-closure grasps with one point at a concave vertex and two points along two arcs in O(n2m1/2+ε+ K) time, • all form-closure grasps with one point at a concave vertex and two points along a single arc in O(nm) or O(n3/2+ε+ K) time (depending on the size of m), • all form-closure grasps with two points at concave vertices and one point along arc in O(nm2) or O (n2+ε+ K) time (depending on the size of m), where ε is an arbitrarily small positive constant. All our algorithms rely on the geometric condition in three-dimensional wrench space, which is transformed into two-dimensional geometric intersection problems.

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

We present a computational method for simulating needle insertions interactively in both 2D and 3D models of soft tissue. The approach is based on the Finite Element Method (FEM) and uses quasi-static stick-slip friction for needle/tissue interactions. The FEM equations are solved using an iterative method, and the mesh is refined adaptively near the needle trajectory. The boundary formed by the needle surface is not represented explicitly in the mesh, but its geometry is accounted for in the friction forces. This has the advantage that we can use a simple and therefore fast refinement scheme that is guaranteed to keep the mesh quality at the initial level. This approach can also be applied to the 3D situation as well as to nonlinear geometry and material models. We present results of computational experiments of the 2D simulation, and show promising samples of the 3D implementation.

Near real time satellite imaging provides timely images of the earth for weather prediction, disaster response, search and rescue, surveillance, and defense applications. As the satellite passes over the earth, camera imaging parameters are changed during each time window based on demand for images, specified as user requested zones in the reachable field of view during that time window. The satellite frame selection (SFS) problem is to find the camera frame parameters that maximize reward during each time window. To automate satellite management, we formalize the SFS problem based on a new reward metric that incorporates both image resolution and coverage. For a set of n client requests we give a series of algorithms, the fastest computes optimal results in O(n/sup 3/) for satellites with continuously variable resolution. We have implemented the algorithms and compare computation speed for all algorithms.

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 shows that any polygonal part without parallel edges can be held in form closure by at most four point fingers on two perpendicular lines. The practical implication of this surprising result is that any such part can be held in form closure by at most four point fingers that are constrained to lie on a given regular grid of orthogonal lines-a requirement present in modular fixturing systems. The difficult issue of existence of solutions in modular settings was raised by Zhuang and Goldberg (1996). In contrast to earlier results in this direction, the result in this paper does not require convexity of the part or a lower bound on the part diameter or edge lengths. The paper also considers the extension of the result to parts with parallel edges and to circular fingers with nonzero radius.

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.

We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots as one composite robot, whose number of degrees of freedom is d, the sum of the numbers of degrees of freedom of the individual robots. We show that it is sufficient to consider a constant number of robot systems whose number of degrees of freedom is at most d \\Gamma 1 for pairs of robots, and d \\Gamma 2 for triples. (The result for a pair assumes that the sum of the number of degrees of freedom of the robots constituting the pair reduces by at least one if the robots are required to stay in contact; for triples a similar assumption is made. Moreover, for triples we need to assume that a solution with positive clearance exists.) We use this to obtain an O(n d ) time algorithm to solve the motion-planning problem for a pair of robots; this is one order of magnitude faster than what the st...

Many algorithms developed in computationid geometry are needlessly complicated and slow because they have to be prepared for very complicated, hypathetical inputs.To avoid this, realistic models are needed that describe the properties that realistic inputs have, so that algorithms can de designed that take advantage of these properties.This can lead to algorithms that are provably efficient in realktic situations.We obtain some fundamental results in this research direction.In particular, we have the following results.. We show the relations between various models that have been proposed in the literature.q For several of these models, we give algorithms to compute the model parameter(s) for a given scene; these algorithms can be used to verify whether a model is appropriate for typical scenesin some application area.q As a case study, we give some experimental results on the appropriateness of some of the models for one particular type of scenes often encountered in GIS, namely certain triangulated irregular networks.

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

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