Symbolic planning with metric time
T. Richard MacMillan · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1992
Most AI planning systems have considered time in a qualitative way only. For example, a plan may require one action to come 'before' another. Metric time enables AI planners to represent action durations and reason over quantitative temporal constraints such as windows of opportunity. This paper presents preliminary results observed while developing a theory of multi-agent adversarial planning for battle management research. Quantitative temporal reasoning seems essential in this domain. For example, Orange may plan to block Blue's attack by seizing a river ford which Blue must cross, but only if Orange can get there during the window of opportunity while Blue is approaching the ford but has not yet arrived. In nonadversarial multi-agent planning, metric time enables planners to detect windows of opportunity for agents to help or hinder each other. In single-agent planning, metric time enables planners to reason about deadlines, temporally constrained resource availability, and asynchronous processes which the agent can initiate and monitor. Perhaps surprisingly, metric time increases the computational complexity of planning less than might be expected, because it reduces the computational complexity of modal truth criteria. To make this observation precise, we review Chapman's analysis to modal truth criteria and describe a tractable heuristic criterion, 'worst case necessarily true.' Deciding if a proposition is worst case necessarily true, in a single-agent plan with n steps, requires O(n) computations only if qualitative temporal information is used. We show how it can be decided in O(log n) using metric time.