The Art Gallery problem asks to find a minimum subset of vertices in a polygon that are sufficient to observe the interior. This problem arises in a variety of multiagent systems, including robotics, sensor networks, ...
详细信息
ISBN:
(纸本)9780982657119
The Art Gallery problem asks to find a minimum subset of vertices in a polygon that are sufficient to observe the interior. This problem arises in a variety of multiagent systems, including robotics, sensor networks, wireless networking, and surveillance. Despite the fact that the centralized version of the problem has been extensively studied for the past thirty years, there is relatively little in the literature describing distributed solutions to the problem that have desirable guarantees in both runtime and optimality. We propose and analyze a new distributed algorithm for approximating a solution to this problem and a number of its variants that runs in a linear number of communication rounds with respect to the number of nodes (independent of the topology of the network), and, under assumptions on the embedding of the edge weights, will run in a logarithmic number of communication rounds producing solutions within a constant factor of optimal.
Multi-agent systems often require runtime planning, which remains an open problem due to the existing gap between planning and execution in practice. Extensive research has been carried out in centralised planning for...
详细信息
ISBN:
(纸本)9781510855076
Multi-agent systems often require runtime planning, which remains an open problem due to the existing gap between planning and execution in practice. Extensive research has been carried out in centralised planning for single-agent systems, but so far decentralised multi-agent planning has not been fully explored. In this paper, we extend existing multi-agent platforms to enable decentralised planning at runtime. In particular, we put forward a planning and execution framework called Decentralised Online Multi-Agent Planning (DOMAP). Experiments with a planning domain we developed on flooding disaster scenarios show that DOMAP outperforms 4 other state-of-the-art multi-agent planners, particularly in the most difficult problems.
The problem of multiagent Gaussian inference in a dynamic environment, also known as distributed Kalman filtering, is formulated into the framework of message passing algorithms. Upon generalizing the derivation of th...
详细信息
ISBN:
(纸本)9780982657119
The problem of multiagent Gaussian inference in a dynamic environment, also known as distributed Kalman filtering, is formulated into the framework of message passing algorithms. Upon generalizing the derivation of the standard Kalman filter to the distributed case, we propose novel solutions that outperform current state of the art techniques.
Significant research progress and understanding about the nature of coordination has been made over the years. Development of the DCOP and DEC-MDP frameworks in the past decade has been especially important. Although ...
详细信息
ISBN:
(纸本)9781634391313
Significant research progress and understanding about the nature of coordination has been made over the years. Development of the DCOP and DEC-MDP frameworks in the past decade has been especially important. Although these advances are very important for multi-agent coordination theory, they overlook a set of coordination behaviors and phenomena that have been observed empirically by many researchers since the early years of the field. The goal of this paper is to challenge researchers in multi-agent coordination to develop a comprehensive formal framework that explains these empirical observations.
A new general framework for agent cooperation and coordination in solvingdistributed constraint satisfaction problems (DCSPs) is presented. The Asynchronous Partitioning Framework (APF) first partitions agents into g...
详细信息
ISBN:
(纸本)9780982657119
A new general framework for agent cooperation and coordination in solvingdistributed constraint satisfaction problems (DCSPs) is presented. The Asynchronous Partitioning Framework (APF) first partitions agents into groups of agents, based on some heuristic, prior to any search being conducted. During the partitioning phase one of the agents in each group is assigned the role of a group leader. Next, two distinct types of search processes among the agents are performed concurrently. The first type of search is conducted within each group, in parallel and asynchronously to all searches in other groups. The second type of search, the global search, is conducted between the groups, and treats each group as if it is a single agent represented by its group leader. The structure of the groups remains static throughout the search processes. Two distinct algorithms implementing APF are presented, and the advantages of APF are evaluated experimentally.
The runtime of winner determination for each round of a sequential bundle-bid auction (= SBB auction) has recently been shown to be linear in the number of submitted bids, which makes SBB auctions appealing for solvin...
详细信息
ISBN:
(纸本)9781615673346
The runtime of winner determination for each round of a sequential bundle-bid auction (= SBB auction) has recently been shown to be linear in the number of submitted bids, which makes SBB auctions appealing for solving cooperative task-assignment problems. In this paper, we introduce the Shrewd (= SHrewd Resource Efficient Winner Determination) algorithm, whose runtime is linear in the number of submitted bids but typically much smaller than the runtime of the existing winner-determination algorithm for SBB auctions, making them feasible for larger bundle sizes.
We present a multiagent organization for data interpretation and fusion in which each agent uses an encapsulated Bayesian network for knowledge representation, and agents communicate by exchanging beliefs (marginal po...
详细信息
ISBN:
(纸本)9780982657119
We present a multiagent organization for data interpretation and fusion in which each agent uses an encapsulated Bayesian network for knowledge representation, and agents communicate by exchanging beliefs (marginal posterior probabilities) on shared variables. We call this organization an Agent-Encapsulated Bayesian Network (AEBN) system. Communication of probabilities among agents leads to rumors, i.e. potential double counting of information. We propose a new and correct method to compensate for rumors in AEBN systems by passing extended messages that contain joint probabilities.
Partial Cooperation is a paradigm and a corresponding model for representing multi-agent systems in which agents are willing to cooperate in order to achieve a global goal, as long as some minimal threshold on their p...
详细信息
Partial Cooperation is a paradigm and a corresponding model for representing multi-agent systems in which agents are willing to cooperate in order to achieve a global goal, as long as some minimal threshold on their personal utility is satisfied. distributed local search algorithms were proposed in order to solve asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative. We contribute by: 1) extending the partial cooperative model to allow it to represent dynamic cooperation intentions, affected by changes in agents' wealth, in accordance with social studies literature. 2) proposing a novel local search algorithm in which agents receive indications of others' preferences on their actions and thus, can perform actions that are socially beneficial. Our empirical study reveals the advantage of the proposed algorithm in multiple benchmarks. Specifically, on realistic meeting scheduling problems it overcomes limitations of standard local search algorithms.
Multi-agent scheduling has received significant attention in tackling the problem of load balancing and task allocation in distributed systems. Apart from dividing the work through decentralization, we consider dynami...
详细信息
ISBN:
(纸本)9781450363099
Multi-agent scheduling has received significant attention in tackling the problem of load balancing and task allocation in distributed systems. Apart from dividing the work through decentralization, we consider dynamicity because allocation of tasks must be concurrent with their execution, and adaptation because tasks must be reallocated when a disruptive event is performed. We will assume that agents are fully distributed and cooperative in order to optimize the global runtime, i.e a system-centric metric rather than user-centric metrics. We will also assume that a task can be performed by any single agent without preemption and precedence order. Moreover, tasks have no deadlines, are indivisible and not *** follow a market-based approach to tackle the multi-agent situated task allocation problem. In order to improve load balancing, agents adopt a locality-based strategy in concurrent one-to-many negotiations for task delegations. The task reallocation is dynamic since the negotiation process is iterated and concurrent with the tasks processing. Moreover, the system is adaptive to disruptive events, e.g. task consumptions. As a practical application, we consider the distributed deployment of the MapReduce design pattern for processing large datasets. Our preliminary empirical results show that, for such an application, the locality-based strategy improves the runtime.
In the context of multi-agent hypothetical reasoning, agents typically have partial knowledge about their environments, and the union of such knowledge is still incomplete to represent the whole world. Thus, given a g...
详细信息
ISBN:
(纸本)9780982657171
In the context of multi-agent hypothetical reasoning, agents typically have partial knowledge about their environments, and the union of such knowledge is still incomplete to represent the whole world. Thus, given a global query they need to collaborate with each other to make correct inferences and hypothesis, whilst maintaining global constraints. There are many real world applications in which the confidentiality of agent knowledge is of primary concern, and hence the agents may not share or communicate all their information during the collaboration. This extra constraint gives a new challenge to multi-agent reasoning. This paper shows how this dichotomy between "open communication" in collaborative reasoning and protection of confidentiality can be accommodated, by extending a general-purpose distributed abductive logic programming system for multi-agent hypothetical reasoning with confidentiality. Specifically, the system computes consistent conditional answers for a query over a set of distributed normal logic programs with possibly unbound domains and arithmetic constraints, preserving the private information within the logic programs.
暂无评论