اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGuided Incremental Local Densification for Accelerated Sampling-based Motion Planning
112
0
0.0
(
0
)
نشر من قبل
Aditya Vamsikrishna Mandalika
تاريخ النشر
2021
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Sampling-based motion planners rely on incremental densification to discover progressively shorter paths. After computing feasible path $xi$ between start $x_s$ and goal $x_t$, the Informed Set (IS) prunes the configuration space $mathcal{C}$ by conservatively eliminating points that cannot yield shorter paths. Densification via sampling from this Informed Set retains asymptotic optimality of sampling from the entire configuration space. For path length $c(xi)$ and Euclidean heuristic $h$, $IS = { x | x in mathcal{C}, h(x_s, x) + h(x, x_t) leq c(xi) }$. Relying on the heuristic can render the IS especially conservative in high dimensions or complex environments. Furthermore, the IS only shrinks when shorter paths are discovered. Thus, the computational effort from each iteration of densification and planning is wasted if it fails to yield a shorter path, despite improving the cost-to-come for vertices in the search tree. Our key insight is that even in such a failure, shorter paths to vertices in the search tree (rather than just the goal) can immediately improve the planners sampling strategy. Guided Incremental Local Densification (GuILD) leverages this information to sample from Local Subsets of the IS. We show that GuILD significantly outperforms uniform sampling of the Informed Set in simulated $mathbb{R}^2$, $SE(2)$ environments and manipulation tasks in $mathbb{R}^7$.
قيم البحث
اقرأ أيضاً
This paper studies the problem of control strategy synthesis for dynamical systems with differential constraints to fulfill a given reachability goal while satisfying a set of safety rules. Particular attention is devoted to goals that become feasibl
e only if a subset of the safety rules are violated. The proposed algorithm computes a control law, that minimizes the level of unsafety while the desired goal is guaranteed to be reached. This problem is motivated by an autonomous car navigating an urban environment while following rules of the road such as always travel in right lane and do not change lanes frequently. Ideas behind sampling based motion-planning algorithms, such as Probabilistic Road Maps (PRMs) and Rapidly-exploring Random Trees (RRTs), are employed to incrementally construct a finite concretization of the dynamics as a durational Kripke structure. In conjunction with this, a weighted finite automaton that captures the safety rules is used in order to find an optimal trajectory that minimizes the violation of safety rules. We prove that the proposed algorithm guarantees asymptotic optimality, i.e., almost-sure convergence to optimal solutions. We present results of simulation experiments and an implementation on an autonomous urban mobility-on-demand system.
We address the problem of planning robot motions in constrained configuration spaces where the constraints change throughout the motion. The problem is formulated as a fixed sequence of intersecting manifolds, which the robot needs to traverse in ord
er to solve the task. We specify a class of sequential motion planning problems that fulfill a particular property of the change in the free configuration space when transitioning between manifolds. For this problem class, we develop the algorithm Planning on Sequenced Manifolds (PSM*) which searches for optimal intersection points between manifolds by using RRT* in an inner loop with a novel steering strategy. We provide a theoretical analysis regarding PSM*s probabilistic completeness and asymptotic optimality. Further, we evaluate its planning performance on multi-robot object transportation tasks. Video: https://youtu.be/Q8kbILTRxfU Code: https://github.com/etpr/sequential-manifold-planning
The discontinuities and multi-modality introduced by contacts make manipulation planning challenging. Many previous works avoid this problem by pre-designing a set of high-level motion primitives like grasping and pushing. However, such motion primit
ives are often not adequate to describe dexterous manipulation motions. In this work, we propose a method for dexterous manipulation planning at a more primitive level. The key idea is to use contact modes to guide the search in a sampling-based planning framework. Our method can automatically generate contact transitions and motion trajectories under the quasistatic assumption. In the experiments, this method sometimes generates motions that are often pre-designed as motion primitives, as well as dexterous motions that are more task-specific.
In this paper, we introduce a new probabilistically safe local steering primitive for sampling-based motion planning in complex high-dimensional configuration spaces. Our local steering procedure is based on a new notion of a convex probabilistically
safe corridor that is constructed around a configuration using tangent hyperplanes of confidence ellipsoids of Gaussian mixture models learned from prior collision history. Accordingly, we propose to expand a random motion planning graph towards a sample goal using its projection onto probabilistically safe corridors, which efficiently exploits the local geometry of configuration spaces for selecting proper steering direction and adapting steering stepsize. We observe that the proposed local steering procedure generates effective steering motion around difficult regions of configuration spaces, such as narrow passages, while minimizing collision likelihood. We evaluate the proposed steering method with randomized motion planners in a number of planning scenarios, both in simulation and on a physical 7DoF robot arm, demonstrating the effectiveness of our safety guided local planner over the standard straight-line planner.
A defining feature of sampling-based motion planning is the reliance on an implicit representation of the state space, which is enabled by a set of probing samples. Traditionally, these samples are drawn either probabilistically or deterministically
to uniformly cover the state space. Yet, the motion of many robotic systems is often restricted to small regions of the state space, due to, for example, differential constraints or collision-avoidance constraints. To accelerate the planning process, it is thus desirable to devise non-uniform sampling strategies that favor sampling in those regions where an optimal solution might lie. This paper proposes a methodology for non-uniform sampling, whereby a sampling distribution is learned from demonstrations, and then used to bias sampling. The sampling distribution is computed through a conditional variational autoencoder, allowing sample generation from the latent space conditioned on the specific planning problem. This methodology is general, can be used in combination with any sampling-based planner, and can effectively exploit the underlying structure of a planning problem while maintaining the theoretical guarantees of sampling-based approaches. Specifically, on several planning problems, the proposed methodology is shown to effectively learn representations for the relevant regions of the state space, resulting in an order of magnitude improvement in terms of success rate and convergence to the optimal cost.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
