Auction-based scheduling

Avni G, Mallik K, Sadhukhan S. 2024. Auction-based scheduling. 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 14572, 153–172.

Download
OA 2024_LNCS_Avni.pdf 508.19 KB [Published Version]

Conference Paper | Published | English

Scopus indexed
Author
Avni, GuyISTA ; Mallik, KaushikISTA ; Sadhukhan, Suman
Series Title
LNCS
Abstract
Sequential decision-making tasks often require satisfaction of multiple, partially-contradictory objectives. Existing approaches are monolithic, where a single policy fulfills all objectives. We present auction-based scheduling, a decentralized framework for multi-objective sequential decision making. Each objective is fulfilled using a separate and independent policy. Composition of policies is performed at runtime, where at each step, the policies simultaneously bid from pre-allocated budgets for the privilege of choosing the next action. The framework allows policies to be independently created, modified, and replaced. We study path planning problems on finite graphs with two temporal objectives and present algorithms to synthesize policies together with bidding policies in a decentralized manner. We consider three categories of decentralized synthesis problems, parameterized by the assumptions that the policies make on each other. We identify a class of assumptions called assume-admissible for which synthesis is always possible for graphs whose every vertex has at most two outgoing edges.
Publishing Year
Date Published
2024-04-05
Proceedings Title
30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems
Acknowledgement
This work was supported in part by the ERC project ERC-2020-AdG 101020093 and by ISF grant no. 1679/21.
Volume
14572
Page
153-172
Conference
TACAS: Tools and Algorithms for the Construction and Analysis of Systems
Conference Location
Luxembourg City, Luxembourg
Conference Date
2024-04-06 – 2024-04-11
ISSN
eISSN
IST-REx-ID

Cite this

Avni G, Mallik K, Sadhukhan S. Auction-based scheduling. In: 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Vol 14572. Springer Nature; 2024:153-172. doi:10.1007/978-3-031-57256-2_8
Avni, G., Mallik, K., & Sadhukhan, S. (2024). Auction-based scheduling. In 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (Vol. 14572, pp. 153–172). Luxembourg City, Luxembourg: Springer Nature. https://doi.org/10.1007/978-3-031-57256-2_8
Avni, Guy, Kaushik Mallik, and Suman Sadhukhan. “Auction-Based Scheduling.” In 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 14572:153–72. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-57256-2_8.
G. Avni, K. Mallik, and S. Sadhukhan, “Auction-based scheduling,” in 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Luxembourg City, Luxembourg, 2024, vol. 14572, pp. 153–172.
Avni G, Mallik K, Sadhukhan S. 2024. Auction-based scheduling. 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 14572, 153–172.
Avni, Guy, et al. “Auction-Based Scheduling.” 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, vol. 14572, Springer Nature, 2024, pp. 153–72, doi:10.1007/978-3-031-57256-2_8.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2024-05-22
MD5 Checksum
dbeb123510997886d11925aedbf9c400


Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2310.11798

Search this title in

Google Scholar
ISBN Search