Effective Planning in Resource-Competition Problems by Task Decomposition

Authors

  • Lukáš Chrpa Czech Technical University in Prague
  • Pavel Rytíř Czech Technical University in Prague
  • Andrii Nyporko Czech Technical University in Prague
  • Rostislav Horčík Czech Technical University in Prague
  • Stefan Edelkamp Czech Technical University in Prague

Keywords:

Adversarial Search, Problem Solving Using Search

Abstract

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.

Downloads

Published

2022-07-17