Improving Search by Utilizing State Information in OPTIC Planners Compilation to LP

Automated planners are computer tools that allow autonomous agents to make strategies and decisions by determining a set of actions for the agent that to take, which will carry a system from a given initial state to the desired goal state. Many planners are domain-independent, allowing their deployment in a variety of domains. Such is the broad family of OPTIC planners. These planners perform Forward Search and call a Linear Programming (LP) solver multiple times at every state to check for consistency and to set bounds on the numeric variables. These checks can be computationally costly, especially in real-life applications. This paper suggests a method for identifying information about the specific state being evaluated, allowing the formulation of the equations to facilitate better solver selection and faster LP solving. The usefulness of the method is demonstrated in six domains and is shown to enhance performance significantly.


Introduction
Automated Planning (often called AI Planning) is concerned with formulating a sequence of actions that transforms a system from a given initial state into a desired goal state. One strength of AI Planning is domain-independence: a single general planner can plan in a wide range of different application domains. Examples of domains in which Planning was used include space (Chien et al. 2000), battery usage (Fox, Long, and Magazzeni 2011), and software penetration testing (Obes, Sarraute, and Richarte 2013). To facilitate application in realistic problems, planners need to reason with expressive models of the world. Such models can be temporal: finding a plan with timestamped actions, taking into account action durations and concurrency, and numeric: considering variables that change discretely, or continuously, over time (Fox and Long 2003).
To solve expressive problems that contain temporal constraints, the planner requires a scheduler -A technique for assigning values to the action's timestamps that would result in a valid plan. For example, the temporal planners SAPA (Do and Kambhampati 2001) and Temporal Fast Downward (Bell et al. 2010) utilize the decision epoch mechanism, Crikey 3 (Bemporad, Ferrari-trecate, and Morari 2000) uses Simple Temporal Network (STN). To solve hybrid problems that contain temporal as well as discrete and continuous change, the planner would require more complex approaches. For instance, SMTPlan formulating the problem into SAT (Cashmore et al. 2016), ENHSP using interval relaxation (Scala et al. 2016), DiNo discretizing time (Piotrowski et al. 2016), and qtScoty using convex optimization (Fernández-González, Karpas, and Williams 2017).
This work focuses on a family of planners that uses Linear Programming (LP) solvers to schedule the plan. This family includes COLIN , POPF (Coles et al. 2010), and OPTIC (Benton, Coles, and Coles 2012). Planners from this family were used in a variety of real-world applications including robotics, (Cashmore et al. 2015), Autonomous Underwater Vehicle (AUV) control (Cashmore et al. 2014), Micro Aerial Vehicles (MAV) control (Bernardini, Fox, and Long 2014) and space applications Denenberg and Coles 2018). These planners perform forward state-space search starting from the initial state. At each search state, an LP solver is used once to determine whether a consistent schedule for the plan exists. If no consistent schedule exists, the search branch can be pruned. If the state is consistent, the LP is then used several more times to bound the numeric variables and thus tightening the space of applicable actions in this state, narrowing the search space ahead. Recent work (Denenberg, Coles, and Long 2019) has shown that solving LPs at every state multiple times may cause the search process to become slow and ineffective.
The contribution of this work is twofold: 1. We propose a better translation from the search state to LP. Our new compilation allows the better selection of optimization tools required for the consistency check of the problem, possibly eliminating the necessity of an LP solver.
2. We propose methods for using information from a given state to compute the current variable bounds in the search, thus calling the solver fewer times and improve the performance of any planner from the OPTIC family.
The rest of the article is ordered as follows: Section 2 describes the problem and the current way OPTIC planners Leg1 Leg2 Obs1 Obs2 Obs3 Obs4 Obs1 start dist.
Obs4 start dist. Figure 1: The flying observer solve it. Section 3 presents the suggested methodology. Section 4 presents the performance of the suggested improvements in a variety of different domains.

Problem Definition
A temporal planning problem with discrete and linear continuous numeric effects is a tuple: where P is a set of propositions and V a set of numeric variables. A state S is defined as a set of value assignments to the variables in P and V. I is such a set representing the initial state of the system. G is the goal: a conjunction of propositions in P , and linear numeric conditions over the variables in V , of the form ..w i and c ∈ R are constants). An action changes the values and carries the system from one state to another. An action is defined as a tuple as well: where d is the duration of the action constrained by a conjunction of numeric conditions. pre ⊢ and pre ⊣ are conjunctions of preconditions (facts and numeric conditions) that must be true at the start and end of the action, pre ↔ are invariant conditions (preconditions that must hold throughout the action's duration), eff ⊢ and eff ⊣ are instantaneous effects that occur at the start and end of the action. Such effects may add or delete propositions p ∈ P (eff + , eff − ) or update a numeric variable v i ∈ V according to a linear instantaneous change: where u, v i ∈ V are numeric variables, and c, w i ∈ R are weights. eff ↔ is a conjunction of continuous effects that act upon numeric variables throughout the action's duration. In this work, we assume all change is linear and is of the form: where c ∈ R is a constant. The planner is required to find a set of actions in A and their schedule, that would carry the system from the initial state to the goal state. (Denenberg, Coles, and Long 2019) first introduced this example; it is an anonymized model of a real-life problem. In this domain, named flying observer, the planner is required time distance Precondition Can start observing Figure 2: Distance Requirement to plan an Unmanned Aerial Vehicle (UAV) observation mission. The UAV is required to fly legs over a defined stretch of land containing objects to be observed. Each leg is of different length. Each observation has a different duration and requires a different type of equipment. A target-start distance defines the area within the leg in which the observation must take place. The observation can only occur when the UAV has flown more than the target-start distance of that leg (flown l ≥ target-start o ). A continuous numeric effect of the fly l action updates the distance flown so far in a leg:

Running Example
where Vel l is the flight velocity. Fig. 1 illustrates an instance of this domain: in this instance, two legs are defined (marked in solid blue lines). In each leg, two observations are required (marked in red, pattern-filled lines). All observations have a target-start distance defined, but for clarity, only the starting distance of the first and last observations are shown.
In order to perform an observation, a defined piece of equipment needs to be calibrated and configured for a specific observation. Once the observation is done, the equipment needs to be released to become available for future observations. The domain comprises the following actions: take-off l (dur=5; pre ⊢ ={on-ground,first-leg l }; eff ⊢ ={¬on-ground, flown l =0}; eff ⊣ ={flying l }), set-course l1,l2 (dur=1; pre ⊢ ={done l1 , next l1,l2 }; eff ⊢ ={¬done l1 }; eff ⊣ ={flying l2 , flown l2 =0}), fly l (dur= distance l / speed l ; pre ⊢ ={flying l }; pre ↔ ={flown l ≤distance l }; eff ⊣ ={done l , ¬flying l } eff ↔ ={ dflown l / dt +=1}), configure o,e (dur=1; pre ⊢ ={available e , optionfor o,e }; eff ⊢ ={¬available e } eff ⊣ ={configuredfor o , pending o,e }), The target distance precondition and temporal constraints force the observe actions to fit within the fly action. The meaning of the precondition is illustrated in Fig. 2: The blue line is a depiction of the distance change as the UAV flies over the leg. The dashed red line is the precondition signifying the distance required for the start of the observation. When the distance reaches the value required in the precondition, the observation can start. Notice that this problem is, in fact, temporal, the numeric constraint can be easily converted to a temporal one depending on the manifestation in the temporal state can be seen in Fig. 3.

OPTIC and Forward Search
The OPTIC family of planners is based on the methodology of converting a state to an LP described in COLIN paper ). Here we survey that methodology.
To find a path from the initial state to the goal, OPTIC performs Forward Search. Starting from the initial state, OP-TIC branches over applicable actions, exploring partiallyordered but un-time-stamped sequences of instantaneous actions. Durative actions are converted to a pair of instantaneous snap-action. Snap-actions mark the start (A ⊢ ) and end (A ⊣ ) of a durative action A. A ⊢ has preconditions pre ⊢ A and effects eff ⊢ A; A ⊣ is analogous. We define the set A inst to contain all instantaneous actions in A, including snapactions.
A state S in the search can be thought of as a set containing: propositions (S.p ⊆ P ) that are true in S, and upper (S.max (v)) and lower (S.min(v)) bounds on the value each variable in V can hold in S. In the initial state, all variables have max (v) = min(v) = v I the value of v specified in the initial state; max (v) and min(v) will only differ from each other in following states if a durative action with a continuous effect has acted on the variable.
An action is deemed applicable if all its propositional invariants are satisfied by S.p and if all numerical invariants can be satisfied by any value between S.max (v) and S.min(v). The planner compiles a list of all open applicable (named openlist). Search proceeds by popping the first state from the openlist: in our work, we use WA* (W=5), so sort the openlist by h(S) + 5.g(s), using the temporal-numeric RPG heuristic of COLIN .
All successors S ′ of S are generated by adding or deleting all propositions in eff + a and eff − a respectively, and applying all discrete numeric effects to both max (v) and min(v) for all v ∈ V affected by eff num a . This guarantees the S ′ to be propositionally consistent.
OPTIC then transforms all the temporal constraints to the following form: where Lb, U b ∈ R are the upper and lower bounds of a time interval. OPTIC also adds the necessary ordering constraints to the plan. The action that has just been applied is ordered after the following: last actions to add each of its preconditions, actions whose preconditions it deletes, and actions with numeric effects on variables it updates or refers to in preconditions/effects. All ordering constraints are of the form t j − t i ≥ ǫ, where t j ,t i are the times at which the new and existing action must occur, respectively, and ǫ is a small positive constant. The temporal and ordering constraints, formulated as Eq. (5), constitute a STN and the planner uses a Simple Temporal Problem (STP) solver to check for temporal consistency. If the STP can solve all equations (i.e., assign values to all time-steps such that the equations are valid), then the STP was able to find a schedule, and the state is temporally consistent. If S ′ is propositionally and temporally consistent, the planner will compile the problem into an LP and then check for numerical consistency. Each step of the plan i is given an LP variable t i . Each variable v ∈ V is given three LP variables for each step i: v i , v ′ i , and δv i . v i denotes the value of v just before applying the action in step i, and v ′ i is the value right after the action's application. The planner applies Eq. (3) to the affected variable thus: where v, u ∈ V are the numerical variables, u n i is the value of the nth numerical variable at step i. w n s are weights.
δv i is the value of the sum of all changes currently acting on v. Recall; in this work, each continuous effect is defined by a constant. When a new action is applied at step prev, the contribution of its effect is added to δv prev ; when an effect ends at step i, the value is removed from δv i .
The value of v i denoting the value just before the application of the action at step i can be computed thus: where i is the current step index and prev is the index of the last step in which the value of v was computed. Note; if the calculation of the value of v is required for an invariant in step j, the next time v will be computed the time interval will be t i − t j , regardless whether δv is changed or if the action is acting on v.
If the STN or LP finds that the state S ′ is inconsistent (i.e., there is no solution, no schedule that would enable achieving the state), it is pruned, and the search will not advance down that branch. If the state is consistent, then the LP solver is called two more times for each variable v to optimize it and compute the new max (v) and min(v) using the standard temporal/numeric relaxed planning graph heuristic of Colin . It is then inserted into the openlist, providing h(S ′ ) = ∞, i.e., the heuristic does not indicate S ′ is a dead-end.
Note that when no numerical change is present, it is sufficient to use STN to prove consistency. When continuous changes or numeric constraints are present, the LP solver is required for the proof of consistency.
In addition to the consistency check, the LP is also used to compute the bounds max (v) and min(v) of S ′ . If all continuous actions on v have ended, then the last defined value v i can be maximized and minimized to compute the bounds.
If v had a continuous effect start but has not yet ended, another time variable is added to the LP denoted t now , representing the latest timestamp. For each variable with an active effect, a variable v now is added. t now is ordered after all Step Action variables constraints comment 0 TakeOff Step2 after Step1  (8). The LP solver then minimizes and maximizes v now to find the possible bounds. (Denenberg, Coles, and Long 2019) showed that though it was previously thought that calling the LP solver is beneficial both for state consistency and for the variable bound update, in large real-life domains, the calls to the LP solver may slow the search down. The premise was that the LP problems solved are small, and therefore the call to the offthe-shelf solver would not be computationally expensive. However, it was shown that in some real-life applications, this was not true: when the state contained many actions and multiple variables, the LP grew large and the solving of which became slow. Table 1 demonstrates the process of converting a state into an LP. The table shows the LP equations for the partial-plan: take-off, fly ⊢ l0 , observe ⊢ o1,l0 , observe ⊣ o1,l0 (for conciseness we assume that take-off is instantaneous and no configure actions are required).
The first action receives a single time variable t 0 . The second action F ly ⊢ l0 , receives a time variable t 1 , which is ordered after t 0 , and the value of f lown is computed. The value before the fly action is the initial assignment, which is 0. Since there is no instantaneous effect on the action's start, the value just after the application of the action is the same. The invariants on the value are enforced just after the beginning of the fly action. The same process is repeated for the next action Observe ⊢ o0 : assigning a time variable for the action, calculating flown before and after the application of the action, and enforcing invariants. Note the ordering constraints formulated as temporal constraints in all actions. Also, the f lown variable is computed at each step, and its value depends on the previous step.
The next section will describe a method for changing Eq. (8) in a way that would allow calling the LP solver fewer times, and compile certain problems containing numerical constraints and change as STP.

Informed Selection of Solver for Consistency and Update
The OPTIC methodology described in the previous chapter was developed to accommodate the general case in which hybrid planning is to be done, covering all possible state types. The planner uses the general representation both in consistency check and in the variable update. It was shown in (Denenberg, Coles, and Long 2019) that the general approach could, at times, lead to slow solving. In this section, we propose two new methods for identifying two specific cases that frequently arise in the state in real-life problems. In such cases, the use of an LP solver can be made redundant, facilitating faster solving. In other cases, information from the current state may be injected into the problem definition to allow for faster solving.
The first method examines the latest added action that carried the system from state S to state S ′ . The second involves a conversion of specific numeric constraints and effects into STN form. Finally, we describe how both these processes can facilitate a more effective update of variable bounds.

Observing the Latest Action
As stated previously, OPTIC solvers attempt to prove inconsistency with an STP first. Then if continuous numeric effects and numeric constraints are present in the current state, the planner compiles the problem as an LP. OPTIC planners treat each state in the most general way: in the general case, every action may render the new state inconsistent. However, using knowledge about previous states, some instances in which the LP solver can be avoided may be found.
Consider the state TakeOff ⊢ , TakeOff ⊣ , Fly l1 ⊢ , configure o1,e2 ⊢ : The partial plan contains continuous numeric effects on the variable f lown l0 . Therefore, to prove this partial plan consistent, OPTIC requires an LP solver. However, since the planner is performing forward search, to reach this state, the planner must have been in a previous state, which it found consistent: TakeOff ⊢ , TakeOff ⊣ , Fly l1 ⊢ . The configure action that is added does not require the value of f lown l0 , and its effect is propositional.
Assume the state S is propositionally, temporally, and numerically consistent. The new state S ′ , which is reached from S by addition of action A ∈ A inst cannot be rendered numerically inconsistent if A does not contain any numerical effects or constraints. Furthermore, since OPTIC only examines states S ′ that are generated to be propositionally consistent, the state only has to be tested only for temporal consistency.
Thus, if an added action A contains only propositional or temporal constraints and effects, the state S ′ can be deemed consistent by using the STP, and an LP is not required.
Note that if this test has determined that S ′ is consistent, there is no need for a numerical variable bound update, as those do not change.

Reformulation of LP
During the search, OPTIC compiles the state into an LP, as depicted in the previous section. This transformation is done in a step-wise manner, meaning each step is transformed into  No consideration is taken as to what effect a step has on a variable; as long as the value of the variable is required, its value will be computed, and the next step will use said computed value. The notation t prev denotes the previous step at which the value of variable v was calculated, and the next step i > prev that computes the value of v will use the value stored in v prev .
Here we suggest making a distinction between two types of steps that affect the value of v: A step containing a start or end of a continuous numeric effect and a step that does not. The later is a step containing numerical constraints on v but does not change the value of δv. To distinguish between the two, we propose two notations ef f for steps that start or end an effect and const for steps containing only constraints.
Using the new notation t p ef f would be the last time in which v had an effect start or end, v p ef f would be the value of v calculated at that time point. Then Eq. (8) is written thus: The conversion of the equations is demonstrated in the previous example: this is presented in Table 2. Notice the difference between Table 1: The effect acting on the variable f lown l0 started in step 1, and therefore the computation of f lown l0 2 f lown l0 3 is always done with respect to step 1.
If no continuous numeric actions have been acting on v before the last action at t p ef f , then the value of v p ef f is a constant. This is seen in our example. The value of f lown l 0 ′ 1 is the same as the initial assignment. This conversion extremely useful when all constraints are of the form: where v ∈ V and C ∈ R. This constraint is written as a less than-equal-to constraint. Without loss of generality, this includes all constraints that have a single variable on one side and a constant on the other. If v p ef f is constant, then using Eq. (9) when enforcing Eq. (10) at step i, we can write Notice that at step i, all the variables on the right-hand side of Eq. (11) are known and are constant. Therefore, Eq. (11) can be formulated for each step i as a constraint of the form of Eq. (10) as long as v p ef f is constant. Notice that the numerical constraint in Eq. (10) is converted to a temporal constraint. If all constraints in the state can be converted thus, then the problem is, in fact, an STN, and the LP solver is not required. The example given above can be converted in such a way. The constraint f lown l0 2 > T arget dist o1 can be converted to t 2 − t 1 > (T arget dist o1−f lown l01) / 1 . All numeric constraints in this partial plan can be converted in the same way. This means that even though continuous numerical effects and numerical constraints are present, this problem is temporal, and can be solved with an STP.
If all numerical constraints were converted to temporal, the planner could determine consistency using the STN. However, updating the bounds is still required. Observing Eq. (8), we note that since v p ef f is constant, the maximum and minimum of v i are dependent on the interval The minimal size of the interval is zero. The maximum may be drawn from the state: if another constraint exists such that limits t i or if t p ef f is a start action beginning an effect, and is the only continuous numeric effect present, the maximal interval is the duration of the action. If no such value can be derived from the problem, then the interval is set to infinity. If δv i > 0 then the minimum value for v i is when T i = 0 and is min (v i ) = v p ef f ; and the maximum is max (v i ) = v p ef f + δv ef f T i . The case in which δv i < 0 is analogous. This update method does not require an external solver and, therefore, very fast. (Denenberg, Coles, and Long 2019) have shown that the variable update is often the task that is most computationally expensive as it requires several calls to the LP solver, depending on the number of numerical variables in the partial plan. The previous section has detailed several cases in which the variable update can be avoided or done without the use of an LP. Here we attempt to facilitate faster LP solving in the update phase in case it is still required. The LP solver may use one of several optimization methods; however, the selection of the method, as well as the method speed, depend on whether the feasible space is bounded and in which direction. We would like to supply the solver with information about variable boundlessness. We cannot use the bounds from the previous state S as those might have changed by action A.

Efficient Variable Update
Therefore, we again examine the snap action A added in the last step that carried the system from previous state S to the current state S ′ . Recalling state S contains bounds on v (S.max (v) andS.min(v)). We wish to determine whether the action A is capable of expanding the limits of v, causing the interval [min(v), max (v)] to grow if A causes the bounds to contract, or if the interval retains its size but shifts.
If an instantaneous numeric effect exists, then the bounds on the latest defined v i (the step at which all continuous ef-

Evaluation
In this section, we examine the performance of the proposed changes in six different domains, which stem from four physical world examples. The domains brought here were chosen to demonstrate both the strengths and the weaknesses of the contribution: The first four illustrate the family of cases in which the contribution is meaningful, shedding light not only to the benefits of our suggestion but also to ways in which to better model a problem for any OP-TIC family planner. The other two domains are brought to demonstrate cases in which the contribution is not useful, in an attempt to assess the price of using it. As this work's contribution is in improving the OPTIC family of planners, we compare our suggestions with the performance of the latest implementation of OPTIC, and apply our improvements to the same code base, and name it OPTIC with Injected Information (OPTIC-II).
The results and results of other additional tests on various IPC domains are publicly available at extra data 1 .
All tests were performed on an Intel i7-8550U CPU@1.80GHz×8 with 8GB RAM. The PDDL files of the domains, the respective problems, and result data will be published on a public website. Runtime results are presented in Table 4. "X" in the table means the runtime was over 1000s. Since the domains and processes are deterministic no statistical analysis is required, as results may only vary due to CPU noise.

Domains
Flying Observer We demonstrate OPTIC-II on a set of previously published domains. The first is the flying ob-server that (Denenberg, Coles, and Long 2019) has presented as a domain stemming from the industry. Two distinct models of this physical domain were tested: The first is identical to the running problem. The second variant of this domain has a requirement that the observer is flying before configuring or releasing pieces of equipment.
The problems in the first variant all require a single observation to be made in each leg. The instances are described in Table 3.
In all instances of the second variant, six observations are defined for each leg, where the first and last leg both share an observation that cannot be performed in the first leg. The fact the observation cannot be used in the first leg may lead the planner down a branch, which would not be useful. The first instance contains two legs, the second three, and so on. (Denenberg, Coles, and Long 2019) showed that these problems are challenging for the planner.
Factory Floor Quality Assurance (QA) This domain describes QA sampling planning on a factory floor. A machine produces parts at a specific rate; at some point, several parts are taken for sampling. The number of produced parts is limited for storage reasons. This domain is similar to the previous domain (the flown distance is analogous to produced parts); only here, we limit the total number of parts that can be produced, adding a global numerical invariant condition. In this domain, too, we have two variants -one allowing the calibration of measuring machinery before the beginning of the manufacturing process, and one that does not. As in the previous domain, the second variant is used for instances that require multiple samples of the same part.
Single Rover IPC Domain and Linear Generator The Single Rover domain is a standard domain taken from the standard IPC 3, and ) used it to demonstrate the hybrid planning mechanism.
The Linear Generator is yet another standard domain that was widely used in previous papers. It describes a generator consuming fuel to generate energy. The generator may be refueled from auxiliary tanks. All actions affect the main-tank fuel quantity, and the fact that all actions contain numerical change and constraints it was expected OPTIC-II to show little to no improvement in solving problems from this domain.

Results
Implementing the changes suggested in this work requires additional tests before building an LP. These tests and checks come with a computational price. However, as can be seen in Table 4, that price is not high. In the Linear generator domain and the single rover, none of the changes are useful. In most states, the information from the applied action cannot reduce the computations, and the problem is not convertible to temporal. This is because in many states, for instance, there are often two continuous linear actions operating on the same variable. The changes not being useful mean that all checks will be false when running OPTIC-II, and the LP solver will be used just as in OPTIC. The results show that OPTIC-II indeed performs a bit slower when used in these domains.  In the four domains from the Flying Observer and QA, OPTIC-II performs far better than OPTIC. We present the results of all three suggested changes, the contribution of each change separately, and possible combinations to better understand the results.
Efficient Variable Update In Section 3.3, we suggest using information about the current action to update the variables' bounds efficiently. This improves the LP solving in the variable update stage of the search. Therefore, we expect this change to be more prominent when the planner handles large plans that result in larger LP problems, and when a large amount of variables needs to be updated.
In Table 4, the line named "Sec. 3.3" presents OPTIC performance when only this change is present in the four domains taken from (Denenberg, Coles, and Long 2019). It can be seen that this change contributes to the performance is more prominent in higher instances where the plan is, indeed, quite long and contains many variables.
Though this change's contribution is not visible in simple academic domains, it helps scale large problems such that arise in a real-life domain and, therefore, useful.
Observing the Latest Action In Section 3.1, we suggested using information about the current action to decide whether an STP can be used to prove temporal consistency even though a numeric change is present in the state. This change may lower the number of LPs that will be solved during the search and, therefore, speed up the search. The runtime results of OPTIC running only this improvement is dubbed "Sec. 3.1" in the table.
In the first four domains, we see a significant reduction of LPs solved in the search 2 , which results in a faster search. In the last two domains, the reduction is minimal, and so the 2 The number of states proved consistent with an LP out of the visited states is given in the extra data, and will be published online tests slightly slow the search process.
Reformulating the LP The last contribution we examine is the one described in Section 3.2. For implementation reasons, this change was only applicable to the previous change. This change was useful in both the flying observer domains. When applied to these domains, all problems were converted to temporal, and no LPs were solved. The result was a significant improvement in planning speed.
In the QA domains, only some of the states were converted from numerical to temporal, and therefore the change was less prominent. The planner was able to identify that the requirement for the total amount of produced parts was the variable that prevented the conversion. If the domain expert believes the total amount limit cannot be reached, he can remove that constraint from the domain and allow for much faster Planning. Thus, using this method, we can improve performance, and perform knowledge engineering, presenting the model expert with possible ways to improve the planning process.