Rolf-David Bergdoll – Publications
(Show all abstracts)
(Hide all abstracts)
2023
-
Pascal Bachor, Rolf-David Bergdoll and Bernhard Nebel.
The Multi-Agent Transportation Problem.
In
Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 11525-11532.
2023.
(Show abstract)
(Hide abstract)
(Online; DOI)
We introduce the multi-agent transportation (MAT) problem,
where agents have to transport containers from their starting
positions to their designated goal positions. Movement takes place
in a common environment where collisions between agents and between
containers must be avoided. In contrast to other frameworks such as
MAPF or MAPD, the agents are allowed to separate from the containers
at any time, which allows for plans in scenarios that might
otherwise be unsolvable and has the potential to reduce the
makespan. We present a complexity analysis establishing
NP-completeness and show how the problem can be reduced to a
sequence of SAT problems when optimizing for makespan. Finally, the
implementation is empirically evaluated relative to input
characteristics, and it is compared to some variants of the MAT
problem and a CBS-based MAPD implementation.
2016
-
Marius Lindauer, Rolf-David Bergdoll and Frank Hutter.
An Empirical Study of Per-instance Algorithm Scheduling.
In
Proceedings of the 10th Learning and Intelligent Optimization Conference
(LION 10), pp. 253-259.
2016.
(Show abstract)
(Hide abstract)
(PDF)
Algorithm selection is a prominent approach to improve a system’s performance by selecting a well-performing algorithm from a portfolio for an instance at hand. One extension of the traditional algorithm selection problem is to not only select one single algorithm but a schedule of algorithms to increase robustness. Some approaches exist for solving this problem of selecting schedules on a per-instance basis (e.g., the Sunny and 3S systems), but to date, a fair and thorough comparison of these is missing. In this work, we implement Sunny’s approach and dynamic schedules inspired by 3S in the flexible algorithm selection framework flexfolio to use the same code base for a fair comparison. Based on the algorithm selection library (ASlib), we perform the first thorough empirical study on the strengths and weaknesses of per-instance algorithm schedules. We observe that on some domains it is crucial to use a training phase to limit the maximal size of schedules and to select the optimal neighborhood size of k-nearest-neighbor. By modifying our implemented variants of the Sunny and 3S approaches in this way, we achieve strong performance on many ASlib benchmarks and establish new state-of-the-art performance on 3 scenarios.
