Abstract:
In complex dynamic multi-robot domains, we have a set of individual robots that must coordinate together through a team planner that inevitably makes assumptions based on probabilities about the state of world and the actions of the individuals. Eventually, the individuals may encounter failures, because the team planner’s models of the states and actions are incomplete. Further, the team planner may find that there is no plan with a reasonable probability of success and instead provides either no further course of action or a plan which is likely to fail. In this thesis, we address the problem of what an individual robot must do when faced with such failures and cannot execute the team plan generated by the team planner.

While previous work has exclusively explored centralized approaches or decentralized approaches for dynamic multi-robot problems, it lacks the combination of a centralized approach with intelligent planning individuals, whom are often found in decentralized approaches. In centralized approaches, the focus has been on removing the need for replanning through conditional planning and policy generations, on hierarchical decomposition to simplify the multi-robot problem, or on predicting the informational needs of teammates. In decentralized approaches, the focus has been on improving auctioning algorithms, task decomposition, task assignment, and policy generation. More generally, shared by both approaches, there has been work on commitment to actions shared between multiple robots, i.e., joint actions. In my thesis, I contribute a novel intra-robot replanning algorithm for the individual robots, within a team, that intelligently handle failures. I introduce team plan conditions in the team plan that provide the reasoning behind the assumptions made by the team planner. My novel intra-robot replanning algorithm has the choice of re-achieving the failed team plan conditions, invoking the team planner with more information, or changing the team plan, thereby changing the state of the world, to improve the probability of the team succeeding. Furthermore, my intra-robot replanning algorithm learns what choice should be taken by the individual robot in a given state of the world.

My thesis is motivated by my previous work with individual robot replanning and team planners and the inability of their individual robots to handle failures. With NASA’s Astrobee, a floating zero-g robot that will operate in the International Space Station, its approach to failures was to stop, message the ground station, and wait for a new plan. With autonomous underwater vehicles (AUVs), their approach to failures was to rise to the surface of the ocean, message the centralized controller, and wait for a new plan. With the Small-Size League soccer robots, their approach to failures was to continue, blindly executing a failing team plan, because taking at least some course of action, even if currently failing, is better than doing nothing in an adversarial domain. Of course, continuing to execute a failing plan is an inadvisable approach, but the individual soccer robots lacked the necessary individual intelligence to fix the problem. All these domains share the common thread of relying on the centralized planner to provide them with a new solution to handle failures. And, in doing so, they each decrease their performance in completing their plans efficiently.

Our work so far has proposed a team plan representation that introduced team plan conditions. Team plan conditions provide the conditions required to accomplish the team’s goal(s), assumed by the team planner to remain valid, and to provide the individual team members with the team planner’s reasoning should they need to replan during execution. I demonstrated that proactively using my novel intra-robot replanning algorithm can improve the performance of the team and that learning has the potential to further improve the decision making of the individual robot.

The remainder of my thesis work will focus on formalizing the team plan representation to include team plan conditions, on generalizing the intra-robot replanning algorithm to clarify the function of the individual and of the team planner, and on learning that informs the individual of the best choice when faced with a failure. In evaluating my thesis work, I will formalize multiple different domains (e.g., robot soccer, coordinated underwater vehicles, and capture the flag) to show the improvement of a team of informed learning individual robots compared to a team of uninformed individual robots.

Thesis Proposal Document

Thesis Committee Members:
Manuela Veloso, Chair
Maxim Likhachev
Stephen Smith
Daniel Borrajo Millán, Universidad Carlos III de Madrid