Researchers crack multi-robot coordination problem with new planning method
Scientists have developed an optimization framework that allows autonomous systems to plan complex tasks involving multiple robots and moving obstacles more efficiently. The breakthrough could accelerate deployment of autonomous warehouses, construction sites, and delivery operations where coordinating robot movements and energy use is critical to profitability.
Originaltitel: Optimization-Based Planning for Task-Motion Integration and Multi-Agent Coordination
<p>Autonomous systems is a research field that has received significant attention during the last decades. An important requirement for such systems is the ability to plan before acting. This includes both higher-level task planning to determine what sequence of actions to take in order for the system to reach a goal, as well as lower-level motion planning in order to detail how to perform the actions required.</p><p>The first part of this thesis focuses on the problem of finding plans for task and motion planning (tamp) problems that optimize a given performance measure, such as energy consumption, path length or time. A method is presented for solving a tamp problem, that can be formulated as a traveling salesman problem with dynamic obstacles and motion constraints, to resolution optimality. The proposed method uses a planner consisting of two nested graph-search planners. Several different heuristics are considered and evaluated.</p><p>The main contribution in this part is a framework for solving a tamp problem, in the form of a rearrangement problem for a tractor-trailer system. In a first step, a method for finding a resolution-optimal solution is proposed. This method combines a task planner with motion planners, all based on heuristically guided graph search, and uses branch-and-bound techniques to improve the efficiency of the search algorithm. The efficiency is further improved by different strategies for recognizing equivalent problems. In a second step, the solution found in the first step is improved using optimal control. The proposed method takes inspiration from finite-horizon optimal control and decomposes the optimization problem into several smaller optimization problems. Compared to solving the original larger optimization problem, it is demonstrated that this can lead to reduced computation time without any significant decrease in solution quality.</p><p>The second part of this thesis focuses on finding kinematically feasible and optimized solutions to multi-agent motion planning (mamp) problems. A method for automatic generation of optimized motion primitives such that all primitive durations are a multiple of the same sample time is proposed. This facilitates collision checking. The proposed planner consists of two steps. In the first step a feasible solution is found using a state-of-the-art mamp planner such as conflict-based search (cbs) together with a single-agent planner. The proposed single-agent planner ensures kinematic feasibility, and allows more general cost functions and larger agents than previous approaches. In the second step, a multi-phase optimal control problem is posed and the solution found in the first step is used to warm start the solver.</p><p>For the special case where all agents are at rest initially and under the constraint of arriving at their goals simultaneously, it is shown that a feasible solution can be found by applying a standard mamp algorithm and searching backward. In particular, for certain choices of cost function and mamp algorithm it is (resolution) optimal. It is proposed to solve the optimization problem in the second step in a distributed and receding-horizon manner using the nonlinear alternating direction method of multipliers (nadmm).</p><p> </p>