AITEC Contract Research Projects in FY1997 : Proposal |
Principal Investigator : | Dr. Jorge LOBO, Associate Professor, |
University of Illinois at Chicago |
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.
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.
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:
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 = {
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,
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,
Indications on how domain dependent heuristics can be added to the search module will be included in the final report.
Thus, we believe that a bottom-up implementation will result in a very efficient planner.
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.
The user will also have direct access to the entailment relation to ask properties about conditional plans.
www-admin@icot.or.jp