Pre-positioning Assets to Increase Execution Efficiency

In many robotic domains, efficiency is an important component of task execution. One way to improve task efficiency is to lessen the overhead of beginning a task by making sure the necessary agents are near the task site when execution begins, minimizing travel time delays - in other words, pre-positioning agents for their future tasks. In static, certain domains, this can easily be done in advance and incorporated into the initial plan. In dynamic domains such as search and rescue, however, there is not enough certainty about task execution to plan for this ahead of time. To address this, we present here a planner that adds pre-positioning to a plan during execution. The planner strategically positions groups of idle robots whose future task assignments are uncertain in order to minimize travel time by the group as a whole once its members are allocated tasks. Because this planner must run in real time, we present five versions of the planning algorithm, addressing the trade-off of computation time and solution quality that results. We then show that by adding in this type of planning, the overhead of beginning a task can be reduced by up to 90%.