This paper describes a new approach to sampling-based motion planning with PRM methods. Our aim is to compute good quality roadmaps that encode the multiple connectedness of the Cspace inside small but yet representat...
详细信息
ISBN:
(纸本)9783540684046
This paper describes a new approach to sampling-based motion planning with PRM methods. Our aim is to compute good quality roadmaps that encode the multiple connectedness of the Cspace inside small but yet representative graphs, that capture well the different varieties of free paths. The proposed approach relies on a notion of path deformability indicating whether or not a given path can be continuously deformed into another existing one. By considering a simpler form of deformation than the one allowed between homotopic paths, we propose a method that extends the Visibility-PRM technique [12] to constructing compact roadmaps that encode a richer and more suitable information than representative paths of the homotopy classes. The Path Deformation Roadmaps also contain additional useful cycles between paths in the same homotopy class that can be hardly deformed into each other. First experiments presented in the paper show that our technique enables small roadmaps to reliably and efficiently capture the multiple connectedness of the space in various problems.
This paper presents Workspace-based Connectivity Oracle (WCO), a dynamic sampling strategy for probabilistic roadmap planning. WCO uses both domain knowledge-specifically, workspace geometry-and sampling history to co...
详细信息
ISBN:
(纸本)9783540684046
This paper presents Workspace-based Connectivity Oracle (WCO), a dynamic sampling strategy for probabilistic roadmap planning. WCO uses both domain knowledge-specifically, workspace geometry-and sampling history to construct dynamic sampling distributions. It is composed of many component samplers, each based on a geometric feature of a robot. A component sampler updates its distribution, using information from the workspace geometry and the current state of the roachmap being constructed. These component samplers are combined through the adaptive hybrid sampling approach, based on their sampling histories. In the tests on rigid and articulated robots in 2-D and 3-D workspaces, WCO showed strong performance, compared with sampling strategies that use dynamic sampling or workspace information alone.
We present a simple algorithm to check for path non-existence for a robot among static obstacles. Our algorithm is based on adaptive cell decomposition of configuration space or C-space. We use two basic queries: free...
详细信息
ISBN:
(纸本)9783540684046
We present a simple algorithm to check for path non-existence for a robot among static obstacles. Our algorithm is based on adaptive cell decomposition of configuration space or C-space. We use two basic queries: free cell query, which checks whether a cell in C-space lies entirely inside the free space, and C-obstacle cell query, which checks whether a cell lies entirely inside the C-obstacle region. Our approach reduces the path non-existence problem to checking whether there exists a, path through cells that do not belong to the C-obstacle region. We describe simple and efficient algorithms to perform free cell and C-obstacle cell queries using separation distance and generalized penetration depth computations. Our algorithm is simple to implement and we demonstrate its performance on 3 DOF robots.
Error propagation on the Euclidean motion group arises in a number of areas such as and in dead reckoning errors in mobile robot navigation and joint errors that accumulate from the base to the distal end of manipulat...
详细信息
ISBN:
(纸本)9783540684046
Error propagation on the Euclidean motion group arises in a number of areas such as and in dead reckoning errors in mobile robot navigation and joint errors that accumulate from the base to the distal end of manipulators. We address error propagation in rigid-body poses in a coordinate-free way. In this paper we show how errors propagated by convolution on the Euclidean motion group, SE(3), can be approximated to second order using the theory of Lie algebras and Lie groups. We then show how errors that are small (but not so small that linearization is valid) can be propagated by a recursive formula derived here. This formula takes into account errors to second-order, whereas prior efforts only considered the first-order case [8, 9].
A distributed model structure for representing groups of coupled dynamic agents is proposed, and the least-squares method is used for fitting model parameters based on measured position data. The difference equation m...
详细信息
ISBN:
(纸本)9783540754039
A distributed model structure for representing groups of coupled dynamic agents is proposed, and the least-squares method is used for fitting model parameters based on measured position data. The difference equation model embodies a minimalist approach, incorporating only factors essential to the movement and interaction of physical bodies. The model combines effects from an agent's inertia, interactions between agents, and interactions between each agent and its environment. Global positioning system tracking data were collected in field experiments from a group of 3 cows and a group of 10 cows over the course of several days using custom-designed, head-mounted sensor boxes. These data are used with the least-squares method to fit the model to the cow groups. The modeling technique is shown to capture overall characteristics of the group as well as attributes of individual group members. Applications to livestock management are described, and the potential for surveillance, prediction, and control of various kinds of groups of dynamic agents are suggested. (C) 2008 Wiley Periodicals, Inc.
This paper addresses the problem of navigating an autonomous moving entity in an environment with both stationary and movable obstacles. If a movable obstacle blocks the path of the entity attempting to reach its goal...
详细信息
ISBN:
(纸本)9783540684046
This paper addresses the problem of navigating an autonomous moving entity in an environment with both stationary and movable obstacles. If a movable obstacle blocks the path of the entity attempting to reach its goal configuration, the entity is allowed to alter the placement of the obstacle by manipulation (e.g. pushing or pulling), to clear its path. This paper presents a probabilistically complete framework for solving path planning problems among movable obstacles. Heuristics are presented to provide efficient solutions for problems in environments encountered in practical situations.
Most algorithms for simultaneous localization and mapping (SLAM) do not incorporate prior knowledge of structural or geometrical characteristics of the environment. In some cases, such information is readily available...
详细信息
ISBN:
(纸本)9783540684046
Most algorithms for simultaneous localization and mapping (SLAM) do not incorporate prior knowledge of structural or geometrical characteristics of the environment. In some cases, such information is readily available and making some assumptions is reasonable. For example, one can often assume that many walls in an indoor environment are rectilinear. In this paper, we develop a SLAM algorithm that incorporates prior knowledge of relative constraints between landmarks. We describe a "Rao-Blackwellized constraint filter" that infers applicable constraints and efficiently enforces them in a particle filtering framework. We have implemented Our approach with rectilinearity constraints. Results from simulated and real-world experiments show the use of constraints leads to consistency improvements and a reduction in the number of particles needed to build maps.
In this paper we present artificial constraints as a method for guiding heuristic search in the computationally challenging domain of motion planning among movable obstacles. The robot is permitted to manipulate unspe...
详细信息
ISBN:
(纸本)9783540684046
In this paper we present artificial constraints as a method for guiding heuristic search in the computationally challenging domain of motion planning among movable obstacles. The robot is permitted to manipulate unspecified obstacles in order to create space for a path. A plan is an ordered sequence of paths for robot motion and object manipulation. We show that under monotone assumptions, anticipating future manipulation paths results in constraints on both the choice of objects and their placements at earlier stages in the plan. We present an algorithm that uses this observation to incrementally reduce the search space and quickly find solutions to previously unsolved classes of movable obstacle problems. Our planner is developed for arbitrary robot geometry and kinematics. It is presented with an implementation for the domain of navigation among movable obstacles.
One common mobile robot design consists of three 'omniwheels' arranged at the vertices of an equilateral triangle, with wheel axles aligned with the rays from the center of the triangle to each wheel. Omniwhee...
详细信息
ISBN:
(纸本)9783540684046
One common mobile robot design consists of three 'omniwheels' arranged at the vertices of an equilateral triangle, with wheel axles aligned with the rays from the center of the triangle to each wheel. Omniwheels, like standard wheels, are driven by the motors in a direction perpendicular to the wheel axle, but unlike standard wheels, can slip in a direction parallel to the axle. Unlike a steered car, a vehicle with this design can move in any direction without needing to rotate first, and can spin as it does so. We show that if there are independent bounds on the speeds of the wheels, the fastest trajectories for this vehicle contain only spins in place, circular arcs, and straight lines parallel to the wheel axles. We classify optimal trajectories by the order and type of the segments;there are four such classes, and there are no more than 18 control switches in ally optimal trajectory.
In this paper we discuss the problem of planning safe paths amidst unpredictably moving obstacles in the plane. Given the initial positions and the maximal velocities of the moving obstacles, the regions that are poss...
详细信息
ISBN:
(纸本)9783540684046
In this paper we discuss the problem of planning safe paths amidst unpredictably moving obstacles in the plane. Given the initial positions and the maximal velocities of the moving obstacles, the regions that are possibly not collision-free are modeled by discs that grow over time. We present an approach to compute the shortest path between two points in the plane that avoids these growing discs. The generated paths are thus guaranteed to be collision-free with respect to the moving obstacles while being executed. We created a fast implementation that is capable of planning paths amidst many growing discs within milliseconds.
暂无评论