Effective Planning in Resource-Competition Problems by Task Decomposition

Effective planning while competing for limited resources is crucial in many real-world applications such as on-demand transport companies competing for passengers. Planning techniques therefore have to take into account possible actions of an adversarial agent. Such a challenge that can be tackled by leveraging game-theoretical methods such as Double Oracle. This paper aims at the scalability issues arising from combining planning techniques with Double Oracle. In particular, we propose an abstraction-based heuristic for deciding how resources will be collected (e. g. which car goes for which passenger and in which order) and we propose a method for decomposing planning tasks into smaller ones (e. g. generate plans for each car separately). Our empirical evaluation shows that our proposed approach considerably improves scalability compared to the state-of-the-art techniques.

Authors

• Lukás Chrpa
• Pavel Rytír
• Andrii Nyporko
• Rostislav Horcík
• Stefan Edelkamp

Keywords

• Adversarial Search
• Problem Solving Using Search