Online Path Planning on a Sliding Fixed-Size Fixed-Resolution Grid Map

摘要: Online path planning on a grid map can be very time consuming and memory intensive. If a fine resolution uniform static grid map covering a large area needs to be allocated and planned on, the latency before path execution can be large. We show that by changing the underlying grid map, we can bound this latency regardless of the distance to the goal. Our implementation of the online path planner uses D* on a fixed-size, fixed-resolution map that slides in global coordinates but remains static with respect to the robot. As the robot executes the path, the map slides accordingly by replacing in memory the area no longer represented on the map with the new area appearing on the map. By implementing maps in this manner, we can designate the initial grid size a priori and thus bound the maximum planning time. This can be useful in situations for robots traveling long distances in an environment where obstacles …