AITEC Contract Research Projects in FY1997 : Proposal

(16) COPLAS, a Conditional Planner with Sensing Actions

Principal Investigator : Dr. Jorge LOBO, Associate Professor,
University of Illinois at Chicago



[Contents]

  1. Background of the research
  2. Purpose of the research
  3. Contents of the research
  4. Project Organization/Research Method
  5. Resulting Software

[Background of the research]

Since its introduction, the action description language "A" of Gelfond and Lifschitz has served as a platform to study several aspects that arise in the formalization of action theories. "A" was designed as a minimal core of a high level language to represent and reason about actions and their effects. Domain descriptions written in this language have direct translations into extended logic programs. Extensions of "A" have been developed to study and reason about the concurrent execution of actions, the non-deterministic effects of some actions and to study many instances of the qualification and ramification problems.

Baral at University of Texas at El Paso, together with his students has implemented a liner planner based on "A" that compares very well to standard planners such as UCPOP, one of the most commonly used (partial order) planners.

In a paper to be presented in AAAI97 we had proposed a new action description language called "Ak". "Ak" is a minimal extension of "A" to handle sensing actions. A sensing action is an action that does not have any effect in the world. The effect is only in the perception of the reasoning agent about the world. The execution of a sensing action will increase the agent knowledge about the current state of the world. Take for example a deactivated agent placed inside a room. The agent has duties to carry out and will be activated by a timer. Let us assume the agent is always placed facing the door. The agent, once activated, may become damaged if it attempts to leave the room since the door may be closed. Before the agent tries to leave the room it needs to perform some act of sensing in order to determine whether the door is opened or not. The agent has incomplete knowledge with respect to the door. A sensing action such as looking at the door would provide information to the agent concerning the status of the door.


[Purpose of the research]

The main goal of the proposal is to develop a domain independent, logic programming-based planner for domain descriptions written in a subset of "Ak". In addition to sensing actions, the planner will have actions with non-deterministic effects. Non-deterministic actions and sensing actions have opposite effects on an agent's knowledge. An action can cause the lost of knowledge if its effect is non-deterministic.

The planner will be able to generate complex plans that will include conditional statements. It will be also able to verify the correctness of a limited class of plans with while-do loops.


[Contents of the research]

In this section we will briefly described "Ak" and show how conditional plans based on this descriptions are defined. We then briefly describe how we can implement a planner.

(5.1) "Ak"

Domains in "Ak" are finite sets of expressions of the following form:

a causes f if p1,...,pn

initially f

a causes to know f if p1,...,pn

In the expressions, "a" is an action, and f,p1,...,pn represent statements about the world and are called fluent literals. The first expression intuitively says that f becomes true when the action a is executed if p1,...,pn are true when a is executed. The second expression imposes conditions on the initial state of the world. It says that f is true in the initial state. The last expression says that the agent will know the truth value of the fluent f if it executes the action a in a state where p1,...,pn are true. Take, for example, a robot instructed to replace the bulb of a halogen lamp. If the lamp is on when the bulb is screwed in, the robots circuits will get burned out from the heat of the halogen bulb. If the robot's circuits get burned out, it will not be able to complete the task. The robot will have to find a sequence of actions that will allow it to complete the task. We assume that the robot is already at the lamp. This is represented by the following domain description,

D_1 = {

r_1 : initially NOT burnOut
r_2 : initially NOT lightFixed
r_3 : replaceBulb causes burnOut if switchOn
r_4 : replaceBulb causes lightFixed if NOT switchOn
r_5 : turnSwitch causes switchOn if NOT switchOn
r_6 : turnSwitch causes NOT switchOn if switchOn
}

In the initial state the robot does not know the state of the switch. Hence, there does not exist a way to determine beforehand what will be the result of the action replaceBulb. When the robot goes to carry out the action replaceBulb, it could end up in a resulting state in which either lightFixed is true or in a state where it will be burned out and unable to complete the task. Without knowing whether the switch is on or off, the robot will not be able to find a plan to accomplish its task. The robot must first check to see if the switch is on or off. After knowing which state the switch is in it will take the appropriate actions to complete the task. The robot will need a knowledge law as the following,

r_7 : checkSwitch causes to know switchOn if NOT burnOut

Sensing gives the robot that extra knowledge it would need to accomplish the task without burning out and provides a branching point in its hypothetical reasoning. If the switch is on, it will turn the switch and replace the bulb. If the switch is off, it will directly replace the bulb. Thus, the robot will need a conditional plan. Plans with conditionals can be recursively defined as follows:

In our AAAI97 paper we define an entailment relation that allows us to prove properties of plans. For example, we can show that D1 entails (denoted by |=) the following statement:

D1 |= lightFixed after checkSwitch, if NOT switchOn
             then replaceBulb
             else [turnSwitch,replaceBulb].

I.e., in D1, the light will be fixed after executing the plan in the right hand side of the expression.

Essentially, our goal is to implement the entailment relation |=. We have develop an equivalent definition of the entailment relation based on epistemic logic programs of Gelfond. The translation covers a richer language. The full "Ak" includes non-deterministic actions and plans with while-do loops. For efficiency reasons, we will trim out some of the aspect of the language (for example we will eliminate the condition part in propositions of the form "a causes to know f if p1,...,pn") to be able to obtain a translation into extended logic programs that is more amenable to implementations, and while-do loops will be used in a very limited context. Even with these restrictions, or planner will be more expressive than UCPOP or Baral's implementation.

A full description of the language and its semantics can be found: "http://www.eecs.uic.edu/~jorge/postscripts/97aaai.ps.gz"

The planner will consist of a search module that traverses the space of conditional plans and a checker module for successful nodes. A node in the search space is successful node if it contains a plan P, such that for the given goal G,

D |= G after P

Indications on how domain dependent heuristics can be added to the search module will be included in the final report.


[Project Organization/Research Method]

(1) Project Organization

Principal Investigator  Jorge Lobo  Asso. Prof.


(2) Research Method

Besides the intrinsic interest of having a logic programming planner with sensing actions, we are interested in developing the software in a bottom-up logic programming evaluator. We have a preliminary bottom-up implementation of Baral's planner. We have tested the planner with a series of examples that were designed by Baral's group to compare Baral's planner with UCPOP through these examples. Baral's work shows that his planners compares very well with UCPOP. We have found that our implementation out-performers Baral's in all the examples, sometimes with 10 fold speedups.

Thus, we believe that a bottom-up implementation will result in a very efficient planner.


[Resulting Software]

(1) The name of the software

COPLAS: a COnditional PLAner with Sensing actions.

(2) Functions and features of the software

The main functionality of the system will be planning. Given a domain description (such as the one in the example above) and a goal, the system must generate a plan to achieve the goal using conditional plans. Domains will be able to describe:

  • Regular actions, a class of non-deterministic actions and sensing actions
  • Universal quantifiers, executavility constraints and ramification constraints.
Many of these features are not part of the original "Ak" definition but can be borrowed from the "L" language of Baral.

The system will provide facilities to encode heuristics to accelerate the planning process with domain dependent information.

We will also provide facilities to prove properties of plans that contain while loops. However, it is not part of our proposal to investigate generation of such plans, since basic research has to be conducted first to find out realistic methods of ensuring termination.

(3) Structure of the software

The system will be a stand-alone planner. The user will be able to either interactively input his/her domain description or provide a file as an input. The system will work as an interpreter where the user provide goals and the system will return a plan (if there exists).

The user will also have direct access to the entailment relation to ask properties about conditional plans.

(4) Related IFS programs (if any)

N/A

(5) Required program language/OS/software packages

The software will be developed on a Sun workstation running the Solaris Operating system using the CORAL deductive database/logic programming system developed at the University of Wisconsin-Madison. CORAL is provided free of charge.

(6) Expected size of the software

Around 5,000 lines of CORAL code.

(7) Expected way of use of the software

There are two fundamental ways this system can be used:

(a) As a planner:

User can write domain descriptions in the language, pose goals to generate plans. As a such, the system can be used as a sub-module for a robot or a software intelligent agent.

(b) As a platform for "A" based action description languages:

Recently, there has been a tremendous amount of language extensions "A" to include, concurrency, narratives, ramification constraints, temporal queries, defeasible actions, etc. Our hopes is that our system will encourage researchers in the field to test their technical ideas by modifying our planner to include such extensions.

(8) Documents which will be added to the software

A report will be written specifying how the system was developed. It will also include some benchmarking of the planner, sources and user manuals. The description of the coding will include sufficient details to let users of the system understand where the software could be modified in order to include new features of actions languages to the planner.


www-admin@icot.or.jp