Planning with Continuous Time: Discussion
Date: Mon, 6 Aug 2001
From: Vladimir Lifschitz
To: TAG
A few weeks ago, I offered you the following challenge problem:
A car is on a road of length L. If the accelerator is activated, the
car will speed up with constant acceleration A until the accelerator is
released or the car reaches its maximum speed MS, whichever comes first.
If the brake is activated, the car will slow down with acceleration -A
until the brake is released or the car stops, whichever comes first.
Otherwise, the speed of the car remains constant.
Give a formal representation of this domain, and write a program that
uses your representation to generate a plan satisfying the following
conditions: at time 0, the car is at rest at one end of the road; at
time T, it should be at rest at the other end.
To test the program, take L=10, A=3, MS=4, T=4.
What's tricky about this question is that it requires the use of fractions.
The numerical values that I suggested for testing were selected in such a
way that a solution in integers is impossible. For instance, here is one
possible plan:
Do nothing for 1/6 of a second;
Accelerate for 4/3 of a second;
Do nothing for 7/6 of a second;
Break for 4/3 of a second.
Some of the solutions that I have received are available now at
http://www.cs.utexas.edu/tag/continuous_solutions .
Representations 1, 2 and 4 use the language of smodels. (The authors of
the last of these solutions have adapted it also to the language of dlv.)
They differ from each other in details, but their general idea is the same:
expressing every quantity involved (time, speed, distance) by fractions
with a fixed denominator. Performing an action--say, "accelerate"--over
p/q of a second, where q is the standard denominator, is viewed as the
execution of the accelerate action (of the standard duration 1/q) p times
in a row.
There is a trade-off between the choice of the denominator q and the number
of steps in the plan. For instance, to get a 4-step plan like the one shown
above, one has to represent the durations of actions using fractions whose
denominator is at least 6. With the denominator 3, a 5-step plan is possible:
Accelerate for 2/3 of a second;
Do nothing for 1/3 of a second;
Accelerate for 2/3 of a second;
Do nothing for 1 second;
Brake for 4/3 of a second.
In fact, the authors of solutions 1 and 4 found ways to use the "minimize"
directive of smodels to generate economical plans.
Solution 3 uses a different approach to representing this domain. It
distinguishes between time as a step on the one hand, and time as duration
on the other. Accelerating for p/q of a second is viewed here as a single
action; p and q are the action's "attributes." Under this approach, more
economical plans are simply the shorter ones, as in traditional planning,
so that no special tricks are required to generate such plans.
Incidentally, the shortest possible plan for the numerical example that
I suggested for testing consists of only 3 steps. But the durations of
actions involved in such a plan are expressed by irrational numbers, so
that the solutions proposed so far would not be able to find such a plan.
Date: Mon, 6 Aug 2001
From: Nam Tran
To: Vladimir Lifschitz
If a common denominator q is fixed at the beginning, then
planning in the continuous time domain (0..T) is the same as
planning in the integer time domain (0..qT), isn't it?
The ccalc solution is really clever. But it still is essentially
planning with discrete time. Here instead of ONE fixed denominator, a
SET of denominators ( integers from 1 to 6) is fixed. I guess that a
real continuous solution isn't possible.
Date: Mon, 6 Aug 2001
From: Vladimir Lifschitz
To: Nam Tran
But doesn't your observation apply to all uses of real numbers in
computer programming? When we operate with reals using floating point
approximations, we replace the continuum with its finite, discrete
subset -- the set of numbers representable in the floating point
notation.
Date: Mon, 6 Aug 2001
From: Nam Tran
To: Vladimir Lifschitz
But when I'm writing a computer program using real numbers I reason with
real numbers. The result I get is approximate because of the
implementation is limited, not because of my program.
It's the difference between ways of reasoning we're talking about.
There're 2 ways of looking at planning with continous time:
(1) reasoning with actions "along continuous line of time".
(2) reasoning with actions "along the line of executed actions". Actions
have real durations which real numbers. This is the ccalc approach, if
I understand it correctly.
My guess is that (1) is impossible ( or put it more correctly,
ill-defined ). In fact, when I heard of "planing w/ continuous time" I
thought first of (1).
(2) can be defined more exactly as "planning w/ actions with durations".