Rapidly-Exploring Quotient-Space Trees: Motion Planning using Sequential Simplifications
Motion planning problems can be simplified by admissible projections of the configuration space to sequences of lower-dimensional quotient-spaces, called sequential simplifications. To exploit sequential simplifications, we present the Quotient-space Rapidly-exploring Random Trees (QRRT) algorithm. QRRT takes as input a start and a goal configuration, and a sequence of quotient-spaces. The algorithm grows trees on the quotient-spaces both sequentially and simultaneously to guarantee a dense coverage. QRRT is shown to be (1) probabilistically complete, and (2) can reduce the runtime by at least one order of magnitude. However, we show in experiments that the runtime varies substantially between different quotient-space sequences. To find out why, we perform an additional experiment, showing that the more narrow an environment, the more a quotient-space sequence can reduce runtime.
Code (0)
등록된 구현이 없습니다.
Tasks
Motion PlanningSimilar Papers 제목 키워드 기반
Fibration Trees: A Unified Approach to Multi-Robot Motion Planning
State space projections and decompositions have emerged as powerful tools to tackle the curse of dimensionality in high-dimensional, multi-robot motion planning problems. However, existing methods lack a unified framewor…
Motion PlanningBroadly-Exploring, Local-Policy Trees for Long-Horizon Task Planning
Long-horizon planning in realistic environments requires the ability to reason over sequential tasks in high-dimensional state spaces with complex dynamics. Classical motion planning algorithms, such as rapidly-exploring…
Motion PlanningTask PlanningIntelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments
The sampling based motion planning algorithm known as Rapidly-exploring Random Trees (RRT) has gained the attention of many researchers due to their computational efficiency and effectiveness. Recently, a variant of RRT …
Computational EfficiencyMotion PlanningOptimal Motion PlanningqRRT: Quality-Biased Incremental RRT for Optimal Motion Planning in Non-Holonomic Systems
This paper presents a sampling-based method for optimal motion planning in non-holonomic systems in the absence of known cost functions. It uses the principle of learning through experience to deduce the cost-to-go of re…
Motion PlanningOptimal Motion Planningreinforcement-learningReinforcement Learning (RL)Graph Neural Networks for Motion Planning
This paper investigates the feasibility of using Graph Neural Networks (GNNs) for classical motion planning problems. We propose guiding both continuous and discrete planning algorithms using GNNs' ability to robustly en…
Motion Planning