Planning efficient and coordinated policies for a team of robots is a computationally demanding problem, especially when the system faces uncertainty in the outcome or duration of actions. In practice, approximation methods are usually employed to plan reasonable team policies in an acceptable time. At the same time, many typical robotic tasks include a repetitive pattern. On the one hand, this multiplies the increased cost of inefficient solutions. But on the other hand, it also provides the potential for improving an initial, inefficient solution over time. In this paper, we consider the case that a single mission specification is given to a multi-robot system, describing repetitive tasks which allow the robots to parallelize work. We propose here a decentralized coordination scheme which enables the robots to decompose the full specification, execute distributed tasks, and improve their strategy over time.
Simultaneous Task Allocation and Planning for Temporal Logic Goals in Heterogeneous Multi-Robot Systems
This paper describes a framework for automatically generating optimal action-level behavior for a team of robots based on Temporal Logic mission specifications under resource constraints. The proposed approach optimally allocates separable tasks to available robots, without requiring a-priori an explicit representation of the tasks or the computation of all task execution costs. Instead, we propose an approach for identifying sub-tasks in an automaton representation of the mission specification and for simultaneously allocating the tasks and planning their execution. The proposed framework avoids the need of computing a combinatorial number of possible assignment costs, where each computation itself requires solving a complex planning problem. This can improve computational efficiency compared to classical assignment solutions, in particular for on-demand missions where task costs are unknown in advance. We demonstrate the applicability of the approach with multiple robots in an existing office environment and evaluate its performance in several case study scenarios.
Motivated by the DARPA Robotics Challenge (DRC), the application of operator assisted (semi-)autonomous robots with highly complex locomotion and manipulation abilities is considered for solving complex tasks in potentially unknown and unstructured environments. Because of the limited a priori knowledge about the state of the environment and tasks needed to achieve a complex mission, a sufficiently complete a priori design of high level robot behaviors is not possible. Most of the situational knowledge required for such behavior design is gathered only during runtime and needs to be interpreted by a human operator. However, current behavior control approaches only allow for very limited adaptation at runtime and no flexible operator interaction. In this paper an approach for definition and execution of complex robot behaviors based on hierarchical state machines is presented, allowing to flexibly change the structure of behaviors on the fly during runtime through assistance of a remote operator. The efficiency of the proposed approach is demonstrated and evaluated not only in an example scenario, but also by application in two robot competitions.