Quick Heuristic Validation of Edges in Dynamic Roadmap Graphs
In this paper we tackle the problem of adjusting roadmap graphs for robot motion planning to non-static environments. We introduce the "Red-Green-Gray" paradigm, a modification of the SPITE method, capable of classifying the validity status of nodes and edges using cheap heuristic checks, allowing fast semi-lazy roadmap updates. Given a roadmap, we use simple computational geometry methods to approximate the swept volumes of robots and perform lazy collision checks, and label a subset of the edges as invalid (red), valid (green), or unknown (gray). We present preliminary experimental results comparing our method to the well-established technique of Leven and Hutchinson, and showing increased accuracy as well as the ability to correctly label edges as invalid while maintaining comparable update runtimes.
Code (0)
등록된 구현이 없습니다.
Tasks
Motion PlanningSimilar Papers 제목 키워드 기반
Serialized Red-Green-Gray: Quicker Heuristic Validation of Edges in Dynamic Roadmap Graphs
Motion planning in dynamic environments, such as robotic warehouses, requires fast adaptation to frequent changes in obstacle poses. Traditional roadmap-based methods struggle in such settings, relying on inefficient rec…
Motion PlanningEnergy-Aware Collaborative Exploration for a UAV-UGV Team
We present an energy-aware collaborative exploration framework for a UAV-UGV team operating in unknown environments, where the UAV's energy constraint is modeled as a maximum flight-time limit. The UAV executes a sequenc…
Autonomous UAV Exploration of Dynamic Environments via Incremental Sampling and Probabilistic Roadmap
Autonomous exploration requires robots to generate informative trajectories iteratively. Although sampling-based methods are highly efficient in unmanned aerial vehicle exploration, many of these methods do not effective…
Safe ExplorationLandmark Guided Probabilistic Roadmap Queries
A landmark based heuristic is investigated for reducing query phase run-time of the probabilistic roadmap (\PRM) motion planning method. The heuristic is generated by storing minimum spanning trees from a small number of…
Motion PlanningOptimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent
We present a novel approach called Optimized Directed Roadmap Graph (ODRM). It is a method to build a directed roadmap graph that allows for collision avoidance in multi-robot navigation. This is a highly relevant proble…
Collision AvoidanceMulti-Agent Path FindingNavigateRobot Navigation