ZENO

  ZENO is a least committment planner that handles actions occurring over
  extended intervals of time. The algorithm is both sound and complete.

  Zeno supports deadline goals, metric pre conditions, metric effects, and 
  continuous change. Simultaneous actions are allowed as long as their effects
  don't interfere.  This allows zeno to reason about the deadline goals, 
  peicewise-linear continuous change, and external events.


  The example problem used in the paper involves 3 people located at one of 
  4 cities and one plane that will move the people to thier desired destination.
  Other considerations are the travel speed of the plane which can be either
  fast or slow and the fuel consumption rate is different for each. Also, the 
  problem considers the time it takes to refeul the plan and the time it 
  takes passengers to board and leave the plane.

  Zeno uses a first order language in which actions are represented as schema.
  Each schema specifies the time over which an action occurs, the preconditions,
  and the effects.

  	example schema:

	  fast-fly(m,l)
	    at-time: [ ts, te ]
	    precondition:
	      for all time t, t in [ ts, te ] -> fuel(t, plane) > 0 and 
		  at(ts, plane,m) and 
		  dist(m,l) = v2 and 
		  mpg(plane) = v3

	    constraints:
	      v4 = -600/v3, te = ts + v2 / 600

 	    effect:
	      at(te,plane,l) and 
	      for all time t, t in [ ts, te ] -> not at(t,plane,m) and
	      for all human o for all time t
		  (t in [ ts, te ] and in (plane,o) ) -> not at(t,o,m) and
		  at(t,o,l)
		  and
	      for all time t, t in [ ts, te ] -> d/dt fuel(t,plane) = v4 
              
 

  A goal for zeno may ba any logical sentence made up of connectives (and / or)
  and literals. 

  ZENO plans are triples composed of a set of steps S, a set of causal links
  L, and a set of constraints C. (S, L, C)

  The algorithm:
    Zeno is a least committment, regression planner. The search space consists
    of pairs of partial plans and goal agendas. It starts at a node P with 
    P = (S,L,C) is the plan problem and G is the goal agenda. It then goes 
    through the following loop:

  Is C consistant? 		- no  : FAIL

    - yes : Does G = null?	- yes : Return P
		
		- no  : Remove a goal from G
			
			Is this goal a primitive?	- no  : Reduce, go to 
								start.

 			 	- yes : Is it metric?	- no  : Choose source
								ei for the goal
								and add a link
								to L, resolve
								threats and 
								go to start.

                                - yes : Post the goal, 
					go to start.

  Posting a goal means that, if the time of the goal tg is a point, then
	only 1 constraint of the goal is posted, ie: at tg. Otherwise, zeno
	will post the constraint for both endpoints of the interval. (using
	piecewise linearity)

  There are 3 non - deterministic dicisions in the algorithm. 
  
 	 First, decomposing a complex goal into simpler formula.
	 Second, choosing actions to satisfy simple goals.
	 Third, introducing constraints to prevent interference between actions
		and goals.


  In order to avoid infinite branching while reducing goals the implementation
  will only split intervals to a pre set depth.


  Zeno resolves threats using the standard promotion and demotion, which posts 
  constraints on time points.

  Zeno is a constraint satisfaction algorithm. The types of constraints are
  codesignations, linear equalities, linear inequalities, and nonlinear 
  equasions. Codesignations are handled the same way as in UCPOP, using 
  equivelence classes. Linear equasions are solved by Gaussian elimination,
  non linear equasions are delayed until they bocome linear by the solving of
  other inequalities.

  Performance:

    The initial results show that zino performs about equal with state based 
    in domains that do not use interval goals, continuous change and metric 
    relationships. (ie: it does as good as state based planners on state 
    based domains)

    Using the time interval features still leaves ZENO's performance in a 
    manageable range for experimental use and research. However, further 
    work needs to be done before ZENO can handle large scale practical problems.

    Time test included in the zeno paper are:

     problem    		CPU time (sec)
   -------------------------------------------------------

    Door latch			  0.04 +/-  0.0
    Airplane routing		151.56 +/- 27.56
    SIPE example 		  1.42 +/-  0.24