Automated Planning seeks to nd a sequence of actions, a plan, transforming the environment from its initial state to some goal state. In real-world environments, however, exogenous events might occur and might modify the environment without agent's consent. Besides disrupting agent's plan, events might hinder agent's pursuit towards its goals and even cause damage (e.g. destroying the robot). In this paper, we present how planning problems with non-deterministic events can be translated into Fully-Observable Non-Deterministic (FOND) planning problems and hence we can exploit FOND planning engines to solve them (i.e., nd strong cyclic plans). Speci cally, we will consider two cases in a single agent scenario { at most one event can occur after agent's action or a set of independent events can occur after agent's action. We compare the FOND-based approach with a traditional planning/execution/replanning one to highlight the performance gap as well as success rate of the latter approach.
Planning and acting in real-world scenarios [
The concept of events in planing is not new [
In this paper, we focus on a single-agent planning in fully observable
environment with deterministic action e ects and non-deterministic exogenous events
Copyright c 2019 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
where, roughly speaking, the task is to nd policies such that the agent
eventually reaches its goal (i.e., strong cyclic plans) under the fairness assumption
that each event when applicable has a chance to occur. We consider two
assumptions such that in the rst one after agent's action at most one event can
occur, while in the second one after agent's action a set of independent events
can occur. We show how planning problems with events under both
assumptions can be compiled to FOND planning that focuses on a di erent challenge {
non-deterministic action e ects (note that, for example, problems with partially
observable environment can also be compiled to FOND [
Classical planning, in particular, assumes a static, deterministic and fully observable environment; a solution plan amounts to a sequence of actions. Technically, a classical planning domain model is a tuple D = (L; A), where L is the set of propositional atoms used to describe the state of the environment (set of propositions from L that are true), and A is the set of actions over L. An action is a tuple a = (pre(a); del (a); add (a)), where pre(a); del (a) and add (a) are sets of atoms from L representing a's precondition, delete, and add e ects, respectively. We assume that del (a) \ add (a) = ;. An action a is applicable (or executable) in a state s if and only if pre(a) s. If possible, application (or execution) of a in s, denoted as (s; a), yields the successor state of the environment (s n del (a)) [ add (a), otherwise (s; a) is undened. The notion of applicability can be extended to sequences of actions, i.e., (s; ha1; : : : ; ani) = (: : : (s; a1) : : : ; an).
A classical planning problem is a tuple P = (D; I; G), where D is a planning domain model, I is the initial state of the environment, and G is the goal, generally in the form of a set of propositions. A solution plan (for a planning problem) is a sequence of actions such that their consecutive application starting in the initial state results in a state satisfying the goal (i.e., a goal state). 2.1
Fully Observable Non-Deterministic (FOND) planning assumes fully observable
and static environment but in contrast to classical planning actions have
nondeterministic e ects [
Similarly to the de nition of an action, an event is a tuple e = (pre(e); del (e); add (e)), where pre(e), del (e) and add (e) are sets of atoms representing e's precondition, delete, and add e ects, respectively. We assume that del (e)\add (e) = ;. Applicability of an event in a state as well as the result of an application (or execution) of an event is de ned in the same way as for actions. In contrast to actions that are executed by agents, events can occur regardless of agent's consent. Technically, an event can (but does not necessarily have to) occur in a state where event's precondition is met modifying the state of the environment according to event's e ects. A planning domain model , in this case, is a triple D = (L; A; E), where L is the set of propositions, A and E is the set of actions and events over L, respectively. A planning problem, P = (D; I; G), is de ned analogously to the classical planning case.
We de ne a noop action/event that represents that no action has been taken by agent, or event has occurred. Formally, pre(noop) = del (noop) = add (noop) = ;.
We say that events ei, ej are independent if and only if del (ei) \ (pre(ej ) [ add (ej )) = ; and del (ej ) \ (pre(ei) [ add (ei)) = ;.
The following assumption simpli es the reasoning by considering a singleagent scenario such that actions of the agent and events of the environment alter like in a two-players game. The process hence follows the pattern in which the agent can apply an action (not necessarily has to), then the environment can trigger (apply) an event (not necessarily has to), and so on. Formally: Assumption 1. Let D = (L; A; E) be a planning domain model. In a current state s 2 2L, the agent can apply an action a 2 A [ fnoopg such that a is applicable in s. After that, a (arbitrarily selected) event e 2 E[fnoopg, applicable in (s; a), is applied resulting in a state s0 = ( (s; a); e) which will become a new current state. We say that s0 is a successor state of s; a.
The following assumption extends the previous assumption by considering the pattern in which the agent can apply an action (not necessarily has to), then the environment can trigger (apply) a set of independent events (not necessarily has to), and so on. Formally: Assumption 2. Let D = (L; A; E) be a planning domain model. In a current state s 2 2L, the agent can apply an action a 2 A [ fnoopg such that a is applicable in s. After that, a (arbitrarily selected) set of independent events Ei E [ fnoopg, applicable in (s; a), is applied resulting in a state s0 = ( (s; a); Ei) which will become a new current state. We say that s0 is a successor state of s; a.
Let D = (L; A; E) be a planning domain model. We say that a state s0 2 2L is reachable from a state s 2 2L with respect to D and Assumption 1 (Assumption 2) if and only if there exists a sequence of actions and events (sets of independent events), including noops, such that its consecutive application in s results in s0. Otherwise, we say that s0 is unreachable from s.
Let P = (D; I; G) be a planning problem. Atoms p; q for which it is the case that there does not exist a state s reachable from I such that p; q 2 s are mutually exclusive , or shortly mutex .
Solutions in non-deterministic planning are in the form of policies, mappings from states to actions (similarly to probabilistic or FOND planning, for example). Policies, in plain words, provide information about which action the agent has to apply in a current state of the environment. As we assume events might be triggered between actions the agent executes, the policy execution interleaves agent's actions (including \noop") and environment's events (including \noop"). De nition 1. Let D = (L; A; E) be a planning domain model and P = (D; I; G) be a planning problem. We say that : 2L ! A [ fnoopg is a policy for P such that for each s 2 2L reachable from I, (s) is applicable in s.
In analogy to FOND planning, we can de ne a strong cyclic plan that represents a policy that, roughly speaking, has to guarantee that the agent will eventually achieve its goal under the fairness assumption that each applicable event/set of independent events (including \noop") in each (reachable) state has a chance to be applied. The strict variant, i.e., a strong acyclic plan, guarantees that the agent always reaches a goal state in a nite number of steps (no state can be visited more than once).
De nition 2. Let D = (L; A; E) be a planning domain model and P = (D; I; G) be a planning problem. Let be a policy for P. We construct a directed graph G such that its nodes are states S 2L, I 2 S, for each s 2 S and each its successor state s0 of s; (s) there is an edge from s to s0.
A strong cyclic plan for P is a policy (for P) such that for each state s in G there is a path to a goal state.
A strong acyclic plan for P is a policy (for P) such that for each state s in G there is a path to a goal state and G is acyclic. 2.3
Actions as well as events in uence each other by achieving atoms that are
required by other actions/events, or, in contrast, delete atoms required by other
actions/events. An early work of Chapman [
De nition 4. Let D = (L; A; E) be a planning domain model. We say that an action/event x 2 A [ E is a disabler for an event e 2 E if del(x) \ pre(e) 6= ;. 2.4
Standard action (and event) de nition can be extended by Conditional E ects that capture possible state changes if some extra condition is met in the current state. Formally, a conditional e ect of an action (or event) x is speci ed as ce (x) = (cond (x); cdel (x); cadd (x)) where cond (x) is a set of atoms representing a condition and cdel (x); cadd (x) are sets of atoms representing conditional delete and add e ects respectively. In plain words, if a condition in a current state is met, then the e ects take place in the resulting state after action application. Action (or event) de nition can be extended as follows x = (pre(x); del (x); add (x); ce 1(x); : : : ; ce k(x)), where ce 1(x); : : : ; ce k(x) are conditional e ects of x. Applicability of x in a state s is still determined as whether pre(x) s. The result of application of x in s is s n (del (x) [
[ condi(x) s cdel i(x)) [ add(x) [
[ condi(x) s cadd i(x)
In a nutshell, conditional e ects do not in uence action (or event)
applicability but modify the resulting state if the conditions are met in the current state.
Conditional e ects can be compiled away, i.e., an equivalent classical
representation can be obtained, however, the representation either grows exponentially
or the length of solution plans grows polynomially [
For the sake of clarity, we will use conditional e ects in our compilations of
planning problems with events into FOND planning. Conditional e ects are now
supported by many state-of-the-art classical planners [16] as well as the FOND
planner PRP [
To illustrate our concepts we introduce three case studies. 3.1
\Sticky" and \Slippery" BlocksWorld
We introduce a variant of the well known 4-ops BlocksWorld domain [
Technically speaking, the operators unstack, stack, pickup and putdown are amended as follows. Unstack and pickup are split into \slippery" and \sticky" variants, where each variant requires the corresponding robotic hand as a precondition. Precondition of both variants of unstack and pickup contains a (movable ?b) predicate representing whether a block ?b can be moved by either robotic hand. The add e ects of the \sticky" variant of unstack and pickup is extended by a (sticky ?b) predicate representing that a block ?b became \sticky".
We de ne two events such that an event slip causes the block held by the \slippery" hand to fall onto the table and an event stick makes the \sticky" block unmovable (by removing the (movable ?b) predicate).
A strong acyclic plan unstacks blocks from their initial position with the \slippery" hand and puts them down on the table (if they do not fall down by themselves) and then stack them on their goal positions with the \sticky" hand (if they are in the goal positions they do not have to be moved). A strong cyclic plan, for instance, can a ord to use only the \slippery" hand, since blocks that fell down can be picked up again (and eventually be placed into their goal positions). 3.2
We introduce a simpli ed variant of task planning for AUV, inspired by the
recent work of Chrpa et al. [
Ships, however, are not controlled by the agent, i.e., ships are controlled by the environment. Ships can move only on some cells of the grid or might not be present in the area. Each ship can enter the area at its entry cells, can move to adjacent cells according to its route, and leave the area at its exit cells. A ship can appear in its entry cell, if the ship is not already in the area. A ship can leave the area, if it is in its exit cell. Two \move" events are considered, move-ship-tofree and move-ship-to-auv. Both require that the ship can move to the destination cell. The e ect of both events is that the ship moves to the destination cell. If the ship moves to a free cell, then besides the cell becomes not free for a moment, nothing else happens. However, if the ship moves to the cell with the AUV, then the AUV is destroyed (and can no longer perform any action).
A strong cyclic plan has to avoid situations in which the AUV is, after applying its action, next to any ship, or in any ship's entry point (if the ship is not yet in the area). Strong acyclic plans might not always exist, since ships can (if being active adversaries) prevent the AUV to get to some resources. 3.3
The Perestroika domain we introduce here is inspired by the well known Perestroika game (also known as a Toppler game). In our domain, an agent has to navigate through a 4-grid of solid and shrinking platforms and collect all resources that can be placed on solid platforms. Solid platforms remain stable, i.e., they do not change its size nor disappear. In contrary, the shrinking platforms can have large, medium or small shape, or disappear completely.
The agent can perform two types of actions. It can move to a neighbouring platform (if it has not disappeared) and/or collect a resource if the resource is on the same platform as the agent. Shrinking platforms are a ected by ve events each. Two events change the shape of the platform from large to medium and from medium to small, respectively. Two events make the platform disappear if it has a small shape { the di erence is whether the platform is empty or the agent is on it. In the former case, the platform just disappears whereas in the latter case it kills the agent. The last event allow the platform to reappear in a large shape.
A strong cyclic plan has to avoid situations in which the agent moves to or stays on small platforms. Also, the agent must always have an escaping way to a nearby solid platform to avoid being \trapped" on a shrinking platform which might disappear at some point and kill the agent. Similarly to the AUV domain, strong acyclic plans might not always exist as the agent might have to wait until the shrinking platforms are large enough to be safely crossed. 4
In FOND planning, the agent does not have control of action outcome but the outcome is determined immediately after action execution nishes. In contrast, an event might be applicable even without \enabling" it by agent's actions (e.g., the event preconditions are met in the initial state), or when \enabled" by agent's action event's applicability does not cease until some other action or event \disables" it. 4.1
Let D = (L; A; E) be a domain model. We construct an equivalent FOND domain model DF = (LF ; AF ) as follows. We introduce atoms (act-turn) and (ev-turn) https://en.wikipedia.org/wiki/Perestroika (video game) to determine \action" and \event" turn respectively. For each event ei 2 E we introduce atoms (enab-ei) and (disab-ei) representing whether ei is applicable in a current state or not, and an atom (selected-ei) representing whether ei has been selected. LF is constructed by a union of the introduced atoms and L (without loss of generality we assume that none of the introduced atoms is in L). An action aj 2 A is translated into ajF 2 AF as follows: pre(ajF ) del (ajF ) add (ajF ) = = = = pre(aj ) [ f(act-turn)g del (aj ) [ f(act-turn)g [ [f(enab-ei) j aj is a disabler for eig [ [f(disab-ei) j aj is a sole enabler for eig add (aj ) [ f(ev-turn)g [ [f(disab-ei) j aj is a disabler for eig [ [f(enab-ei) j aj is a sole enabler for eig
ce ei (ajF )
(pre(ei) n add (aj ); (disab-ei); (enab-ei)) On top of the actions de ned in the domain model we have to explicitly model the \noop" action anFoop 2 AF that only switches from the action to the event turn (as the agent decided to do nothing in its turn). In particular, pre(anFoop) = del (anFoop) = f(act-turn)g and add (anFoop) = f(ev-turn)g.
The ajF actions can be executed in the \action turn" and since they correspond to the actions in A their e ects are deterministic. After executing an action we move to the \event turn".
In the \event turn", we have to \transfer" non-deterministic events into nondeterministic action e ects. We can do that in two steps. First, we select an event or \noop" by non-deterministic action e ects. Then, if the selected event is enabled, the event is executed, otherwise (if the event is disabled) the case is considered as \noop". The \event selecting" action asel 2 AF is encoded as follows, del 0(asel) and add 0(asel) represent the selection of \noop" (i.e., no event will be executed in the current \turn") while del i(asel) and add i(asel) represent the selection of an event ei 2 E (all the events in E are considered): pre(asel) = f(ev-turn)g del 0(asel) = f(ev-turn)g add 0(asel) = f(act-turn)g del i(asel) = f(ev-turn)g add i(asel) = f(selected-ei)g
Then, for each event ej 2 E we construct two actions aeej 2 AF and aedj 2 AF representing an execution of ej if enabled or resorting to the \noop" case if ej pre(aeej ) [f(enab-ei) j ej is a disabler for eig [ [f(disab-ei) j ej is a sole enabler for eig add (ej ) [ f(act-turn)g [ [f(disab-ei) j ej is a disabler for eig [ [f(enab-ei) j ej is a sole enabler for eig (pre(ei) n add (ej ); f(disab-ei)g; f(enab-ei)g)
For a planning problem P = (D; I; G), the corresponding FOND problem PF = (DF ; IF ; G) is constructed such that
IF = I [ f(act-turn)g [ f(enab-ei) j pre(ei) Ig [ f(disab-ei) j pre(ei) 6 Ig:
We can see that to solve the FOND planning problem we have to simulate \action" and \event" turns. The (act-turn), (ev-turn), (selected-ei) atoms ensure the applicability of an action, of the event selection action, of an event, respectively. In particular, in the action turn an action is (non-deterministically) selected. The event turn comprises an \event selecting" action and possibly an \event" action. The \event selecting" action represents event selection (or noop selection) in its non-deterministic e ects. Noop selection skips the \event" action (as no event occurs). Otherwise, if an event ei is selected ((selected-ei) becomes true), then either aeei or aedi can be applied depending whether ei is applicable or not. Applying aeei simulates ei application while aedi simulates noop as ei is inapplicable. Also, we have to maintain information about applicability of particular events, which is done through the (enab-ei) and (disab-ei) atoms. If an action or event is a sole enabler for ei, then it adds (enab-ei) and removes (disab-ei). Analogously, if an action or event is a disabler for ei, then it adds (disab-ei) and removes (enab-ei).
Let F be a strong cyclic plan of PF , then a strong cyclic plan for a corresponding planning problem P is constructed as follows. For each sF 2 2LF and aiF 2 AF such that F (sF ) = aiF we de ne (sF \ L) = ai. In plain words, we consider only pairs hstate,actioni from the strong cyclic plan associated with actions translated from actions de ned in P. As states of PF contain additional atoms, these have to be removed to obtain states of P. It can be observed that if a strong cyclic plan of PF is found there is no \open state" which is not a goal state. As events occur implicitly (as in Assumption 1), the corresponding strong cyclic plan of P has to consider only \action turns". The above is summarised in the following theorem.
Theorem 1. Let P be a planning problem (with events) and PF be its translation into a FOND problem (as described above). Then, F is a strong cyclic plan of PF if and only if (constructed from F as above) is a strong cyclic plan of P.
Proof (Sketch). To nd a strong cyclic plan of PF the \action" and \event" turns alternate. In particular, in the action turn a planner (non-deterministically) selects an action. The event turn comprises an \event selecting" action and possibly an \event" action so simulate all possibilities of event occurrence. The \event selecting" action represent possibilities of event selection (or noop selection) in its non-deterministic e ects. Noop selection skips the \event" action (as no event occurs). Otherwise, if an event ei is selected ((selected-ei) becomes true), then either aeei or aedi can be applied depending whether ei is applicable or not. Applying aeei simulates ei application while aedi simulates noop as ei is inapplicable. It can be seen that (enab-ei) is true if and only if ei is applicable while (disab-ei) is true if and only if ei is inapplicable. Multiple noops caused by disabled events result in the same state as the regular noop. Enabled events result in (possibly) new states that have to be explored. If a strong cyclic plan of PF is found there is no \open state" which is not a goal state. As events occur implicitly (as in Assumption 1), the corresponding strong cyclic plan of P has to consider only \action turns". 4.2
Let D = (L; A; E) be a domain model. We construct an equivalent FOND domain model DF = (LF ; AF ) as follows. We introduce atoms (act-turn), (enab-ei), (disab-ei) and (selected-ei) as in the previous case. On top of that, we introduce atoms (ev-turn) and (ev-turn2) representing two parts of the event turn and for each event ei 2 E, an atom notsel-ei representing that ei has not been selected (in a given turn), and an atom (wenab-ei) representing that ei will be enabled in the next turn. Similarly to the previous case, LF is constructed by a union of the introduced atoms and L (without loss of generality we assume that none of the introduced atoms is in L). The translation of each action aj 2 A into ajF 2 AF as well as the noop action is the same as in the previous case.
The \event selecting" action asel 2 AF has to re ect selection of sets of independent events (including noop). That involves calculating power sets for all sets of independent events. To reduce the number of these power sets we can exploit mutexes such that events whose preconditions are mutex are not present in any set together (despite being independent). In the AUV domain, for example, a single ship cannot move between di erent locations at the same time as it can be at at most one location, or outside at the same time.
The precondition of asel as well as the e ects representing the noop event selection is the same as in the previous case. For a set of independent events fei1 ; : : : ; eim g E we de ne non-deterministic e ects del i(asel) and add i(asel) in which all the sets of independent events from E are considered: del i(asel) = f(ev-turn); (notsel-ei1); : : : ; (notsel-eim)g add i(asel) = f(ev-turn2); (selected-ei1); : : : ; (selected-eim)g
For the \event" actions aeej 2 AF and aedj 2 AF representing an execution of ej (if enabled or resorting to the \noop" case if disabled), the main di erence, in contrast to the previous case, is that after applying the \event" action, we are still in the \event" turn (hence we can apply all the events from the selected set). Also, enabling events must not in uence applicability of selected events because the selected (independent) events have to be applied at one step. It, however, might be that case that one independent event is an enabler for another independent event (on the other hand, an independent event cannot be a disabler for another independent event) and thus it has to be indicated that an event will be enabled in the following step (by the wenab atom).
For each ei 2 E such that ej is a non-sole enabler for ei [f(enab-ei); (wenab-ei) j ej is a disabler for eig add (ej ) [ f(notsel-ej)g [ [f(disab-ei) j ej is a disabler for eig [ [f(wenab-ei) j ej is a sole enabler for eig (pre(ei) n add (ej ); fg; f(wenab-ei)g)
Resorting back to the \action" turn can be done after all the selected events (respectively their corresponding \event" actions) were applied. In other words, if no event is selected, then we can resort to the \action" turn while enabling events that were marked as \will be enabled". The \resorting" action ares 2 AF is de ned as follows:
For a planning problem P = (D; I; G), the corresponding FOND problem PF = (DF ; IF ; G) is constructed in such a way that IF = I [ f(act-turn)g[ f(enab-ei) j pre(ei) Ig [ f(disab-ei) j pre(ei) 6 Ig [ f(notsel-ei) j ei 2 Eg. pre(ares) del (ares) add (ares) ce i(ares)
f(ev-turn2); (notsel-e1); : : : ; (notsel-en)g f(ev-turn2)g (f(wenab-ei)g; f(wenab-ei),(disab-ei)g; f(enab-ei)g)
Similarly to the previous case, to solve the FOND planning problem we simulate action and event turns. The main di erence is that in this case more (independent) events can be selected in one turn. Therefore, the event turn is divided into three stages, event selection, event application and resorting to the action turn. On top of that, as events might enable other events, even one independent event can be an enabler of another independent event, to correctly simulate the event turn we have to postpone a possible enabling of events until the end of the turn. Technically speaking, the \event selecting" action selects a set of independent events that are all sequentially processed by \event" actions. The e ects of a selected event take place if the event is enabled, otherwise the event is skipped. However, as the event e ects might enable other events (even independent ones) it is important to postpone the information about newly enabled events until all the selected events were processed. The information about newly enabled events has to be kept (the wenab atoms) and when all the selected events are processed, the \resorting" action uses the information to determine enabled events for the next turn (the enab atoms).
Let F be a strong cyclic plan of PF , then a strong cyclic plan for a corresponding planning pro2b2leLmF aPndis aciFon2stAruFctseudchastfhoaltlows. Analogously to the previous case, for each sF F (sF ) = aiF we de ne (sF \ L) = ai. In plain words, we consider only pairs hstate,actioni from the strong cyclic plan associated with actions translated from actions de ned in P. Also the additional atoms de ned in PF have to be removed to obtain states of P. It can be observed that if a strong cyclic plan of PF is found there is no \open state" which is not a goal state. As events occur implicitly (as in Assumption 2), the corresponding strong cyclic plan of P has to consider only \action turns". The above is summarised in the following theorem.
Theorem 2. Let P be a planning problem (with events) and PF be its translation into a FOND problem (as described above). Then, F is a strong cyclic plan of PF if and only if (constructed from F as above) is a strong cyclic plan of P.
Proof (Sketch). Analogously to the proof sketch of Theorem 1, the \action" and \event" turns alternate and we keep track of which events are enabled or disabled. The di erence is that a set of independent events can occur at once in a single event turn. An \event selecting" action therefore selects a set of independent events. Selected events are processed in a sequence one by one (by \event" actions) such that event e ects take place if the event is enabled, otherwise the event is considered as \noop". However, as \event" actions are processed in sequence, e ects of one might enable an event that is going to be processed later. That would have deviated from Assumption 2 as such an event is inapplicable in the state before the set of independent events can occur. To prevent enabling events that are disabled in a given turn, we use the wenab atoms that conditionally enable events. Conditional enabling if persists becomes \real" at the end of the event turn. The \resorting" action, which switches from event to action turn, can be applied only if all selected events have been processed (i.e., all the events are \not selected"). On top of that, the \resorting" action makes all conditionally enabled events enabled. Noteworthy, the selecting action uses the (ev-turn) atom and achieves the (ev-turn2) atom for the resorting action such that they are applied in the correct order.
Disabling events cannot a ect those selected in the current event round because one of the properties for events being independent is that delete e ects of one event are disjoint with preconditions of other (independent) events. Also, disabling an event (even non-selected) is \permanent" for a given turn as the other property of independence guarantees that add e ects are disjoint with delete e ects among independent events. Hence any atom deleted by one event cannot be re-achieved by another independent event.
If a strong cyclic plan of PF is found there is no \open state" which is not a goal state. As events occur implicitly (as in Assumption 2), the corresponding strong cyclic plan of P has to consider only \action turns". 5
The aim of the experiments is to measure performance gap between a complete (o ine) FOND approach and the (online) PER approach for solving planning problems with non-deterministic events. Also, we would like to highlight how the success rate of the latter approach can drop in problems with dead-ends.
For our experimental evaluation, we speci ed the following problems. In BW, Problems 1,3,5 consider one sticky and one slippery hand, while Problems 2,4,6 two slippery hands only. Problems 1,2 have 5 blocks, 3,4 have 10 blocks and 5,6 have 15 blocks. For AUV, three resources are located in (or near) corners for each of the problems. Problems 1 and 2 are on 4x4 grid. Problem 1 has one ship that can move on 3th column and 3th row from 3th column to 4th column. Problem 2 has two ships moving \to the cross" (3th row and 3th column). Problems 3 and 4 are proportionally scaled to 8x8 grid. Problem 5 has three ships moving in adjacent columns (4th to 6th) such that the middle ship moves in the opposite direction than the other two. In Perestroika, Problems 1,2 are on the 3x3 grid while problems 3,4 are on 5x5 grid such that in Problems 1 and 3 solid platforms are on coordinates that are either both odd or both even. In Problems 2 and 4, shrinking platforms are on even rows and even columns. In Problems 1,2, resources are located in the other corners and for Problems 3,4 also in the middle of the grid. In Problem 5, resources are located on all solid platforms. In all problems, the agent starts in a corner. All problems are solvable, i.e., there exists a strong cyclic plan for each problem.
As a FOND planner, we used the PRP planner that also supports conditional
e ects [
The results summarised in Table 1 show that the PER approach can solve the problem in a few seconds in most cases, however, at the cost of lower success rate (especially for larger Perestroika problems considering Assumption 2). The FOND approach, on the other hand, can solve only the simpler problems, which is exacerbated for Assumption 2. The results, of course, are not very surprising given as the FOND approach is complete and has to consider all possibilities of event occurrence while the PER approach \takes a chance" by ignoring events in the planning stage, which is \risky" for problems with dead-ends (e.g. the agent might step on a small shrinking platform which due to an event might disappear and kill the agent).
To give an illustration why the FOND approach struggles to solve even rather toy problems, especially under the (more realistic) Assumption 2, let us see the Perestroika Problem 1 that has 4 shrinking platforms. It results, in consequence, in 16 sets of independent events (including noop) to be considered in every step (turn). Hence the number of \open states" can explode exponentially (with respect to the number of events). 6
Planning with non-deterministic events presents a challenge of nding strong
cyclic plans for agents in dynamic environments. In this paper, we present a
Scripts for compilation to FOND and benchmark problems are available at
https://github.com/martinpilat/events-FOND
compilation of planning problems with events into FOND planning problems.
We have experimentally shown that nding strong cyclic plans is viable, under
reasonable time and memory constraints, for very small problems. On the other
hand, the global reasoning for solving the problem might be unnecessarily
expensive (at least for some classes of problems). For example, in Perestroika, the
agent might need to reason only with shrinking platforms that are on the way
between solid platforms. Generally speaking, the agent might need to nd strong
cyclic plans between \safe" states [
In future, we plan to investigate how the problem can be decomposed such that we have to nd a sequence of local policies that can be combined into a strong cyclic plan.
Acknowledgements This Research was funded by the Czech Science Foundation (projects no. 17-17125Y and 18-07252S). 15. Richter, S., Westphal, M.: The LAMA planner: Guiding cost-based anytime planning with landmarks. Journal of Arti cial Intelligence Research (JAIR) 39, 127{ 177 (2010) 16. Vallati, M., Chrpa, L., Grzes, M., McCluskey, T.L., Roberts, M., Sanner, S.: The 2014 international planning competition: Progress and trends. AI Magazine 36(3), 90{98 (2015) 17. Yoon, S.W., Fern, A., Givan, R.: FF-Replan: A baseline for probabilistic planning.
In: ICAPS 2007. pp. 352{359 (2007)