Design and evaluation of a lookup-table based collision-checking approach for fixed sets of mobile robot paths

摘要

Several existing mobile robot navigation systems adopt a fixed set of local paths to find traversable areas in the robot's neighborhood. In order to perform collision checking for these paths or - more generally - to compute a path cost, it is sometimes pre-computed offline which cells in a grid representation of the environment are visited by the robot for each of the paths, and these are stored in a lookup table. Then, in the online phase, just these pre-computed cells have to be checked to efficiently compute the cost and traversability of the paths. This paper presents an alternative for such collision and cost computation of paths by constructing the lookup table the other way around, by storing for all cells which paths pass through them instead of storing for all paths the cells they visit. The algorithm has been implemented and tested on several of our robotic wheelchairs. We show that this approach is almost always faster than the existing approach, and can result in considerable gains in memory and run-time computation.