NDLI: Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects

Content Provider	Springer Nature Link
Author	Khan, Majid Ali Turgut, Damla Bölöni, Ladislau
Copyright Year	2010
Abstract	We consider a problem domain where coalitions of agents are formed in order to execute tasks. Each task is assigned at most one coalition of agents, and the coalition can be reorganized during execution. Executing a task means bringing it to one of the desired terminal states, which might take several time steps. The state of the task evolves even if no coalition is assigned to its execution and depends nondeterministically on the cumulative actions of the agents in the coalition. Furthermore, we assume that the reward obtained for executing a task evolves in time: the more the execution of the task is delayed, the lesser the reward. A representative example of this class of problems is the allocation of firefighters to fires in a disaster rescue environment. We describe a practical methodology through which a problem of this class can be encoded as a Markov Decision Process. Due to the three levels of factoring in the resulting MDP (the states, actions and rewards are composites of the original features of the problem) the resulting MDP can be directly solved only for small problem instances. We describe two methods for parallel decomposition of the MDP: the MDP RSUA approach for random sampling and uniform allocation and the MDP REUSE method which reuses the lower level MDP to allocate resources to the parallel subproblems. Through an experimental study which models the problem domain using the fire simulation components of the Robocup Rescue simulator, we show that both methods significantly outperform heuristic approaches and MDP REUSE provides an overall higher performance than MDP RSUA.
Starting Page	415
Ending Page	438
Page Count	24
File Format	PDF
ISSN	13872532
Journal	Autonomous Agents and Multi-Agent Systems
Volume Number	22
Issue Number	3
e-ISSN	15737454
Language	English
Publisher	Springer US
Publisher Date	2010-05-14
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Optimization Coalition formation Agents Computer Systems Organization and Communication Networks Computing Methodologies Artificial Intelligence (incl. Robotics) User Interfaces and Human Computer Interaction Software Engineering/Programming and Operating Systems
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Sequentially optimal repeated coalition formation under uncertainty

Coalition formation for task allocation: theory and algorithms

Considering inter-task resource constraints in task allocation

Power and welfare in bargaining for coalition structure formation

Computational logic-based agents

Dynamically generated commitment protocols in open systems

An influence diagram based multi-criteria decision making framework for multirobot coalition formation

Agents for games and simulations

Multi-goal economic search using dynamic search structures

Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects

Similar Documents

Sequentially optimal repeated coalition formation under uncertainty

Coalition formation for task allocation: theory and algorithms

Considering inter-task resource constraints in task allocation

Power and welfare in bargaining for coalition structure formation

Computational logic-based agents

Dynamically generated commitment protocols in open systems

An influence diagram based multi-criteria decision making framework for multirobot coalition formation

Agents for games and simulations

Multi-goal economic search using dynamic search structures

Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects