Real-time multi-robot path planning revisited as a caching problem

摘要

Path planning is a fundamental component of mobile robots. In case of large maps, path planning is a time consuming process, particularly for robots equipped with embedded computers and has adverse effects on the real-time response of the robots. This paper takes a fresh look at the path planning problem by considering it to be a caching or tabular-lookup problem. The robots ‘cache’ their generated paths and arm trajectories across various start and goal configurations. These cached paths are stored in a database accessible to robots in the network. Robot path planning is then reduced to a simple table-lookup which can be resolved in real-time. To overcome a cache-miss, a micro-grid and macro-grid based caching is proposed for real-time path generation for ‘nearby’ start and goal configurations. Another important characteristic of the proposed cache based path planning is that multiple robots also update the locations of the new obstacles in the map. This benefits other robots as they are able to get an updated information about the new obstacles in remote locations of the map, without explicitly discovering those obstacles by themselves. We show that by considering the robot path planning as a caching problem, robots can achieve faster and real-time responses, particularly in case of large maps with multiple robots in a sensor network.