Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a fail first strategy by using the Min-domain property (Haralick and Elliott...
详细信息
Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a fail first strategy by using the Min-domain property (Haralick and Elliott, Artif Intel 14:263-313, 1980;Bessiere and Regin, Mac and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Proc. CP 96, pp. 61-75, Cambridge, MA, 1996;Smith and Grant, Trying harder to fail first. In European Conference on Artificial Intelligence, pp. 249-253, 1998;Dechter, Constraint Processing. Morgan Kaufman, 2003). Ordering heuristics have been introduced recently to asynchronous backtracking (ABT), for distributed constraints satisfaction (DisCSP) (Zivan and Meisels, Dynamic ordering for asynchronous backtracking on discsps. In CP-2005, pp. 32-46, Sigtes (Barcelona), Spain, 2005). However, the pioneering study of dynamically ordered ABT, ABT_DO, has shown that a straightforward implementation of the Min-domain heuristic does not produce the expected improvement over a static ordering. The present paper proposes an asynchronous dynamic ordering which does not follow the standard restrictions on the position of reordered agents in ABT_DO. Agents can be moved to a position that is higher than that of the target of the backtrack. Combining the Nogood-triggered heuristic and the Min-domain property in this new class of heuristics results in the best performing version of ABT_DO. The new version of retroactively ordered ABT is faster by a large factor than the best form of ABT.
We consider multi-agent decision making problems in which agents need to communicate with other agents to make socially optimal decisions but, at the same time, have some private information that they do not want to s...
详细信息
ISBN:
(纸本)9781450342391
We consider multi-agent decision making problems in which agents need to communicate with other agents to make socially optimal decisions but, at the same time, have some private information that they do not want to share. Abstract argumentation has been widely used in both single-agent and multi-agent decision making problems, because of its ability for reasoning with incomplete and conflicting information. In this work, we propose an abstract argumentation-based knowledge representation and communication protocol, such that agents can find socially optimal strategies by only disclosing the 'necessary' and 'disclosable' information. We prove that our protocol is sound, efficient, of perfect information security and guaranteed to terminate.
We consider multi-agent decision making problems in which agents need to communicate with other agents to make socially optimal decisions but, at the same time, have some private information that they do not want to s...
详细信息
ISBN:
(纸本)9781510855083
We consider multi-agent decision making problems in which agents need to communicate with other agents to make socially optimal decisions but, at the same time, have some private information that they do not want to share. Abstract argumentation has been widely used in both single-agent and multi-agent decision making problems, because of its ability for reasoning with incomplete and conflicting information. In this work, we propose an abstract argumentation-based knowledge representation and communication protocol, such that agents can find socially optimal strategies by only disclosing the 'necessary' and 'disclosable' information. We prove that our protocol is sound, efficient, of perfect information security and guaranteed to terminate.
A new general framework for agent cooperation and coordination in solving distributed 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 solving distributed 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.
暂无评论