A New Roadmap Constitution Method Based on Dividing Grid and Level-Set

Roadmap methods were widely used in route planning fields, both for robots and unmanned aircrafts. Traditional roadmap is constituted by connecting the vertexes of convex obstacle, which is related to the locations of start and goal of route, so the roadmap can not be reused when anyone of start and goal changed. Absence of reusability reduces the efficiency of route planning by using roadmap. A new roadmap constitution method was proposed in this paper, which is build on dividing the 2D configuration space into multi-scale grids and setting nodes of roadmap on grid boundary using Level-Set method, same method was used to construct the map cells of roadmap between any two nodes lays on same grid. The roadmap constituted with new method can be reused when the start or goal was changed; it is efficient for replanning problem.