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".