Path Clearance Using Multiple Scout Robots

Maxim Likhachev and Anthony Stentz

Carnegie Mellon University



This paper presents the techniques that we have been developing recently to solve the problem of path clearance. In the path clearance problem the robot needs to reach its goal as quickly as possible without being detected by enemies. The problem is complicated by the fact that the robot does not know the precise locations of enemies, but has a list of their possible locations. Either the robot itself or scout robots can be used to sense these possible enemy locations before the robot traverses through them on the way to its goal. We have recently developed a general and efficient algorithm called PPCP (Probabilistic Planning with Clear Preference) for planning under uncertainty in the environment. In this paper we first describe how it can be applied to the problem of path clearance when there are no scout robots available and show that there are significant benefits of planning with PPCP over commonly used alternatives. We then explain a strategy for how to use the PPCP algorithm in case multiple scout robots are available and show that this strategy reduces the time it takes for the robot to reach its goal even further.


Keywords: path clearance, planning, planning under uncertainty, multi-robot coordination, planning with adversaries