On extending SAPA to handle temporal goal reduction

[Subbarao Kambhampati <rao@asu.edu>]

Folks:

 I asked Minh Do to comment on what would be needed to support
goals with a temporal extent by reducing them into smaller interval
goals. (E.g. if the garage is large, light two candles one after other
and cross the garage thatway). Here are his "informal" comments. FYI.

Rao

=================
To support the goal of your type, I guess the extensions we need are:

1. Temporal goal representation & Goal checking condition:
We need some way to represent goals of the type: g=("have light", 5 
hrs). From a semantic point of view, I don't think it's necessarily 
different from the goal of maintainance such as the subgoal of the 
"overall" action's (pre)condition. For example, assume that we have a 
pick-up-in-the-basement action with duration 5 hrs that require that the 
(pre)condition is that it's lighted the whole time, then when we apply 
that action, the "protected" condition of having a light for 5 hours 
looks similar to the goal g in our case.

Hmm..., I think that there may be some differences between them. In the 
"overall" condition, any search branch generated from that node should 
not violate the protected "overall" condition. However, we can violate 
the goal g=("have light", 5hrs) and still be a valid search node (but we 
won't achieve that particular goal, at the moment).

This lead me to the thinking that the goal checking condition for g in 
state S is quite simpler, if g \in current goal set G, we first check 
that if "have light" is true, then what was the last time that "have 
light" is made true (this information is kept in Sapa's search node), if 
the time different between those two time points are \geq 5hrs then g is 
satisfied in the current state and we should remove g from G for any 
future search node from S

2. Action representation:
This causes me a little headache. Intuitively, it should be totally ok 
to light up candles at any time. However, if the semantic of the 
"light-on-candle" action indidates that there is a "light-on" effect at 
the begining, and "~light-on" effect at the end, then it prevents us 
from light-on-candle at the exact end time point of the other 
"light-on-candle", which doesn't make sense. The original semantic of 
Sapa where we prevent contradicting events to be in the same queue 
(which I think that I took off later for exo-events) won't even allow 
two "light-on" actions to execute in concurrent. Moreover, it also seems 
that at the end of the "light-on-candle", light-on becomes false even if 
there is another candle burning. Therefore, we should somehow be able to 
say that it's light-on if one of the (many) "light-on-candle" action is 
executing and thus if there is an executing "light-on" action, then the 
"~light-on" effect of another action doesn't cause anything.

I don't know how to solve the "concurrent light-on-candle" dilema in 
PDDL2.1 right now. May be some extensions of \forall and \exists are 
enough, but I don't really know.

Assumming that we can only light up candle one by one, then the 
validation condition in VAL would still require that the two time points 
representing the end of the first light-on action  and the start of the 
second light-on action to be separated by \epsilon, which can be 
arbitrary small. Therefore, I don't know if it can totally satisfy our goal.

In conclusion, I can't think of the clean way of easily extending Sapa 
to handle your particular "candle" example. If we relax the goal by 
saying "total light-on time by burning candle of at least 5 hrs (not 
necessarily un-interrupted), then it would be quite easy. For the goal 
checking condition, we need to monitor the total time that "light-on" 
has been true for each search node, which Sapa can be extended quite 
easily. Then whenever that total duration reach 5hrs, then we remove the 
goal from consideration. For the heuristic, it would be easy too because 
we only extend the graph until (light-on, 5hrs) is reached, which will 
require 5 consecutive candle actions in the graph building phase. When 
extrracting the relaxed plan, we use the same approach of keeping track 
how long "light-on" has been true and will come up with 5 candle actions.


If you have different opinions, please let me know.


Minh
======================================