Robotics Institute Thesis Proposal: Proactive Replanning for Multi-Robot Teams

Proactive Replanning for Multi-Robot Teams

Brennan Sellner
Robotics Institute
Carnegie Mellon University

Place and Time
NSH 3002 2:00 PM

Abstract:
Rather than blindly following a predetermined schedule, human workers often dynamically change their course of action in order to assist a coworker who is having unexpected difficulties. The goal of this research is to examine how this notion of "helpful" behavior can inspire new approaches to online plan execution and repair in multi-robot systems. Specifically, we are investigating the enabling of proactive replanning by dynamically predicting task duration and adapting to predicted problems or opportunities through the modification of executing tasks. By continuously predicting the remaining task duration, a proactive replanner is able to adjust to upcoming opportunities or problems before they manifest themselves. One way in which it may do so is by adjusting the allocation of agents to the various executing tasks by adding or removing agents, which allows the planner to balance a schedule in response to the realities of execution. We propose to develop a planning/scheduling/execution system that, by supporting duration prediction and adaptation, will be able to execute complex multi-robot tasks in an uncertain environment more efficiently than is possible without such proactive capabilities.

We have developed a proof-of-concept system that implements duration prediction and modification of existing tasks, yielding simulated executed makespans as much as 31.8% shorter than possible without these capabilities. Our initial system does not operate in real time, nor with actual hardware, instead interfacing with a simulator and allowing unlimited time for replanning between time steps. We propose to characterize the applicability of this approach to various domains, extend our algorithms to support more complex scenarios and to address shortcomings we have identified, and optimize the algorithms with respect to both computational complexity and the makespan of the final executed schedule, with the goal of bringing the advantages of duration prediction and task modification to real-time planning/execution system. We will evaluate our approach to proactive replanning both in an extensive series of simulated experiments and in a real-time assembly scenario using actual hardware. We hypothesize that proactive replanning can be performed in real time while yielding significant improvements in overall execution time, as compared with a baseline repair-based planner.

Further Details:
A copy of the thesis proposal document can be found at http://gs295.sp.cs.cmu.edu/brennan/files/sellner_proposal.pdf.

Thesis Committee:
Reid Simmons, Chair
Sanjiv Singh
Stephen Smith
Tara Estlin, Jet Propulsion Laboratory