Los, J. (2016) Preference-Based Improvements on Solutions of Multi-Agent Temporal Problems by Automated Negotiation. Master's Thesis / Essay, Artificial Intelligence.
|
Text
AI-MAI-2016-J.LOS.pdf - Published Version Download (785kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
Toestemming.pdf - Other Restricted to Backend only Download (823kB) |
Abstract
Scheduling problems arise in numerous real-world situations. In many of them, different agents are each responsible for their own part of a scheduling problem, although they are dependent on the schedules of other agents. Hence, the agents have to adjust their schedules to certain external constraints. General approaches for solving multi-agent scheduling problems return an arbitrary solution that satisfies all constraints, regardless of the quality of the schedule. However, in many cases, agents have certain preferences with respect to the schedule, for example, they want to do tasks in a certain order, to complete all tasks as early as possible, or to have a break between two tasks. In the current literature, scheduling frameworks with preferences are only defined for single-agent problems. We therefore extend the work on Simple Temporal Problems and Disjunctive Temporal Problems, and develop the frameworks of Multi-agent Simple Temporal Problems with Preferences and Multi-agent Disjunctive Temporal Problems with Preferences. Having defined frameworks for these problems, we develop methods for solving them. Existing approaches for Multi-agent Temporal Problems search for a decoupling, i.e. a collection of local subproblems, one for each agent, such that any combination of solutions to the local subproblems is a solution to the original shared problem. By this, the agents can solve the subproblems in parallel, and their privacy is respected. We propose to improve existing decoupling solutions, with the preferences of the different agents as performance criterion, by applying automated negotiation. Automated negotiation is in general a computationally efficient distributed process in which the agents do not have to reveal all their preference information, that deals with both cooperation and competition, and hence fits well into the multi-agent scheduling context. Two types of negotiation protocols are developed: First, we propose post-decoupling protocols for finding Pareto-improvements on a given decoupling. Next, we develop pre-decoupling negotiation protocols that can be applied in existing decoupling algorithms to improve the decoupling. Our results show that both the post-decoupling and the pre-decoupling negotiation methods improve existing decoupling algorithms with respect to the preferences of the agents. For a larger number of agents, the pre-decoupling negotiation algorithms turn out to be better. Furthermore, we compare our solutions with methods that have the flexibility of a solution as performance metric and show that our solutions are more flexible. Finally, the possibilities for further increasing social welfare by letting the agents also make non-Pareto improvements are discussed.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Degree programme: | Artificial Intelligence |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 15 Feb 2018 08:25 |
| Last Modified: | 15 Feb 2018 08:25 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/14574 |
Actions (login required)
 |
View Item |