Determinization-Guided Planning for Multi-Robot Multi-Goal Navigation under Terrain-Dependent Robot Failure

Abstract

We study concurrent multi-robot, multi-goal navigation in which a terrain traversal can permanently immobilize a robot, and the robots that remain must still visit every goal. Solving this exactly requires full probabilistic planning. In practice the problem is determinized and planned with a fixed cost per traversal that keeps time or risk, which cannot represent whether another robot could still cover a goal after a failure. We introduce a RISK-TIME value function, that accounts for travel time, failure cost, and the coverage that remains after a failure. It is computed from a determinized version of the problem, and the same function serves determinized planning as a cost per traversal and probabilistic planning as a state value. With failure probabilities fit to off-road traversals, it reduces mean expected cost by 29–43% across the synthetic terrain layouts relative to a time-only baseline, and by 5.9% relative to a risk-only baseline. Probabilistic planning with it yields a further benefit at larger teams, but not consistently more than determinized planning with the same function. The choice between the two can therefore follow the computation available to the team at planning time.