Share Email Print
cover

Proceedings Paper

Symbolic planning with metric time
Author(s): T. Richard MacMillan
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

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.

Paper Details

Date Published: 1 March 1992
PDF: 12 pages
Proc. SPIE 1707, Applications of Artificial Intelligence X: Knowledge-Based Systems, (1 March 1992); doi: 10.1117/12.56897
Show Author Affiliations
T. Richard MacMillan, MITRE Corp. (United States)


Published in SPIE Proceedings Vol. 1707:
Applications of Artificial Intelligence X: Knowledge-Based Systems
Gautam Biswas, Editor(s)

© SPIE. Terms of Use
Back to Top