Faster Conflict Generation for Dynamic Controllability

Faster Conflict Generation for Dynamic Controllability

Nikhil Bhargava, Tiago Vaquero, Brian Williams

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4280-4286. https://doi.org/10.24963/ijcai.2017/598

In this paper, we focus on speeding up the temporal plan relaxation problem for dynamically controllable systems. We take a look at the current best-known algorithm for determining dynamic controllability and augment it to efficiently generate conflicts when the network is deemed uncontrollable. Our work preserves the O(n^3) runtime of the best available dynamic controllability checker and improves on the previous best runtime of O(n^4) for extracting dynamic controllability conflicts. We then turn our attention to temporal plan relaxation tasks and show how we can leverage our work on conflicts and the structure of the network to efficiently make incremental updates intended to restore dynamic controllability by relaxing constraints. Our new algorithm, RelaxIDC, has the same asymptotic runtime as previous algorithms but sees dramatic empirical improvements over the course of repeated dynamic controllability checks.
Keywords:
Planning and Scheduling: Scheduling
Planning and Scheduling: Search in Planning and Scheduling
Uncertainty in AI: Uncertainty in AI