APPROXIMATE REASONING ABOUT TEMPORAL CONSTRAINTS IN REAL TIME PLANNING AND SEARCH

Artificial Intelligence (AI) systems are being increasingly applied to challenging real time problems. Real time AI systems typically have to operate under stringent temporal constraints. These temporal constraints can be either explicit (e.g., a system may have to respond within a given deadline) or implicit (e.g., there may be no explicit deadlines but optimal response times may be desired). This paper is concerned with approximate reasoning about temporal constraints present either explicitly or implicitly in real time systems. A graph search procedure is used as the conceptual representation for real time reasoning and planning. The cost of a response consists of the cost to plan a solution and the cost to execute the chosen solution. There is an intimate tradeoff between these two costs. Algorithms for approximate reasoning about such tradeoffs are discussed in this paper. In particluar, a heuristic algorithm called NORA is proposed for determining the tradeoff between planning and execution costs and a formal proof is given for. the performance bound obtained. The application of NORA to the domains of semantic query optimization and the A * heuristic search algorithm is described. 1 2