2011-12-19

Happening sequence for plans with both simple and durative actions in PDDL2.1

by Forrest Sheng Bao http://fsbao.net

I have been struggling with a definition in an important paper about temporal planning in past few weeks. And today i finally understand it with the help of one of the authors. In his words, this definition is sorta counter-intuitive. So I am now writing this blog and hope it will help others struggling with this as well.

Some background: The paper defines a major revision of PDDL, the de facto standard in planning, a sub-field of AI. It's called ``PDDL2. 1: An extension to PDDL for expressing temporal planning domains'' by Maria Fox and Derek Long. The paper is published in Journal of AI Research, one of the few top AI journals, in 2003.

Now let's begin. In Definition 16, the author defines the happening sequence of a plan, which implicitly includes both simple and durative actions as follows.

If P is a plan, then the happening sequence for P is \( \{t_i\}_{t=0...k}, \) the ordered sequence of the time points formed from the set of times

$$\{t| (t,a)\in P~or~ (t, a[t'])\in P~or~(t-t', a[t'])\in P\}$$

I don't understand why the 3rd disjunction (maybe in British English it's called ``disjunct.'') in the formula has $$t-t'$$ instead of $$t+t'$$ as the time point.

Dr. Derek Long, the 2nd and last author of this paper, gave me two email replies and finally made me understood.

Let's add something into the formula to see whether it helps.

$$\{t| (t,a)\in P~or~ (t, a[t'])\in P~or~(t-t', a[t'])\in P, t\in \mathbb{R}\}$$

So, for the 3rd disjunction, \( t \) is a real number, such that \( t-t' \) is the start of a durative action (by Definition 17) \( a \) whose duration is \( t' \). Since \( t-t' \) is the start, and \( t' \) is the duration of the action \( a \), \( t \) is the end of the action \( a \). In this way, the finishing time points of durative actions are included in the set of \( t \) 's.

Does it still sound ``counter-intuitive?'' If so, please write to me.

1 comment:

建筑者 said...

Wow, you're now using MathJax for equation rendering! I am a senior student in China who is now pursuing a graduate education in US, and I have been reading your blog for a while. I think it's pretty fun!