Abstract:
Multi-robot applications frequently seek to employ human operators to direct robot actions online because fully automated planners struggle to encode human expertise or handle the extenuating circumstances that occur during real world operations. However, it is extremely challenging for a human to direct multi-robot teams, especially online, i.e., in real-time. From entertainment to defense, applications can require detailed inter-robot coordination direction which can be difficult for an operator to specify. Finding motion plans that then meet user intent is complicated by the need to operate in cluttered environments while absolving the human operator from having to consider physical constraints of the system such as dynamic feasibility or safety.

Existing multi-robot policy specification and planning methods have difficulty providing all the required capabilities to enable high-speed, online, human-directed multi-agent motion generation in cluttered environments. While reaction based or local control methods have been widely used for multi-robot applications due to their fast computation times, these methods can fail to produce coordinated responses or safety guarantees. In contrast, optimization methods and search approaches are frequently used to coordinate actions across robots and generate high quality motion plans. Unfortunately, the large number of inherent decision variables, especially as frequently incurred when considering numerous obstacles, often means these methods require computation times in excess of online operation limits.

In this thesis, we enable a search based methodology to find safe and feasible multi-robot trajectories at fast time scales even in highly cluttered environments by leveraging a group-based representation of multi-robot actions and offline acquired data. Our approach generalizes across environments and enables an operator to coordinate multi-robot motions online for applications requiring high-frequency plan generation such as required by joystick control. We show results for two human-commanded multi-robot applications: theatrical performance and urban reconnaissance. Both applications require a multi-robot planner to resolve differences between operator input and feasibility requirements given the current state of the system, and generate dynamically feasible and safe trajectories for all agents within time and computation constraints.

This thesis establishes an online multi-robot planning and control system for the specification of multi-robot behaviors, and we demonstrate the feasibility of the approach using a multi-quadrotor system, controlling up to 30 physical robots online in the context of the theatric application. We then address assumptions made under the theatric context to meet the high-frequency planning and cluttered environment context of the urban reconnaissance application, and present a generalized formulation of multi-robot behaviors and leverage examples of multi-agent actions from real world data sets to inform an online search policy. We demonstrate that the generalized representation coupled with the proposed data-based search heuristic enables high-speed multi-robot coordination in cluttered environments, providing needed capabilities to enable multi-robot solutions for complex real world applications.

More Information

Thesis Committee Members:
Nathan Michael, Chair
Howie Choset
Maxim Likhachev
Mac Schwager, Stanford University