Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning
- URL: http://arxiv.org/abs/2105.01225v1
- Date: Tue, 4 May 2021 00:30:02 GMT
- Title: Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning
- Authors: Murat Cubuktepe, Franti\v{s}ek Blahoudek, and Ufuk Topcu
- Abstract summary: We study the problem of minimizing the resource capacity of autonomous agents cooperating to achieve a shared task.
In a consumption Markov decision process, the agent has a resource of limited capacity.
We develop an algorithm that solves this graph problem in time that is emphpolynomial in the number of agents, target locations, and size of the consumption Markov decision process.
- Score: 19.614913673879474
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of minimizing the resource capacity of autonomous agents
cooperating to achieve a shared task. More specifically, we consider high-level
planning for a team of homogeneous agents that operate under resource
constraints in stochastic environments and share a common goal: given a set of
target locations, ensure that each location will be visited infinitely often by
some agent almost surely. We formalize the dynamics of agents by consumption
Markov decision processes. In a consumption Markov decision process, the agent
has a resource of limited capacity. Each action of the agent may consume some
amount of the resource. To avoid exhaustion, the agent can replenish its
resource to full capacity in designated reload states. The resource capacity
restricts the capabilities of the agent. The objective is to assign target
locations to agents, and each agent is only responsible for visiting the
assigned subset of target locations repeatedly. Moreover, the assignment must
ensure that the agents can carry out their tasks with minimal resource
capacity. We reduce the problem of finding target assignments for a team of
agents with the lowest possible capacity to an equivalent graph-theoretical
problem. We develop an algorithm that solves this graph problem in time that is
\emph{polynomial} in the number of agents, target locations, and size of the
consumption Markov decision process. We demonstrate the applicability and
scalability of the algorithm in a scenario where hundreds of unmanned
underwater vehicles monitor hundreds of locations in environments with
stochastic ocean currents.
Related papers
- AI planning in the imagination: High-level planning on learned abstract
search spaces [68.75684174531962]
We propose a new method, called PiZero, that gives an agent the ability to plan in an abstract search space that the agent learns during training.
We evaluate our method on multiple domains, including the traveling salesman problem, Sokoban, 2048, the facility location problem, and Pacman.
arXiv Detail & Related papers (2023-08-16T22:47:16Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space.
Also, we propose a novel framework to adopt the multi-agent options in the MARL process.
We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
arXiv Detail & Related papers (2022-10-07T00:40:59Z) - DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in
Complex Environments [55.204450019073036]
We present a novel reinforcement learning based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments.
We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it.
We observe improvement up to 14% in terms of task completion time and up-to 40% improvement in terms of computing collision-free trajectories for the robots.
arXiv Detail & Related papers (2022-09-07T00:35:27Z) - Task Allocation with Load Management in Multi-Agent Teams [4.844411739015927]
We present a decision-making framework for multi-agent teams to learn task allocation with the consideration of load management.
We illustrate the effect of load management on team performance and explore agent behaviors in example scenarios.
A measure of agent importance in collaboration is developed to infer team resilience when facing potential overload situations.
arXiv Detail & Related papers (2022-07-17T20:17:09Z) - Resource-Aware Distributed Submodular Maximization: A Paradigm for
Multi-Robot Decision-Making [3.5788754401889022]
Resource-Aware distributed Greedy is the first algorithm to account for each robot's on-board resources independently.
RAG balances the trade-off of centralization, for global near-optimality, vs. decentralization, for near-minimal on-board computation, communication, and memory resources.
arXiv Detail & Related papers (2022-04-15T15:47:05Z) - On the Use and Misuse of Absorbing States in Multi-agent Reinforcement
Learning [55.95253619768565]
Current MARL algorithms assume that the number of agents within a group remains fixed throughout an experiment.
In many practical problems, an agent may terminate before their teammates.
We present a novel architecture for an existing state-of-the-art MARL algorithm which uses attention instead of a fully connected layer with absorbing states.
arXiv Detail & Related papers (2021-11-10T23:45:08Z) - Efficient Strategy Synthesis for MDPs with Resource Constraints [16.774128823546416]
We consider strategy synthesis for the formalism called consumption Markov decision processes.
The presented algorithms work in time with respect to the representation of the model.
arXiv Detail & Related papers (2021-05-05T14:59:30Z) - Resource allocation in dynamic multiagent systems [0.0]
The MG-RAO algorithm is developed to solve resource allocation problems in multi-agent systems.
It shows a 23 - 28% improvement over fixed resource allocation in the simulated environments.
Results also show that, in a volatile system, using the MG-RAO algorithm configured so that child agents model resource allocation for all agents as a whole has 46.5% of the performance of when it is set to model multiple groups of agents.
arXiv Detail & Related papers (2021-02-16T17:56:23Z) - Asynchronous Multi Agent Active Search [6.587280549237275]
We propose two distinct active search algorithms called SPATS (Sparse Parallel Asynchronous Thompson Sampling) and LATSI (LAplace Thompson Sampling with Information gain)
We consider that targets are sparsely located around the environment in keeping with compressive sensing assumptions.
We provide simulation results as well as theoretical analysis to demonstrate the efficacy of our proposed algorithms.
arXiv Detail & Related papers (2020-06-25T22:17:20Z) - Randomized Entity-wise Factorization for Multi-Agent Reinforcement
Learning [59.62721526353915]
Multi-agent settings in the real world often involve tasks with varying types and quantities of agents and non-agent entities.
Our method aims to leverage these commonalities by asking the question: What is the expected utility of each agent when only considering a randomly selected sub-group of its observed entities?''
arXiv Detail & Related papers (2020-06-07T18:28:41Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination.
We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
arXiv Detail & Related papers (2020-05-27T01:10:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.