Time-Situated Reasoning Within Tight Deadlines and Realistic Space and Computation Bounds

Abstract

We develop an effective representational and inferential framework for fully deadline-coupled planning and acting in hard, non-extensible, unforeseen deadline situations. While meta-planning is the usual proposal for reasoning about the reasoning process, few formalisms to date acknowledge that meta-planning takes time too. In traditional mechanisms, the planning effort is treated as a different kind of beast, not an action itself that takes time. A paradigmatic time-critical problem scenario was chosen: Nell, Dudley and the railroad tracks. Nell is tied to the railroad tracks and a train approaches. Dudley, the agent, must formulate a plan to save her and carry it out before the oncoming train reaches her. We design a time-situated inference mechanism based on an underlying framework of active logics. We demonstrate the generality of our formal methods by using them to tackle projection issues in some real-time versions of the canonical Yale Shooting Problem. In a realistic setting, an agent planning under time-pressure must also measure up to two other crucial resource limitations as well, namely, space and computation bounds. We introduce a limited short-term memory combined with a primitive relevance mechanism, and a limited-capacity inference engine. We propose heuristics to maximize an agent's chances of meeting a deadline in this enhanced framework. Logical omniscience, and inferential closure are computational impossibilities for an agent embedded in a real environment. We construct a variation on active logics for which there is a sound and complete modal semantics. It overcomes the key obstacle of closure under consequence. This result illustrates the similarity and differences between active-logic approaches to knowledge and belief, and previous modal approaches. To summarize the novel elements in this dissertation: we present a declarative planning framework based on active logics which can account for all the time taken to plan, making it suitable for deadline situations. We describe a novel treatment of temporal projection in a real-time setting, a modal semantics for active logics, and additional results in reasoning under resource limitations. Several aspects of this design have been implemented and tested.