Real-time robot motion planning using rasterizing computer graphics hardware

摘要: We present a real-time robot motion planner that is fast and complete to resolution. The technique guaranteed find path if one exists at the resolution, all paths returned are safe. can handle any polyhedral geometry of obstacles, including disjoint highly concave unions polyhedra.The uses standard graphics hardware rasterize configuration space obstacles into series bitmap slices, then dynamic programming create navigation function (a discrete vector-valued function) calculate in this rasterized space. which produces minimal with respect an L1 (Manhattan) distance metric includes rotation as well translation.Several examples shown illustrating competence generating planar rotational translational plans for complex two three dimensional robots. Dynamic sequences, complicated non-obvious backtracking solutions, be executed real time.