University of Macedonia Economic and Social Sciences
Distributed constraint optimization, resource allocation and scheduling in large scale agent networks
Abstract
dc:descriptionThe thesis explores new directions pertaining to methods for scheduling andallocating atomic and complex tasks in large-scale networks of homogeneous orheterogeneous cooperative agents. Tasks are requests for resources managed by theagents that populate the network. The proposed methods encapsulate the concepts ofsearching, task allocation and scheduling seamlessly in decentralized processes.Consequently, there is no need for accumulated or centralized knowledge.Furthermore, centralized coordination is also not necessary. Efficient searching foragent groups that can facilitate the scheduling of tasks is accomplished through theuse of a dynamic overlay structure of gateway agents and the exploitation of routingindices. Gateway agents are network nodes that due to specific topological issues havethe ability to accumulate limited knowledge relevant to the resources available in theirimmediate neighbourhood. They issue, keep and constantly update routing indicesbased on their view on local resources. Routing indices are used for directing requestsχfor resources towards parts of the network where the probability of them beingserved is high. Efficient routing leads to formation of agent teams that try to breakdown each task into smaller pieces and allocate the appropriate resources to it. Thetask allocation and the scheduling of complex tasks are accomplished by combiningdynamic reorganization of agent groups and distributed constraint optimizationmethods. After a complex task has been broken down into subtasks, constraints thatmay exist between the derived subtasks or constraints inherent to the resourceallocation procedure are modelled as a distributed constraint optimization problem.The newly formed agent team that has been assigned the problem tries to solve itoptimizing the cost due to constraints, at the same time. Upon success the requestedresources are allocated accordingly. Otherwise the complex task is forwarded on itsentirety so as to another agent team can be formed and try to solve the problemExperiments have demonstrated promising results.
Degree
thesis:*- Grantor dc:publisher
- University of Macedonia Economic and Social Sciences
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Karagiannis, Panagiotis
- Καραγιάννης, Παναγιώτης
Subjects
dc:subject × 14Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/30444