Volume 7: January - December 1997

Issue 1: 1997


How to (plan to) meet a deadline between now and then

  • How to (plan to) meet a deadline between now and then
  • M. Nirkhe1, S. Kraus1, M. Miller3 and D. Perlis4 1Microsoft Corporation, One Microsoft Way, Redmond, WA 98052, USA. Email: madhuran@microsoft.com, 2Department of Mathematics and Computer Science, Bar Ilan Unviersity, Ramat Gan, 52900 Israel. Email: sarit@bimacs.cs.biu.ac.il, 3Intelligent Automation, Inc., Rockville, MD 20850, USA. Email: mm@i-a-i.com and 3Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park, MD 20742, USA. Email: perlis@cs.umd.edu


    In planning situations involving tight deadlines, a commonsense reasoner may spend a substantial amount of the available time in reasoning towards and about the formulation of the (partial) plan. This reasoning involves, but is not limited to, (partial) plan formulation, making decisions about available and conceivable alternatives, plan sequencing, and also plan failure and revision. However, the time taken in reasoning about a plan brings the deadline closer. The reasoner should therefore take account of the passage of time during that same reasoning, and this accounting must continuously affect every decision under time-pressure. Step-logics were introduced as a mechanism for reasoning situated in time. We employ an extension of them here, called 'active logics', to create a logic-based planner that lets a time-situated reasoner keep track of an approaching deadline as he/she makes (and enacts) his/her plan, thereby treating all facets of planning (including plan-formation and its simultaneous or subsequent execution) as deadline-coupled. While an agent under severe time-pressure may spend a substantial amount of the available time in reasoning towards and about a plan of action, in a realistic setting the same agent must also measure up to two other crucial resource limitations as well, namely space and computation bounds. We address these concerns and offer some solutions by introducing 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 within these additional realistic constraints. We give examples from commonsense planning, including ones we have solved and implemented in Prolog.

    Keywords: Automated planning, deadlines, resource-limitations, active logic.

    Pages: 109 - 156

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    Click here to register with OUP.

    This page is maintained by OUP admin

    Last updated 25 Jan 97

    Part of the OUP Journals World Wide Web service.

    Copyright Oxford University Press, 1997