PaperlayerView exact revision on arXiv

Source-linked AI summary

Planning for Decentralized Control of Multiple Robots Under Uncertainty

Christopher Amato, George D. Konidaris, Gabriel Cruz, Christopher A. Maynor, Jonathan P. How, Leslie P. Kaelbling

arXiv:1402.2871v1cs.ROcs.AIcs.MA

TL;DR

Dec-POMDPs provide a general way to plan cooperative multi-robot behavior under uncertainty, but are typically intractable for real-world problems. This paper uses macro-actions with an approximate planner to synthesize policies, and demonstrates task allocation, direct communication, and signaling across warehouse scenarios.

  • Problem

    Dec-POMDPs model cooperative agents under uncertainty and limited communication, but are typically intractable for real-world problems.

    Source: Introduction · p. 1

  • Method

    The paper models multi-robot domains as MacDec-POMDPs and uses an approximate, memory-bounded planner to generate policies from the domain model.

    Source: Introduction · p. 2, Model · p. 3

  • Results

    Across three warehouse-task variations, the planner generated cooperative behavior using task allocation, direct communication, and signaling as appropriate.

    Source: Introduction · p. 2, Conclusion · p. 9

  • Takeaways & Limitations

    Task allocation, communication, and signaling can emerge as properties of the optimal solution for a given multi-robot problem model.

    Source: Introduction · p. 2, Conclusion · p. 9

    A policy restricted to sequences of the given macro-actions may have lower value than the optimal Dec-POMDP policy over all history-dependent low-level policies.

    Source: Algorithms · p. 4

Abstract

from arXiv · show

We describe a probabilistic framework for synthesizing control policies for general multi-robot systems, given environment and sensor models and a cost function. Decentralized, partially observable Markov decision processes (Dec-POMDPs) are a general model of decision processes where a team of agents must cooperate to optimize some objective (specified by a shared reward or cost function) in the presence of uncertainty, but where communication limitations mean that the agents cannot share their state, so execution must proceed in a decentralized fashion. While Dec-POMDPs are typically intractable to solve for real-world problems, recent research on the use of macro-actions in Dec-POMDPs has significantly increased the size of problem that can be practically solved as a Dec-POMDP. We describe this general model, and show how, in contrast to most existing methods that are specialized to a particular problem class, it can synthesize control policies that use whatever opportunities for coordination are present in the problem, while balancing off uncertainty in outcomes, sensor information, and information about other agents. We use three variations on a warehouse task to show that a single planner of this type can generate cooperative behavior using task allocation, direct communication, and signaling, as appropriate.

Introduction

The paper motivates replacing hand-designed multi-robot controllers with general-purpose planning from a world model and cost function. It presents MacDec-POMDPs and an approximate solver, then demonstrates that coordination behaviors can emerge in warehouse tasks.

Introduction

  • The paper contrasts general-purpose planning from a world model and cost metric with hand-designed controllers tailored to particular environments or behaviors.Prior approaches include task allocation, formation navigation, cooperative transport, signaling, and communication under limitations,,,, and.Source: Introduction · p. 1
  • Dec-POMDPs represent cooperative multi-agent problems with uncertainty in outcomes, sensors, and information about other agents, but are typically infeasible beyond very small problems.Agents share a reward or cost function while communication limits can prevent them from sharing state.Source: Introduction · p. 1
  • Macro-actions let agents make coordination decisions over temporally extended actions, enabling near-optimal solutions for significantly larger problems than other Dec-POMDP methods.They can represent controllers such as navigating to a waypoint or grasping an object.Source: Introduction · p. 1
  • A MacDec-POMDP planner generated task allocation, direct communication, and signaling as appropriate across three warehouse-task variations.The coordination behaviors emerged as properties of the optimal solution for each model.Source: Introduction · p. 2
  • The paper outlines an approximate, memory-bounded MacDec-POMDP algorithm and a process for modeling robot domains and converting solutions into SMACH task controllers.The approach uses a world model and cost function to generate policies.Source: Introduction · p. 2

Decision Processes

A Dec-POMDP models multiple agents making decentralized decisions from partial observations under uncertainty, while optimizing a shared reward. Its solutions are joint policies, but the general problem is computationally difficult to solve at scale.

Decision Processes

  • Agents act in parallel using locally observable information and receive individual observations, while their decisions affect a shared reward or cost.The model allows uncertainty and decentralized execution because agents have different partial views of the world.Source: Decision Processes · p. 2
  • A Dec-POMDP is specified by agents, states, actions, transition and reward functions, observations, an observation model, and a horizon.The model uses finite sets and discrete time steps here, assumes Markovian state transitions, and permits a flat state that need not factor by agent.Source: Decision Processes · p. 2

Solutions

  • A solution is a joint policy comprising one history-dependent policy per agent, represented as a policy tree or finite-state controller.In a policy tree, vertices specify actions and edges specify observation-conditioned transitions.Source: Solutions · p. 2, Figure 2 · p. 3
  • The objective is to maximize expected cumulative reward from the initial state distribution, and the paper assumes the model is known to all agents.Agents generally do not observe the other agents’ actions or observations, although rewards, transitions, and observations depend on all agents’ decisions.Source: Solutions · pp. 2–3
  • Dec-POMDPs are NEXP-complete, and scalable approaches often rely on strong domain assumptions or provide no solution-quality guarantees.Some advances have been made in optimal algorithms [1, 2, 4, 11, 13, 28], while other approaches assume substantial independence between agents or lack guarantees.Source: Solutions · p. 3

Macro-Actions for Dec-POMDPs

MacDec-POMDPs plan over temporally extended robot controllers, addressing the timing and planning limits of synchronous primitive-action decisions. Their option-based policies support coordination at option choices, with algorithms that trade unrestricted policy optimality for tractable planning when needed.

Macro-Actions for Dec-POMDPs

  • Macro-actions let robots execute controllers for differing durations and defer coordination decisions until agents choose which macro-actions to run.This avoids requiring every robot to finish a controller before the next decision and reduces planning over every primitive time step.Source: Macro-Actions for Dec-POMDPs · p. 3

Model

  • A local option comprises stochastic initiation and termination conditions plus an internal policy, which can depend on an agent’s action-observation history.The formulation also allows simpler reactive policies and conditions based on single observations.Source: Model · p. 3
  • Option histories retain both prior selected options and the action-observation histories at which they were chosen, and can guide later option choices.The joint policy selects options from option histories while each option’s policy determines primitive actions during execution.Source: Model · pp. 3–4

Algorithms

  • Hierarchical optimality maximizes expected value over sequences of the agents’ given options, but may fall short of the unrestricted Dec-POMDP optimum.Including primitive actions among the options can guarantee a globally optimal policy, though the paper says this typically makes little sense for modeling existing robot controllers.Source: Algorithms · p. 4
  • Option-based exhaustive search generates legal deterministic policies until they reach the desired horizon, then selects the highest-value policy at the initial state.This yields a hierarchically optimal deterministic policy within the space of legal option policies that reach that horizon.Source: Dynamic Programming · p. 4
  • Option-based memory-bounded dynamic programming retains at most MaxTrees policy trees per backup, giving time and space complexity linear in the horizon.The fixed cap can make it suboptimal, and reducing MaxTrees can reduce solution quality.Source: Memory-Bounded Dynamic Programming · p. 5

Warehouse Domain

The warehouse experiments apply one planner to three communication settings, demonstrating cooperative box retrieval with no communication, local communication, and signaling. The domain has three robots, two box sizes, unknown depot contents, and large boxes that require two robots to move.

The Warehouse Domain

  • Three robots retrieve small and large boxes from depots with unknown contents and bring them to a drop-off area; large boxes require two robots to move.The planner produces a SMACH controller for each robot, which executes online in a decentralized manner.Source: The Warehouse Domain · p. 5, Warehouse Domain · p. 5
  • Navigation time is stochastic, with greater noise when robots push large boxes; the work assumes these noise parameters are known, though they could be learned through repeated macro-action execution.Source: The Warehouse Domain · pp. 5–6

Scenario 1: No Communication

  • Without communication, robots independently search depots, handle small boxes, and reunite to push a large box that requires help.The planner produces task-allocation-like behavior by accounting for action costs, uncertainty, and future outcomes.Source: Scenario 1: No Communication · p. 6

Scenario 2: Local Communication

  • With local communication, robots return to the waiting room to recruit help, then two robots successfully push the large box while others handle small boxes.The planning process determines how the signals are used.Source: Scenario 2: Local Communication · pp. 6–8

Scenario 3: Global Communication

  • With signaling, a depot light indicates that a large box needs assistance, and another robot responds so two robots can move it to the goal.The planner is not assigned a fixed mapping between light colors and depots.Source: Scenario 3: Global Communication · p. 8

Related Work

Prior multi-robot approaches include behavioral task allocation, LTL-derived controllers, market-based trading, and decision-process models. Their stated assumptions and limitations differ, including task structure, dynamics, communication, and scalability.

  • Behavioral task-allocation methods address loosely or tightly coupled tasks but are heuristic and assume a strong task-class structure.Source: Related Work · p. 8
  • LTL specifications yield reactive controllers guaranteed to satisfy them, but suit non-probabilistic dynamics and discrete behavior constraints, with a separate specification needed for each robot.Source: Related Work · pp. 8–9
  • Market-based methods optimize task allocation through traded value, but are largely aimed at tightly coupled tasks where robots communicate through bidding.Source: Related Work · p. 9
  • Prior decision-process approaches include a low-level Dec-POMDP with limited scalability and an MDP-based controller model whose decision-making is centralized.Source: Related Work · p. 9

Conclusion

The authors argue MacDec-POMDPs are expressive enough to represent multi-robot systems and feasible to solve, with cooperative behaviors emerging from the planner. They identify combining existing macro-actions and improving scalability as future directions.

Conclusion

  • A general-purpose MacDec-POMDP planner generates cooperative behavior, with task allocation, direct communication, and signaling emerging as properties of the optimal solution.The authors describe the model as expressive enough for multi-robot systems while remaining feasible to solve in practice.Source: Conclusion · p. 9
  • Prior solutions for formation navigation, cooperative transport, signaling, and constrained communication may be represented as macro-actions for more complex scenarios.The authors propose this as a way to build on existing research.Source: Conclusion · p. 9
  • Future work includes incorporating state-of-the-art macro-actions, exploiting other structure, improving scalability, and enabling robots to learn models of sensors, dynamics, and other robots.The authors identify these directions as having potential for automated coordination with large heterogeneous teams in complex, uncertain domains.Source: Conclusion · p. 9
Loading 1402.2871v1…