# Heuristic Search for Planning with Different Forced Goal-Ordering Constraints

Authors: Jiangfeng Luo; Weiming Zhang; Jing Cui; Cheng Zhu; Jincai Huang; Zhong Liu
Journal: The Scientific World Journal
 (2013)

---

## Abstract

Planning with forced goal-ordering (FGO) constraints has been proposed many times over the years, but there are still major difficulties in realizing these FGOs in plan generation. In certain planning domains, all the FGOs exist in the initial state. No matter which approach is adopted to achieve a subgoal, all the subgoals should be achieved in a given sequence from the initial state. Otherwise, the planning may arrive at a deadlock.
For some other planning domains, there is no FGO in the initial state. However, FGO may occur during the planning process if certain subgoal is achieved by an inappropriate approach. This paper contributes to illustrate that it is the excludable constraints among the goal achievement operations (GAO) of different subgoals that introduce the FGOs into the planning problem, and planning with FGO is still a challenge for the heuristic search based planners. Then, a novel multistep forward search algorithm is proposed which can solve the planning problem with different FGOs efficiently.


---

## Body

## 1. Introduction

A large majority of real-world problems have interfering subgoals. How to effectively plan for the interfering subgoals, especially when there are forced goal-ordering (FGO) constraints, has been a long term focus. As the Goal Agenda Manager (GAM) [1] used in the FF planner [2] and the ordered landmarks [3, 4] introduced in the LAMA planner [5], quite a number of approaches have been proposed but the performance results have scarcely improved. This is because, if any of the FGO constraints is violated, forward search may arrive at a deadlock, from which there is no way to reach the goal state. However, the proposed approaches such as GAM and landmark cannot detect all the deadlocks exactly and the undiscovered deadlocks make a planning difficult. In this case, this paper proposes an approach that can automatically put right the planning process when it leads the search to a deadlock and significantly improve the planning efficiency.Many real-world problems as in military, industrial, aviation, and space domains involve FGO constraints. An example is a naval platform which has to counter many incoming missiles with different weapons [6]. Firing weapons at one missile may interfere with the interception of others. Thus it can cause the naval platform to suffer from high probability of leaking if the missiles are countered in an incorrect order. Another example is a scenario of a robot rescue [7]. Each robot has a special ability, such as survivor search/transport, cleaning barriers, or medical distribution. The rescue tasks should be finished coordinately in constrained orderings with respect to a given environment. Certain robots only care about their own subgoals and achieving them too early may result in the failure of an entire military operation. Additionally, FGO constraint can be observed in a NASA scenario as a digger robot is allowed to dig the ground on mars only after a photograph robot has taken a picture of the site [8]. Along with the complex domain dependent constraints, the FGO constraint is one of the main challenges that a planner needs to overcome for the above problems.Next, we first give the problem statement. Some definitions and properties are proposed to explain why FGOs occur for a planning problem. Then, a novel forward search algorithm is proposed to solve the planning with FGOs. Based on the evaluation, it can be concluded that planning with FGOs is still a challenge for current automatical planners but our method can solve it efficiency.


## 2. Problem Statement

Before introducing forced goal ordering (FGO), we first give the description of a planning problem(O,I,G) as given in [1].In a planning problem definition,O is a finite set of ground actions with the STRIPS style (in this paper). For any o∈O, there is o=(pre,add,del), where pre, add, and del are finite sets of ground atoms. pre is the precondition set under which the action is applicable. add and del are the atoms added or deleted after the execution of the action. I and G are the finite sets of ground atoms and represent the initial and goal state of the problem. For any given state s and action o∈O, the result of applying o to s is
(1)result(s,o)={s∪add(o)∖del(o),ifpre(o)⊆s,s,otherwise.
For the action sequence {o1,o2,…,on} (oi∈O, 1⩽i⩽n), there is
(2)result(s,{o1,o2,…,on})=result(result(s,{o1,o2,…,on-1}),on).
The planning problem is finding a sequence of actions π, such that G⊆result(I,π). The set of action sequence is defined as ΠO. A state s is reachable from the initial state if and only if ∃π∈ΠO, s.t., s⊆result(I,π). Similarly, an atom f is achievable from a certain state s if and only if f∈s or ∃π∈ΠO, s.t., f∈result(s,π). An action o is applicable in a reachable state s if and only if pre(o)⊆s.Definition 1 (forced goal ordering (FGO) [1]).
For the planning problem(O,I,G), let g,g′∈G be the atomic goals. We say that there is a forced ordering between g and g′, written as g′≺g, if and only if, for any state s(g,¬g′), there is no plan π satisfying g′∈result(s(g,¬g′),π). s(g,¬g′) represents a reachable state, in which g has just been achieved, but g′ is false.
In any given state, an atomic goal remaining false means that the goal is not achieved. Definition1 illustrates that forward search arrives at deadlock s(g,¬g′) when there is g′≺g and the atomic goal g is achieved before g′. In some of the literatures [2, 9], s(g,¬g′) is called a dead-end state too. During the planning process, forward search which violates any of the FGOs may lead the planning to a deadlock, from which there is no way to the goal state.
With respecting to the FGO, there is goal ordering defined as reasonable goal ordering (RGO) written asg′≺rg. There is a reasonable ordering between g and g′, if and only if, for any reachable state s(g,¬g′), there is no longer a plan that can achieve g′ from s(g,¬g′) without deleting g, at least temporarily [1]. So, if there is g′≺rg and g is achieved before g′, in order to get a plan solution, the planning must first delete the achieved goal g, then to achieve g′, and last to achieve g again. In this paper, as to focus the problem on FGO, it is supposed that there is no goal deletion during the planning process. Each goal cannot be deleted once it has been added.
The first planning domain for planning competition with FGOs is the Floortile proposed in the International Planning Competition (IPC) 2011 [10]. During the competition, no participating planner in the sequential satisficing track can solve it well. Figure 1 shows an example of the Floortile domain in the IPC 2011. In the initial state, the status of all floor tiles is clear. Floor tiles need to be painted black and white, while adjacent tiles should have different colors. Robots can only paint tiles that are in front (up) or behind (down). Moreover, once a tile is painted, a robot cannot stand on it. This particular configuration makes the domain very hard to solve because of the existence of FGOs. For example, suppose a robot first selects the tile(2,1) to paint in white. In further planning steps, the robot can only stand on a tile(2,1) to paint the front tile(3,1) in black. This process can be achieved if and only if the atom (robot-at tile(2,1)) is true. However, this atom is not true and cannot be added once the tile(2,1) has been painted. The reason is that the atom (robot-at tile(2,1)) is mutually exclusive with the atomic goal (painted tile(2,1) white), and (painted tile(2,1) white) cannot be deleted once it has been added. Therefore, painting tile (2,1) before (3,1) violates the FGO constraint, in consequence, causing the search to arrive at a deadlock.Figure 1
Floortile domain in IPC 2011.In this example, there are many FGOs in the Floortile problem, and the robots should paint tiles obeying a correct sequence. In the case of Figure1, the FGOs are(painted tile(3,1) black) ≺ (painted tile(2,1) white) ≺ (painted tile(1,1) black);(painted tile(3,2) white) ≺ (painted tile(2,2) black) ≺ (painted tile(1,2) white);(painted tile(3,3) black) ≺ (painted tile(2,3) white) ≺ (painted tile(1,3) black).In the above domain, all the FGOs exist in the initial state. No matter which approach is adopted to achieve an atomic goal, all the atomic goals should be achieved in a given sequence starting from the initial state. Otherwise, the planning may arrive at a deadlock. However, in some real-world planning problem, there is no FGO in the initial state. For anyg,g′∈G, planning starting from the initial state to firstly achieve g or g′ would not lead to a deadlock. However, the planning may arrive at a given state s(¬g1,¬g2,¬g3) (g1,g2,g3∈G) without FGO among g1, g2, and g3. Now, if certain plan as π1 is selected to achieve g1 while translating the search to state s(g1,¬g2,¬g3), then there is g2≺g3 or g3≺g2.Figure2 shows an example for the air defense of a naval group (ADoNG). A naval group has some Surface to Air Missile (SAMs) and chaffs to intercept the incoming antiship missiles. The arrived antiship missiles at the same time is supposed to locate at a spherical surface above the naval group, which can be transferred into a m×n rectangular plane as shown in Figure 2. In each rectangle, there is an antiship missile, while one ship of the naval group can fire a SAM or chaff to intercept it. However, once a chaff is employed to intercept an antiship missile in a given rectangle, the rectangles in the up, down, left, and right of the given rectangle should be interfered by the chaff cloud. If certain rectangle is interfered by the chaff cloud from one direction, the antiship missile in this interfered rectangle can only be intercepted by chaff, because chaff cloud can prevent the radar from guiding the SAM interception. Moreover, if certain rectangle is interfered by the chaff cloud from more than one direction, the antiship missile in this rectangle cannot be intercepted, because the radar of the naval group may lose the accurate position of the antiship missile. The goal state is to intercept all the incoming missiles by the given SAMs and chaffs.Figure 2
Air defense of a naval group.For the planning of the air defense of a naval group, there is no FGO in the initial state. Taking the problem shown in Figure3 as an example, there are 4 antiship missiles in a 2×2 rectangular plane with 3 chaffs and 1 SAM. Obviously, in the initial state, every antiship missile can be intercepted with the highest priority. However, if the antiship missile in rectangle (2, 1) is firstly intercepted by a chaff, there are FGOs (1,2)≺(1,1) and (1,2)≺(2,2) in the successor state, and the antiship missile in (1, 2) must be intercepted by a SAM. However, if the antiship missile in rectangle (2, 1) is firstly intercepted by a SAM, there is no FGO for the remaining antiship missiles in (1,1), (1,2), and (2,2).Figure 3
Air defense of naval group.


## 3. Related Works

Heuristic search planning (HSP) has become a dominant domain independent paradigm over the last decade [5]. The HSP method, first proposed by Bonet and Geffner [11], performs a forward search from an initial state to a goal state in a search graph. This method employs some powerful heuristic estimators to guide the search in a fast forward manner towards the goal state, with the help of heuristics for choosing helpful actions to extend the search closer to the goal state. In the past, great success has been achieved in heuristic search planning systems, such as FF [2], FD [12], SGPlan [13], and LAMA [5]. Researchers have also considered various goal interactions in multiple-goal achievement and detection [1, 14]. All of the above planners have their own approaches to deal with the goal orderings.Among the previous works, the most relevant methods to our approach are Goal Agenda Manager (GAM) and ordering landmarks. The concept of a Goal Agenda Manager (GAM) was proposed in [1] to detect the reasonable goal orderings. The GAM is widely used in many planning systems such as IPP and FF, which can improve the performances of IPP and FF dramatically. A GAM defines the order in which the subgoals are achieved. In the beginning of a search process, a GAM is employed to check all the ordering relationships of each atomic goal pair. Then, the search divides the goal set into many subsets so that the planner can achieve each of them in sequence.For each atomic goal pair asg,g′∈G, GAM uses FDgg=⋂o∈O,g∈add(o)‍del(o) and O*=Og∖{o∈O∣pre(o)∩FDgg=∅}, where Og={o∈O∣g∉del(o)}, to calculate whether there is an action sequence p∈PO* satisfying g′∈result(s(g,¬g′),p). If there is not, there exists an ordering defined as g′≺rg. Otherwise, the GAM checks whether g≺rg′ exists. Therefore, there are P|G|2 atomic goal pairs that need to be checked.A concept known as “landmark” is defined to extend the GAM on goal ordering at top-level atomic goals as well as certain states known as landmarks during a planning process [3, 4]. For a planning problem (O,I,G), an atom l is called a landmark if, for any p={o1,o2,…,on}∈PO and G⊆result(I,p), there is l∈result(I,{o1,…,oi}) (1⩽i⩽n). A planning system that uses landmarks obtains all the landmarks of the problem at the beginning of the planning process. The planner then orders them heuristically. It uses a backtracking method via a relaxed plan graph (RPG) [2] to find the candidate landmarks and their orders. For example, all the atomic goals are landmarks. For each atomic goal g, the atoms in ⋂∀o∈O,g∈add(o)‍pre(o) are treated as new landmarks, where there is relationship f≺rg for each f∈⋂∀o∈O,g∈add(o)‍pre(o). Then, f is treated as a new atomic goal. The landmark-generation algorithm repeats the above process from the top level of the RPG to the lowest level.The third method to handle the goal ordering is the incremental planning process adopted by the planner SGPlan6 [13, 15]. As shown in Figure 4, the incremental planning process try to check part of the goal orderings in the initial state. Some of the checked atomic goals which can be achieved with high priority are firstly handled. Then, the incremental planning process try to find out more other goal orderings in current state and achieve part of atomic goals with high priority. The planning continues the above process until all the atomic goals are achieved.Figure 4
The incremental planning process.


## 4. Why FGOs Occur?

Definition 2 (goal achievement operation (GAO)).
For planning problem(O,I,G), o∈O is a GAO, if ∃g∈G, satisfying g∈add(o). o is written as og.Definition 3 (available GAO).
o
g is available in a given state s, if and only if pre(og)⊆s, or ∃π∈ΠO, s.t.pre(og)⊆result(s,π).For an unachieved atomic goalg in s, an available GAO as og represents a plan, written as πog, while g∈result(s,πog). So, if pre(og)⊆s, there is πog={og}. Otherwise, if pre(og)⊆result(s,π), there is πog={π,og}.Definition 4 (available GAO sequence).
Suppose thatG′⊆G while s(¬G′) is reachable, and there is at least one available GAO as oi∈O (1⩽i⩽|G′|) for each gi∈G′ in s(¬G′) (|G′| is the number of atomic goals contained in G′). These GAOs can be ranked as an available GAO sequence if and only if(1)
these GAOs are ranked in a correct sequence{oj1,oj2,…,oj|G′|}, (ji=1,2,…,|G′|, jk≠jl if k≠l, 1⩽i, k,l⩽|G′|);(2)
there are number of|G′| corresponding plans {πj1,πj2,…,πj|G′|} such that
(3)pre(oj1)⊆result(s(¬G′),πj1),gj1∈result(s(¬G′),{πj1,oj1})=s1,pre(oj2)⊆result(s1,πj2),{gj2,gj1}⊆result(s1,{πj2,oj2})=s2,⋮pre(oj|G′|)⊆result(s|G′|-1,πj|G′|),G′⊆result(s|G′|-1,{pj|G′|,oj|G′|}).Property 1.
For the planning problem(O,I,G) with FGO constraints, the reachable state s is not a deadlock if and only if there is at least an available GAO sequence for the maximum unachieved atomic goal set in s.Proof.
Based on Definition4, suppose that the maximum unachieved atomic goal set in s is G′. Since goal deletion is not considered in this paper, there is a plan
(4)π={πj1,oj1,πj2,oj2,…,πj|G′|,oj|G′|},
s.t., G⊆result(s(¬G′),π). Therefore, s(¬G′) is not a deadlock. Additionally, if s is not a deadlock, there must be at least one available GAO sequence in s.Definition 5 (excludable constraint of GAO).
For a reachable states(¬g1,¬g2), there are available GAO og1 for g1 and og2 for g2. There is an excludable constraint in s(¬g1,¬g2), written as og1↛og2, if and only if og2 is unavailable in state result(s(¬g1,¬g2),πog1).Definition 6 (excludable GAO set).
In a reachable states(¬G′)(G′⊆G), the excludable GAO set for the available GAO og (g∈G′) is written as O^og(s(¬G′)), if and only if, (1) for any og↛og′(g′∈G′,  g′≠g), there is og′∈O^og(s(¬G′)); (2) for any og′∈O^og(s(¬G′)), there is og↛og′; (3) for any og′∉O^og(s(¬G′)), there is not og↛og′.Definition 7 (equivalent GAO).
In a reachable states(¬g)  (g∈G), og1 and og2 are two different available GAOs for g. og1 and og2 are equivalent in s(¬g), written as og1≅og2, if and only if O^og1(s(¬g))=O^og2(s(¬g)).Definition 8 (equivalent State).
Reachable statess1 and s2 are equivalent, written as s1≅s2, if and only if, for any π∈Πo, there is G⊆result(s1,π), there must be G⊆result(s2,π) and vice versa.
In a reachable states(¬g), for an available GAO og with pre(og)⊆s(¬g), there may be two different action sequences π1 and π2 satisfying pre(og)⊆result(s(¬g),π1) and pre(og)⊆result(s(¬g),π2). However, result(s(¬g),π1) might not be equivalent with result(s(¬g),π2). In this case, the atomic goal g achieved by the same GAO og may lead the search to two different nonequivalent states. Planning with this feature may increase the search space dramatically when handling the planning with FGOs. Therefore, with respect to the above case, we can define two different GAOs as ogπ1 and ogπ2 to replace og to ensure that, in a given state, achieving an atomic goal by the same GAO should lead the search to the equivalent state. Namely, for a given reachable state s(¬g) and an available GAO og, for any π1,π2∈ΠO, if there are pre(og)⊆result(s(¬g),π1) and pre(og)⊆result(s(¬g),π2), there must be result(s(¬g),{π1,og})≅result(s(¬g),{π2,og}).Property 2.
For a reachable sates(¬G′) (G′⊆G, g∈G′) and two available GAOs og1 and og2, there are s1=result(s(¬G′),πog1) and s2=result(s(¬G′),πog2). If both s1 and s2 are not deadlock and there is og1≅og2, there must be s1≅s2.Proof.
Suppose thatOG′ is the set of all possible available GAO sequences contained in s(¬G′), OG′∖g1 is the set of all possible available GAO sequences contained in s1, and OG′∖g2 is the set of all possible available GAO sequences contained in s2. As og1 and og2 have the same excludable GAO set, there must be OG′∖OG′∖g1=OG′∖OG′∖g2. It can be inferred that OG′∖g1=OG′∖g2. As s1 and s2 have the same set of possible available GAO sequences, it can be declared that, for any available GAO sequence contained in s1(s2), this available GAO sequence must be available in s2(s1). So there is s1≅s2.Property 3.
For the planning problem(O,I,G), s(¬g) is a reachable state. og1 and og2 are two different available GAOs of g in s(¬g) while og1≅og2. Starting from s(¬g), if selecting og1 to achieve g leads the planning to state s1 and selecting og2 leads the planning to state s2, then, for any ¬g1,¬g2∈si (i=1,2), if there is g1≺g2 in s1(s2), there must be g1≺g2 in s2(s1).Proof.
Based on the Property2, it can be inferred that s1 and s2 have the same set of possible available GAO sequences. So if there is g1≺g2 in s1, there is no available GAO sequence contained in s1 which can achieve g2 before g1. As s1 and s2 have the same set of possible available GAO sequences, so starting from s2, g2 cannot be achieved before g1 too. So there is g1≺g2 in s2. Obviously, by the same way, it can be inferred that, if there is g1≺g2 in s2, there must be g1≺g2 in s1.Property3 illustrates that, during the planning process, selecting the equivalent GAO to achieve an atomic goal introduces the same possible FGOs into the planning.Definition 9 (independent goal set).
For the planning problem(O,I,G), the goal set G can be divided into k independent goal sets, written as {G1,G2,…,GK} (1⩽k), while G1∪G2∪,…,Gk=G and Gi∩Gj=∅ (for all 1⩽i, j⩽k). Gi and Gj are called independent with each other, if and only if, for any gi∈Gi and gj∈Gj, there is no excludable constraint between the GAO of gi and gj in each reachable state.
Based on the above discussion, it can be concluded that FGOs occur just because there are excludable constraints among the GAOs of different atomic goals. Take the instance shown in Figure1 as a example. In the initial state, the available GAO for atomic goal (painted tile(3,1) black) is (paint-up robot1 tile(3,1) tile(2,1)). The available GAOs for atomic goal (painted tile(2,1) white) are (paint-up robot1 tile(2,1) tile(1,1)) and (paint-down robot1 tile(2,1) tile(3,1)), as there are(paint-up robot1 tile(2,1) tile(1,1))  ↛  (paint-up robot1 tile(3,1) tile(2,1));(paint-down robot1 tile(2,1) tile(3,1))  ↛  (paint-up robot1 tile(3,1) tile(2,1));So there is(painted tile(3,1) black)  ≺  (painted tile(2,1) white) in the initial state.
Furthermore, for the planning which has no FGO in the initial state, the excludable constraints among the GAOs may introduce FGOs into the planning process. As the example shown in Figure3, in the initial state, each antiship missile can be intercepted by a SAM or chaff. However, as there are(Chaff-Intercept (2,1))  ↛  (SAM-Intercept (1,1))(Chaff-Intercept (2,1))  ↛  (SAM-Intercept (2,2))the FGOs(intercept (1,2))  ≺  (intercept (1,1)) and (intercept (1,2))  ≺  (intercept (2,2)) occur.
Obviously, for the planning problem(O,I,G), if for all gi,gj∈G (i≠j) while gi is independent with gj as Definition 9 described, no FGO may occur during the planning process.
Next, a forward search algorithm is proposed based on the above discussion to solve the planning problem with different FGOs.


## 5. A Novel Forward Planning Algorithm

During the planning process, selecting a GAO with the bigger excludable GAO set to achieve an atomic goal has the higher probability to introduce FGOs into the planning. Generally, for the same atomic goal, a search algorithm prefers to select the GAO with the smaller excludable GAO set first to achieve it. However, for some planning problem, keeping to select the GAO with smaller excludable GAO set first may cause certain operation resource excessively consumed. In this case, the later planning process can only select the GAO with the bigger excludable GAO set to achieve each atomic goal. Then, planning may lead to a deadlock as the FGOs introduced by the excludable GAOs. Therefore, with respect to the planning algorithm proposed in this paper, the atomic goal asg1 with the fewest number of available GAO is firstly selected to be achieved by an available GAO with the biggest excludable GAO set. Then, calculate the number of available GAO for the remaining unachieved atomic goals. The atomic goal, whose number of available GAO is decreased after the achievement of g1, is selected to be achieved with high priority. Continuing the above process, if planning arrives at a state which contains an unachieved atomic goal without available GAO, move the achievement sequence of this atomic goal ahead and find an available GAO with the smallest excludable GAO set to achieve it, while ensuring that all the prior achieved goals can also be achieved by the prior selected GAOs (or the equivalent GAOs).The excludable GAO set based forward search algorithmEx_MsFS (multi-step forward search) for the planning with FGOs is displayed in Algorithm 1. In the initial state s, the planning selects an atomic goal with the fewest number of available GAO to be achieved first (step 04). With respect to the selected atomic goal as g, the available GAO as og with the biggest excludable GAO set is selected with the highest priority to achieve g (step 08). Then, in the successor state s′ after g achieved (step 09), there exist the following two cases. In case one, there is an unachieved atomic goal as g′, which has no available GAO in s′. In this case, s′ is a deadlock. All possible available GAOs for g′ in s′ are excluded by the GAOs which have been adopted to achieve the earlier selected atomic goals contained in L. So the achievement sequence of g′ should be moved ahead (step 12). The detailed moving algorithm is lately discussed in Algorithm 2. For case two (step 20), if all unachieved goals in s′ have available GAO, the atomic goals which have fewer available GAOs in s′ than that in s should be selected to be achieved with high priority starting from s′ by the depth-first search strategy (steps 23, 07).Algorithm 1:
Ex_MsFS algorithm.
Input: planning problem (O,I,G).
Output: plan π with G⊆result(I,p)
01s=I,
G′=∅, π=∅;
02do{
03Q=∅, L=∅;
04     select¬g∈s with the fewest number of available GAO;
05Q.push_back((s,g)), tems←s;
06do{
07s←Q.pop_back().s, g←Q.pop_back().g;
08       select an available GAOog with the biggest excludable GAO set;
09s′←result(s,πog); L.push_back((s′,o,s));
10for each  ¬g′∈s′
11if  g′ does not have available GAO in s′
12if Move_ahead(L,g′,L′)==true;
13L.clear(), L←L′, s′←L.back().s′;
14else
15if  G′.contain(g′)== true
16return FAILURE;
17else
18Q.clear(), L.clear(), G′.insert(g′);
19Q.push_back((tem_s,g′)), go to step 05;
20for each  ¬g′∈s′
21if Available GAOs of g′ in s′ is fewer than that of in s
22ifQ.contain((s′,g′))==false
23Q.push_back((s′,g′));
24           }while(Q≠∅)
25fori=0:L.size()-1
26π.push_back(L[i].o);
27s←s′, L.clear();
28    }while(G⊈s)
29returnπ.Algorithm 2:
M
o
v
e
_
a
h
e
a
d
(
L
,
g
,
L
′
).
Input: Achieved goal sequence list L. Goal g whose achievement
sequence needs to be moved ahead.
Output: New goal achievement sequence list L′
01 boolsuccess_moved=false, num←L.size();
02fori=num:1
03L′←∅;
04for  (k=1;k⩽i-1;k++)
05state_op_pair←L[k];
06L′.push_back(state_op_pair);
07s1←L[i].s;
08       boolhave_op=false;
09Og(s1)={Og1(s1),Og2(s1),…,Ogm(s1)}
is the available GAO
set ofg in s1. For ∀o,o′∈Ogn(s1), there is o≅o′(1⩽n⩽m).
The GAO in setOgn1(s1) has the smaller excludable GAO
set than that of inOgn2(s1) if there is 1⩽n1<n2⩽m;
10forl=1:m
11          select an available GAOog′ from Ogl(s1);
12s2=result(s1,πog′)
13if  (∃¬g′′∈s2, g′′ has no available GAO in s2)
14           continue;
15else
16have_op=true;
17           break;
18if(have_op==true)
19L′.push_back((s2,og′,s1));
20       boolis_break=false;
21forj=i:num
22o←L[j].o;
23if(o or its equivalent GAO o′ is available in s2)
24tem_o←o or tem_o←o′;
25s′=s2;
26s2=result(s′,πtem_o);
27L′.push_back((s2,tem_o,s′));
28else
29is_break=true;
30          break;
31if(is_break==false)
32success_moved=true;
33       returnsuccess_moved;
34else
35       continue;
36   returnsuccess_moved;The algorithmMove_ahead used in step 12 of Algorithm 1 is displayed in Algorithm 2. For the step 11 of Algorithm 1, when there is an atomic goal as g having no available GAO in current state, it means that certain achieved goals stored in list L (step 09 of Algorithm 1) should not be achieved before g. So the achievement sequence of g should be tried to move ahead. Suppose there are num elements contained in L. Each element is written as (s′,og,s), which means that selecting the available GAO og in current state s to achieve goal g transfers the state to the successor s′. The atomic goals contained in the list L are achieved by the sequence from the head to the end. The algorithm tries to set g as the ith (1⩽i<num) goal to be achieved (step 02). The atomic goals stored in L from the location index 1 to i-1 are still achieved by the previously selected GAOs (steps 04–06). Then, it is the turn to select an available GAO to achieve g. As to ensure that all the atomic goals stored in list L from the location index i to num can still be achieved by its previously selected GAOs or the equivalent GAOs of the previously selected GAOs, the algorithm chooses an available GAO with the smallest excludable GAO set to achieve g (step 09–17). Now, the algorithm starts to check whether the atomic goals stored in list L from the location index i to num can still be achieved by its previously selected GAOs or whose equivalent GAOs (steps 21–35). If it is, it means that, with respect to the atomic goals in L, g can be taken as the ith goal to be achieved. So the algorithm returns true (steps 31–33). Otherwise, move g ahead as the (i-1)th goal to be achieved. If achieving g before all the atomic goals in list L still cannot ensure that the atomic goals stored in list L can be achieved by their previously selected GAOs or whose equivalent GAOs, the Move_ahead algorithm returns false (step 36).Based on Algorithms1 and 2 and the Definition 9, it can be inferred that, for each do_while loop (steps 06–24) of the algorithm Ex_MsFS, the achieved goals contained in each list L defined in step 03 of Algorithm 1 come from the same independent goal set. During the depth-first search process, all the atomic goals which are related with each selected goal (in step 04 of Algorithm 1) are stored in each list Q. Obviously, the atomic goals in each list Q are from the same independent goal set. For the moving ahead process displayed in Algorithm 2, the requirement that all the achieved goals in each list L can still be achieved by their previously selected GAO or their equivalent GAO after the achievement sequence of certain atomic goal is moved ahead, is to ensure that with respect to each list L, the elements having contained in list Q would not be changed during the moving ahead process. The reason is that the equivalent GAO makes an atomic goal lose the same number of available GAOs. So the depth-first process could not be inferred by the moving ahead process.Figure5 gives an example of the air defense for a naval group to illustrate the search process of Ex_MsFS. In the initial state, there are 6 antiship missiles. There are 5 chaffs and a SAM that can be used to intercept all the antiship missiles while the antiship missile in rectangle (2,1) must be intercepted by a chaff. As there is only one available GAO (Chaff_Inter(2,1)) for the missile in (2,1), Ex_MsFS selects the missile in (2,1) to firstly intercept by a chaff and transfers the state to s1 (step 04 of Algorithm 1). Element (s1,Chaff_Inter(2,1),I) is pushed into list L (steps 08-09 of Algorithm 1). When the missile in (2,1) is intercepted by a chaff, the rectangles (1,1) and (2,2) are interfered by the chaff cloud coming from rectangle (2,1). So the missiles in (1,1) and (2,2) cannot be intercepted by SAM. The number of available GAOs for missiles in (1,1) and (2,2) in s1 is fewer than that of in I. Therefore, missiles in (1,1) and (2,2) are pushed back into list Q (steps 22-23 of Algorithm 1) and assigned the higher priority to be intercepted during in the depth-first process. Suppose that missile in (2,2) is firstly selected to be intercepted by a chaff in state s1 (step 07). Planning leads to s2 and element (s2,Chaff_Inter(2,2),s1) is pushed back into list L (step 09 of Figure 4). At the same time, missiles in (1,2) and (2,3) are pushed back into list Q (step 22 of Algorithm 1).Figure 5
The example of air defense for a naval group.Continuing the above process, element(s3,Chaff_Inter(2,3),s2) is pushed back into list L and missiles in (1,3) is pushed back into list Q. Now, the planning arrives at state s3 and list Q pops back the missile in (1,3) to intercept. As rectangle (1,3) is interfered by the chaff cloud from rectangle (2,3), the missile in (3,1) can only be intercepted by a chaff. In this case, rectangle (2,3) should be interfered by the chaff cloud from rectangles (2,2) and (1,3) as the state s4 shows. So there is no available GAO for the missile in (1,3), and the interception sequence of the missile in (1,3) needs to be moved ahead (steps 11-12 of Algorithm 1).Now, themove_ahead algorithm tries to intercept the missile in (1,2) before that of in (1,3). It means to intercept the missile in (1,2) using (Chaff_Inter(1,2)) starting from state s3. This selection may lead the search to state s5, in which missiles in (1,1) and (1,3) cannot be intercepted. So the intercept sequence of missile in (1,2) should be further moved ahead. The move_ahead algorithm tries to intercept it before the missile in (2,3), which leads the planning to state s6. Obviously, the missile in (1,1) cannot be intercepted starting from s6. So the missile in (1,2) should be intercepted before the missile in (2,2). It means intercepting the missile in (1,2) starting from s1. Now, the available GAO (SAM_Inter(1,2)) with the smaller excludable GAO set is selected. Furthermore, all the missiles in (2,2), (2,3), and (1,3) can still be intercepted by its previously selected GAOs. After the moving ahead process, planning arrives at state s8, from which the goal state can be arrived after the missile in (1,1) is intercepted by the last one chaff.


## 6. Discussion of the Problem and Algorithm

This section proposes some properties about the planning with FGOs and the search algorithmEx_MsFS.Property 4.
The complexity for solving the planning with FGOs, all of which exist in the initial state and are irrelevant with the approach for each atomic goal to be achieved, isPnn, where n=|G|.Proof.
As all the FGOs exist in the initial state and are irrelevant to the approach for each atomic goal to be achieved, the search can arrive at the goal state if and only if all the atomic goals are achieved by a correct sequence. It is a complete permutation problem. So the complexity isPnn.Property 5.
The complexity for solving the planning problem, in which there is no FGO in the initial state but FGOs would occur during the planning process if and only if certain goal is achieved by an inappropriate approach, is up toPnn·Kn, where n=|G| and K is the average number of approach that can be adopted to achieve each atomic goal.Proof.
In this case, all the atomic goals should be achieved in a correct sequence, and each atomic goal should be achieved by an appropriate approach. However, as there is no FGO in the initial state, not all the atomic goals need to take part in the complete permutation. So the complexity is up toPnn·Kn.For the Floortile problem, the solving complexity isPnn while the air defense planning problem for a naval group is up to Pnn·Kn.Property 6.
For a solvable problem with FGOs, theEx_MsFS algorithm is sufficient to returning a plan solution if the move_ahead algorithm returns true (step 12 of Algorithm 1) for each time it is called.Proof.
If themove_ahead algorithm returns true (step 12 of Algorithm 1) for each time that it is called, it means the search process which violates certain FGO constraints has been put right. So the search process can arrive at the goal state and return a plan solution.For some planning problem, the search may arrive at certain state, from which no matter which, atomic goal is firstly selected to achieve, the search should arrive at a deadlock. In this case, themove_ahead algorithm always returns false and the Ex_MsFS algorithm cannot return the plan solution. Therefore, further works need to be done to extend the Ex_MsFS algorithm to a more general case.Property 7.
Evaluated by the Relaxed Graph [2], Ex_MsFS algorithm is an enforce hill-climbing algorithm, which climbs multiple steps each time.Proof.
SupposeH(s) is the distance, calculated by the Relaxed Plan Graph, between the reachable state s and the goal state G, where H(G)=0. In the estimator of Relaxed Graph,
(5)H(s)=hg1(s)+hg2(s)+⋯+hgn(s)-∑Os‍(|o|-1),
where gi∈G (1⩽i⩽n) is the unachieved atomic goal in s, and hgi(s) is the number of actions in the relaxed graph to achieve the atomic goal gi starting from s. Set Os contains actions shared by different atomic goals during their achievements in the relaxed graph, where |o| is the frequency of o that has been shared. For each atomic goal as gi selected in step 04 of Algorithm 1, the Ex_MsFS algorithm selects an available GAO and generates a plan to achieve gi, which transfers the search from the current state s to the successor state s′. As action deletion is not considered in the relaxed graph, there are hgi(s′)=0 and
(6)H(s)-H(s′)=hgi(s)-(∑Os‍(|o|-1)-∑Os′‍(|o|-1)).
Suppose thatgi has k independent actions to other atomic goals in the Relaxed Graph starting from s. The value of ∑Os‍(|o|-1)-∑Os′‍(|o|-1) is hgi(s)-k. Therefore, for each selected atomic goal, there is H(s)-H(s′)=k. The search direction of the Ex_MsFS algorithm is along the direction of the enforced hill climbing by k steps at a time toward a goal state.


## 7. Evaluation

This paper evaluates the proposed algorithmEx_MsFS by comparing it with the following planning systems:(1)
FF planning system [2], in which the GAM heuristic is used for the detection of goal ordering,(2)
SGPlan6 [13], which adopts the incremental planning process to handle the goal orderings,(3)
LAMA 2008 planning system [5], which adopts the hill-climbing strategy where the preferred actions of each step are selected by the FF and landmark heuristics. Moreover, the orderings of (disjunction) landmarks are calculated based on the domain transition graph and the causal graph.FF, SGPLan6, and LAMA 2008 won the 1st prize of the satisficing planning track in IPC 2001, 2006, and 2008 respectively. In addition, the LAMA 2008 planning system consists of translating, processing, and searching modules. The translating and processing modules are used to construct some structured data, based on which, searching module is employed for forward search. In this paper, in order to compare theEx_MsFS with the previous approaches, we use the Ex_MsFS algorithm to replace the search modules of the Lama 2008 planning system.The competition domains are the Floortile proposed in IPC 2011 and the air defense of naval group problem introduced in Section1. For an air defense of naval group problem, there are m×n antiship missiles while |(m×n)/3| SAMs and m×n-|(m×n)/3| chaffs can be used. As this paper focuses on the efficiency when to solve a planning problem with FGOs, the quality of the planning solution is not considered. So we evaluate each planner by the scale of planning problems it can solve. The experiments are implemented in the Mac OS X with 2.4 GHz Intel Core 2 Duo and 2 GB 1067 MHz DDR3 memory. Each instance fails if the running time is more than 1,200 seconds.Figure6 shows the running time curves of the four different search approaches on the Floortile domain. There are 20 instances while LAMA 2008 can only solve 3 instances and FF can only solve 4 instances. However, SGPlan6 and the Ex_MsFS algorithm can solve all of the instances. Moreover, in this domain, SGPlan6 can solve each instance with the fewer time cost than Ex_MsFS. The reason is that the incremental planning process is very suitable in handling the FGOs of the Floortile domain. Taking the instance displayed in Figure 1 as an example, the incremental planning process first paints the upest tiles as (3,1), (3,2), and (3,3). Then, it paints the tiles (2,1), (2,2), and (2,3). At last, it paints the tiles (1,1), (1,2), and (1,3). This process satisfies the FGO constraints.Figure 6
Planning results of the Floortile.For the air defense of naval group problem, SGPlan6 can only solve only 1 out 0f the 17 instances while FF and LAMA 2008 can solve 10 instances. Moreover, as there are time constraints during the air defense process of the naval group in real world, if we require that each instance should be solved within 20 seconds, FF can solve only 7 instances and LAMA 2008 can only solve 6 instances. However, theEx_MsFS approach can solve all of the 17 instances and return the solution plan for each instance within 10 seconds.Based on Figure7, it can be inferred that air defense of naval group problem is a new challenge for many current planners and Ex_MsFS can solve the planning problems with different FGOs efficiently.Figure 7
Planning results of air defense of naval group problem.


## 8. Conclusions and Future Works

This paper contributes to introduce a new planning domain with FGOs, for which all the current related planners do not perform well when solving it. Then, a new search algorithm is proposed which can solve the planning problem with different FGOs efficiently.For future works, theEx_MsFS should be extended to a more general case to solve more real-world problems with FGOs. Also, machine learning approach [16, 17] can be employed to obtain more informed about FGOs. The learned knowledge can improve the efficiency of the search process. Moreover, a human-computer method is considered for planning with FGO constraints. As some FGO constraints may easily be inferred by humans and other FGO constraints can be learned easily by computers, a human-computer method can be employed in a mixture of automatic and hand-crafted control rules [18]. In addition, if two different domains have similar subgoals interaction, the knowledge of deadlock checking leaned from one domain can be considered transferrable to other domains [19].



---

*Source: 963874-2013-07-08.xml*