Incremental Dynamic Controllability in Cubic Worst-Case Time

摘要: It is generally hard to predict the exact duration of an action. Uncertainty in durations often modeled temporal planning by use upper bounds on durations, with assumption that if action happens be executed more quickly, plan will still succeed. However, this false: If we finish cooking too early, dinner cold before everyone ready eat. Simple Temporal Problems (STPUs) allow us model such situations. An STPU-based planner must verify plans it generates are executable, captured property dynamic controllability. The Efficient IDC (EIDC) algorithm can do incrementally during planning, amortized complexity per step O(n3) but a worst-case O(n4). In paper show run-time EIDC does occur, leading repeated reprocessing nodes STPU while verifying controllability property. We present new version algorithm, EIDC2, which through optimal ordering avoids need for reprocessing. This gives EIDC2 strictly lower run-time, making fastest known STPUs.