动态路图图中边的快速启发式验证

Addressing the challenge of adapting roadmap graphs for robot motion planning in non-static environments, the "Red-Green-Gray" paradigm is introduced as a modification of the SPITE method. This paradigm classifies the validity status of nodes and edges using inexpensive heuristic checks, enabling fast semi-lazy roadmap updates. Given a roadmap, simple computational geometry methods are employed to approximate the swept volumes of robots and perform preliminary obstacle collision detection. Edges in the roadmap are then categorized into three states based on these checks: green (valid/safe), red (invalid/colliding), and gray (unknown). Green edges signify that the robot can safely traverse them in the current environment, red edges indicate a collision with an obstacle, while gray edges denote that their validity is not fully determined and requires further detailed verification. This classification mechanism allows the system to prioritize the re-evaluation of uncertain gray edges, rather than performing expensive re-validation for all edges. Such an approach significantly reduces the time and computational resources required to update the roadmap in dynamic environments. When the environment changes, the system does not need to construct a new roadmap from scratch. Instead, it re-evaluates affected nodes and edges, updating their color states incrementally. This incremental update strategy substantially enhances the real-time performance and efficiency of motion planning, particularly beneficial in complex dynamic environments where obstacles frequently appear or move.