We are excited to announce that the repository will soon undergo an upgrade, featuring a new look and feel along with several enhanced features to improve your experience. Please be on the lookout for further updates and announcements regarding the launch date. We appreciate your support and look forward to unveiling the improved platform soon.
dc.contributor.author | Timm, Nils![]() |
|
dc.contributor.author | Botha, Josua![]() |
|
dc.date.accessioned | 2023-09-04T10:38:00Z | |
dc.date.available | 2023-09-04T10:38:00Z | |
dc.date.issued | 2022-09 | |
dc.description.abstract | Multi-agent systems for resource allocation (MRAs) have been introduced as a concept for modelling competitive resource allocation problems in distributed computing. An MRA is composed of a set of agents and a set of resources. Each agent has goals in terms of allocating certain resources. For MRAs it is typically of importance that they are designed in a way such that there exists a strategy that guarantees that all agents will achieve their goals. The corresponding model checking problem is to determine whether such a winning strategy exists or not, and the synthesis problem is to actually build the strategy. While winning strategies ensure that all goals will be achieved, following such strategies does not necessarily involve an optimal use of resources. In this paper, we present a technique that allows to synthesise cost-optimal solutions to distributed resource allocation problems. We consider a scenario where system components such as agents and resources involve costs. A multi-agent system shall be designed that is cost-minimal but still capable of accomplishing a given set of goals. Our approach synthesises a winning strategy that minimises the cumulative costs of the components that are required for achieving the goals. The technique is based on a propositional logic encoding and a reduction of the synthesis problem to the maximum satisfiability problem (Max-SAT). Hence, a Max-SAT solver can be used to perform the synthesis. From a truth assignment that maximises the number of satisfied clauses of the encoding a cost- optimal winning strategy as well as a cost-optimal system can be immediately derived. | en_US |
dc.description.department | Computer Science | en_US |
dc.description.librarian | hj2023 | en_US |
dc.description.uri | https://www.eptcs.org | en_US |
dc.identifier.citation | Timm, N. & Botha, J. 'Synthesis of cost-optimal multi-agent systems for resource allocation', Vlad Rusu (Ed.) Sixth Working Formal Methods Symposium (FROM 2022) Electronic Proceedings in Theoretical Computer Science, 369, 2022, pp. 67–82, doi:10.4204/EPTCS.369.5. | en_US |
dc.identifier.issn | 2075-2180 (online) | |
dc.identifier.other | 10.4204/EPTCS.369.5 | |
dc.identifier.uri | http://hdl.handle.net/2263/92159 | |
dc.language.iso | en | en_US |
dc.publisher | Open Publishing Association | en_US |
dc.rights | © N. Timm & J. Botha. This work is licensed under the Creative Commons Attribution License. | en_US |
dc.subject | Multi-agent systems for resource allocation (MRAs) | en_US |
dc.subject | Cost optimization | en_US |
dc.subject | Resource allocation problems | en_US |
dc.subject | Multi-agent systems | en_US |
dc.subject | Maximum satisfiability problem (Max-SAT) | en_US |
dc.title | Synthesis of cost-optimal multi-agent systems for resource allocation | en_US |
dc.type | Article | en_US |