Variable-Delay Controllability

Variable-Delay Controllability

Nikhil Bhargava, Christian Muise, Brian Williams

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4660-4666. https://doi.org/10.24963/ijcai.2018/648

In temporal planning, agents must schedule a set of events satisfying a set of predetermined constraints. These scheduling problems become more difficult when the duration of certain actions are outside the agent's control. Delay controllability is the generalized notion of whether a schedule can be constructed in the face of uncertainty if the agent eventually learns when events occur. Our work introduces the substantially more complex setting of determining variable-delay controllability, where an agent learns about events after some unknown but bounded amount of time has passed. We provide an efficient O(n^3) variable-delay controllability checker and show how to create an execution strategy for variable-delay controllability problems. To our knowledge, these essential capabilities are absent from existing controllability checking algorithms. We conclude by providing empirical evaluations of the quality of variable-delay controllability results as compared to approximations that use fixed delays to model the same problems.
Keywords:
Planning and Scheduling: Planning under Uncertainty
Planning and Scheduling: Planning and Scheduling