This notebook will show how to solve PDDL problems in scikit-decide via the great Unified Planning framework and its third-party engines from the AIPlan4EU project. We will also demonstrate how to call scikit-decide solvers from Unified Planning, allowing for solving PDDL problems with simulation-based solvers embedded in scikit-decide.
Environment setup (package installation)¶
First we install scikit-decide.
import os
if not os.path.exists('install_skdecide.py'):
!wget https://raw.githubusercontent.com/fteicht/icaps24-skdecide-tutorial/main/notebooks/install_skdecide.py
from install_skdecide import install_skdecide
install_skdecide(using_nightly_version=True, force_reinstall=True)
Second, we import the packages that will be used in this notebook.
import os
import sys
import networkx as nx
from enum import Enum
import datetime
import folium
import unified_planning as up
from unified_planning.io import PDDLReader
from unified_planning.shortcuts import (
OneshotPlanner,
UserType,
IntType,
BoolType,
Fluent,
Problem,
InstantaneousAction,
SimulatedEffect,
Equals,
GE,
Not,
Or,
Int,
Object
)
from unified_planning.environment import get_environment
from skdecide.hub.domain.up import UPDomain
from skdecide.hub.solver.up import UPSolver
from skdecide.utils import rollout
from skdecide.hub.solver.iw import IW
from skdecide.hub.solver.ray_rllib import RayRLlib
from ray.rllib.algorithms.dqn import DQN
from skdecide.hub.domain.flight_planning.domain import (
FlightPlanningDomain,
WeatherDate
)
Solving PDDL problems via the scikit-decide bridge to Unified Planning solvers¶
For the purpose of demonstration, we show how to solve a simplistic blocksworld
instance with 4 blocks. Since we are relying on PDDL engines from Unified Planning (e.g. fast-downward
, ENHSP
, tamer
, etc.), you are free to try more challenging benchmarks!
if not os.path.exists('bw-domain.pddl'):
!wget https://raw.githubusercontent.com/potassco/pddl-instances/master/ipc-2000/domains/blocks-strips-typed/domain.pddl
!mv domain.pddl bw-domain.pddl
if not os.path.exists('bw-instance.pddl'):
!wget https://raw.githubusercontent.com/potassco/pddl-instances/master/ipc-2000/domains/blocks-strips-typed/instances/instance-1.pddl
!mv instance-1.pddl bw-instance.pddl
reader = PDDLReader()
up_problem = reader.parse_problem('bw-domain.pddl', 'bw-instance.pddl')
up_problem.add_quality_metric(
up.model.metrics.MinimizeSequentialPlanLength()
)
We now create a skdecide.hub.domain.UPDomain
which embeds a Unified Planning problem.
domain_factory = lambda: UPDomain(up_problem)
domain = domain_factory()
Once the UPDomain
is created, we can call the skdecide.hub.solver.UPSolver
which forward the solving process to a Unified Planning engine, then re-casting back the plan into the scikit-decide action format as defined in the skdecide.hub.domain.UPDomain
.
We are specifically calling here the fast-downward
engine, after what we execute the resulting plan by using skdecide.utils.rollout()
.
assert UPSolver.check_domain(domain)
with UPSolver(
domain_factory=domain_factory,
operation_mode=OneshotPlanner,
name="fast-downward",
engine_params={"output_stream": sys.stdout},
) as solver:
solver.solve()
rollout(
domain,
solver,
num_episodes=1,
max_steps=100,
max_framerate=30,
outcome_formatter=None,
)
2024-05-31 10:51:35,897 | skdecide.utils | DEBUG | Logger is in verbose mode: all debug messages will be there for you to enjoy (〜^∇^ )〜 2024-05-31 10:51:35,898 | skdecide.utils | DEBUG | Episode 1 started with following observation: 2024-05-31 10:51:35,898 | skdecide.utils | DEBUG | {clear(c): true, clear(a): true, clear(b): true, clear(d): true, ontable(c): true, ontable(a): true, ontable(b): true, ontable(d): true, handempty: true, on(d, d): false, on(b, d): false, on(a, d): false, on(c, d): false, on(d, b): false, on(b, b): false, on(a, b): false, on(c, b): false, on(d, a): false, on(b, a): false, on(a, a): false, on(c, a): false, on(d, c): false, on(b, c): false, on(a, c): false, on(c, c): false, holding(d): false, holding(b): false, holding(a): false, holding(c): false} 2024-05-31 10:51:35,899 | skdecide.utils | DEBUG | Action: pick-up(b)
NOTE: To disable printing of planning engine credits, add this line to your code: `up.shortcuts.get_environment().credits_stream = None` *** Credits *** * In operation mode `OneshotPlanner` at line 65 of `/Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/skdecide/hub/solver/up/up.py`, you are using the following planning engine: * Engine name: Fast Downward * Developers: Uni Basel team and contributors (cf. https://github.com/aibasel/downward/blob/main/README.md) * Description: Fast Downward is a domain-independent classical planning system. INFO planner time limit: None INFO planner memory limit: None INFO Running translator. INFO translator stdin: None INFO translator time limit: None INFO translator memory limit: None INFO translator command line string: /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/bin/python /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/up_fast_downward/downward/builds/release/bin/translate/translate.py /var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/tmpkjn20s4z/domain.pddl /var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/tmpkjn20s4z/problem.pddl --sas-file output.sas Parsing... Parsing: [0.000s CPU, 0.001s wall-clock] Normalizing task... [0.000s CPU, 0.000s wall-clock] Instantiating... Generating Datalog program... [0.000s CPU, 0.000s wall-clock] Normalizing Datalog program... Normalizing Datalog program: [0.010s CPU, 0.001s wall-clock] Preparing model... [0.000s CPU, 0.000s wall-clock] Generated 21 rules. Computing model... [0.000s CPU, 0.000s wall-clock] 82 relevant atoms 52 auxiliary atoms 134 final queue length 210 total queue pushes Completing instantiation... [0.000s CPU, 0.001s wall-clock] Instantiating: [0.010s CPU, 0.002s wall-clock] Computing fact groups... Finding invariants... 10 initial candidates Finding invariants: [0.000s CPU, 0.001s wall-clock] Checking invariant weight... [0.000s CPU, 0.000s wall-clock] Instantiating groups... [0.000s CPU, 0.000s wall-clock] Collecting mutex groups... [0.000s CPU, 0.000s wall-clock] Choosing groups... 5 uncovered facts Choosing groups: [0.000s CPU, 0.000s wall-clock] Building translation key... [0.000s CPU, 0.000s wall-clock] Computing fact groups: [0.000s CPU, 0.001s wall-clock] Building STRIPS to SAS dictionary... [0.000s CPU, 0.000s wall-clock] Building dictionary for full mutex groups... [0.000s CPU, 0.000s wall-clock] Building mutex information... Building mutex information: [0.000s CPU, 0.000s wall-clock] Translating task... Processing axioms... Simplifying axioms... [0.000s CPU, 0.000s wall-clock] Translator axioms removed by simplifying: 0 Computing negative axioms... [0.000s CPU, 0.000s wall-clock] Processing axioms: [0.000s CPU, 0.000s wall-clock] Translating task: [0.000s CPU, 0.001s wall-clock] 44 effect conditions simplified 0 implied preconditions added Detecting unreachable propositions... 0 operators removed 0 axioms removed 8 propositions removed Detecting unreachable propositions: [0.000s CPU, 0.000s wall-clock] Reordering and filtering variables... 9 of 9 variables necessary. 5 of 9 mutex groups necessary. 32 of 32 operators necessary. 0 of 0 axiom rules necessary. Reordering and filtering variables: [0.000s CPU, 0.000s wall-clock] Translator variables: 9 Translator derived variables: 0 Translator facts: 30 Translator goal facts: 3 Translator mutex groups: 5 Translator total mutex groups size: 25 Translator operators: 32 Translator axioms: 0 Translator task size: 295 warning: could not determine peak memory Writing output... [0.000s CPU, 0.000s wall-clock] Done! [0.010s CPU, 0.006s wall-clock] translate exit code: 0 INFO Running search (release). INFO search stdin: output.sas INFO search time limit: None INFO search memory limit: None INFO search command line string: /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/up_fast_downward/downward/builds/release/bin/downward --search 'let(hlm,landmark_sum(lm_factory=lm_reasonable_orders_hps(lm_rhw()),transform=adapt_costs(one),pref=false),let(hff,ff(transform=adapt_costs(one)),lazy_greedy([hff,hlm],preferred=[hff,hlm],cost_type=one,reopen_closed=false)))' --internal-plan-file /var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/tmpkjn20s4z/plan.txt < output.sas [t=0.00261583s, 33756068 KB] reading input... [t=0.00391304s, 33764260 KB] done reading input! [t=0.0157367s, 33764260 KB] Initializing landmark sum heuristic... [t=0.0157453s, 33764260 KB] Generating landmark graph... [t=0.015787s, 33764260 KB] Building a landmark graph with reasonable orders. [t=0.015823s, 33764260 KB] Initializing Exploration... [t=0.0160193s, 33764260 KB] Generating landmarks using the RPG/SAS+ approach [t=0.0162969s, 33764260 KB] Removed 0 reasonable or obedient reasonable orders [t=0.016312s, 33764260 KB] Landmarks generation time: 0.000521291s [t=0.0163156s, 33764260 KB] Discovered 14 landmarks, of which 0 are disjunctive and 0 are conjunctive. [t=0.0163189s, 33764260 KB] 18 edges [t=0.0163243s, 33764260 KB] approx. reasonable orders [t=0.0163805s, 33764260 KB] approx. obedient reasonable orders [t=0.0163885s, 33764260 KB] Removed 0 reasonable or obedient reasonable orders [t=0.0163927s, 33764260 KB] Landmarks generation time: 0.000644625s [t=0.0163953s, 33764260 KB] Discovered 14 landmarks, of which 0 are disjunctive and 0 are conjunctive. [t=0.0163987s, 33764260 KB] 24 edges [t=0.0164046s, 33764260 KB] Landmark graph generation time: 0.0006615s [t=0.0164082s, 33764260 KB] Landmark graph contains 14 landmarks, of which 0 are disjunctive and 0 are conjunctive. [t=0.0164119s, 33764260 KB] Landmark graph contains 24 orderings. [t=0.0165504s, 33764260 KB] Simplifying 120 unary operators... done! [96 unary operators] [t=0.0169249s, 33764260 KB] time to simplify: 0.000403958s [t=0.016939s, 33764260 KB] Initializing additive heuristic... [t=0.0169424s, 33764260 KB] Initializing FF heuristic... [t=0.0170629s, 33764324 KB] Building successor generator...done! [t=0.0170999s, 33764324 KB] peak memory difference for successor generator creation: 0 KB [t=0.0171033s, 33764324 KB] time for successor generation creation: 2.8125e-05s [t=0.0172411s, 33764324 KB] Variables: 9 [t=0.0172453s, 33764324 KB] FactPairs: 30 [t=0.0172477s, 33764324 KB] Bytes per state: 4 [t=0.0173905s, 33764324 KB] Conducting lazy best first search, (real) bound = 2147483647 [t=0.0174025s, 33764324 KB] 8 initial landmarks, 3 goal landmarks [t=0.017451s, 33764324 KB] New best heuristic value for landmark_sum(lm_factory=lm_reasonable_orders_hps(lm_rhw()),transform=adapt_costs(one),pref=false): 6 [t=0.0174555s, 33764324 KB] New best heuristic value for ff(transform=adapt_costs(one)): 6 [t=0.017458s, 33764324 KB] g=0, 1 evaluated, 0 expanded [t=0.0174725s, 33764324 KB] Initial heuristic value for landmark_sum(lm_factory=lm_reasonable_orders_hps(lm_rhw()),transform=adapt_costs(one),pref=false): 6 [t=0.0174759s, 33764324 KB] Initial heuristic value for ff(transform=adapt_costs(one)): 6 [t=0.0175269s, 33764324 KB] New best heuristic value for landmark_sum(lm_factory=lm_reasonable_orders_hps(lm_rhw()),transform=adapt_costs(one),pref=false): 4 [t=0.0175306s, 33764324 KB] New best heuristic value for ff(transform=adapt_costs(one)): 4 [t=0.017533s, 33764324 KB] g=2, 6 evaluated, 5 expanded [t=0.0175623s, 33764324 KB] New best heuristic value for ff(transform=adapt_costs(one)): 3 [t=0.0175659s, 33764324 KB] g=4, 9 evaluated, 8 expanded [t=0.0175764s, 33764324 KB] New best heuristic value for landmark_sum(lm_factory=lm_reasonable_orders_hps(lm_rhw()),transform=adapt_costs(one),pref=false): 2 [t=0.01758s, 33764324 KB] New best heuristic value for ff(transform=adapt_costs(one)): 2 [t=0.0175824s, 33764324 KB] g=4, 10 evaluated, 9 expanded [t=0.0175919s, 33764324 KB] New best heuristic value for landmark_sum(lm_factory=lm_reasonable_orders_hps(lm_rhw()),transform=adapt_costs(one),pref=false): 1 [t=0.0175949s, 33764324 KB] New best heuristic value for ff(transform=adapt_costs(one)): 1 [t=0.0175975s, 33764324 KB] g=5, 11 evaluated, 10 expanded [t=0.0176077s, 33764324 KB] Solution found! [t=0.0176127s, 33764324 KB] Actual search time: 0.000208666s pick_up b (1) stack b a (1) pick_up c (1) stack c b (1) pick_up d (1) stack d c (1) [t=0.0176157s, 33764324 KB] Plan length: 6 step(s). [t=0.0176157s, 33764324 KB] Plan cost: 6 [t=0.0176157s, 33764324 KB] Expanded 11 state(s). [t=0.0176157s, 33764324 KB] Reopened 0 state(s). [t=0.0176157s, 33764324 KB] Evaluated 12 state(s). [t=0.0176157s, 33764324 KB] Evaluations: 24 [t=0.0176157s, 33764324 KB] Generated 35 state(s). [t=0.0176157s, 33764324 KB] Dead ends: 0 state(s). [t=0.0176157s, 33764324 KB] Number of registered states: 12 [t=0.0176157s, 33764324 KB] Int hash set load factor: 12/16 = 0.75 [t=0.0176157s, 33764324 KB] Int hash set resizes: 4 [t=0.0176157s, 33764324 KB] Search time: 0.000225917s [t=0.0176157s, 33764324 KB] Total time: 0.0176157s Solution found. Peak memory: 33764324 KB Remove intermediate file output.sas search exit code: 0 INFO Planner time: 0.08s
2024-05-31 10:51:35,936 | skdecide.utils | DEBUG | Action: stack(b, a) 2024-05-31 10:51:35,971 | skdecide.utils | DEBUG | Action: pick-up(c) 2024-05-31 10:51:36,009 | skdecide.utils | DEBUG | Action: stack(c, b) 2024-05-31 10:51:36,045 | skdecide.utils | DEBUG | Action: pick-up(d) 2024-05-31 10:51:36,083 | skdecide.utils | DEBUG | Action: stack(d, c) 2024-05-31 10:51:36,084 | skdecide.utils | DEBUG | Episode 1 terminated after 7 steps. 2024-05-31 10:51:36,084 | skdecide.utils | INFO | The goal was reached in episode 1.
However, thanks to the unified API of scikit-decide, we can also call scikit-decide's native planners - which do not need to be specifically designed for PDDL problems! - which are compatible with the features of UPDomain
.
Looking more closely to UPDomain
's characteristics, we see that it inherits from DeterministicPlanningDomain
, which is itself a shortcut for the following features: Domain
, SingleAgent
, Sequential
, DeterministicTransitions
, Actions
, Goals
, DeterministicInitialized
, Markovian
, FullyObservable
, and PositiveCosts
.
Especially, scikit-decide's implementation of the Iterated Width planner is compatible with such characteristics. In order to be able to computey Iterated Width's novelty measures, we must provide the state features as vectors. In order to do so, we pass the parameter state_encoding='vector'
to the UPDomain
instance's constructor. The state feature vector used by Iterated Width will then just be the state vector itself.
domain_factory = lambda: UPDomain(up_problem, state_encoding='vector')
domain = domain_factory()
with IW(domain_factory=domain_factory,
state_features=lambda d, s: s,
node_ordering=lambda a_gscore, a_novelty, a_depth, b_gscore, b_novelty, b_depth: a_novelty > b_novelty
) as solver:
solver.solve()
rollout(
domain,
solver,
num_episodes=1,
max_steps=100,
max_framerate=30,
outcome_formatter=None,
)
2024-05-31 10:51:38,277 | skdecide.utils | DEBUG | Logger is in verbose mode: all debug messages will be there for you to enjoy (〜^∇^ )〜 2024-05-31 10:51:38,278 | skdecide.utils | DEBUG | Episode 1 started with following observation: 2024-05-31 10:51:38,278 | skdecide.utils | DEBUG | [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 2024-05-31 10:51:38,951 | skdecide.utils | DEBUG | Action: action pick-up_b { preconditions = [ clear(b) ontable(b) handempty ] effects = [ ontable(b) := false clear(b) := false handempty := false holding(b) := true ] }
[2024-05-31 10:51:37.587] [info] Running sequential IW solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:37.587] [info] Running sequential IW(1) solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:37.649] [info] IW(1) could not find a solution from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:37.649] [info] Running sequential IW(2) solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:37.813] [info] IW(2) could not find a solution from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:37.814] [info] Running sequential IW(3) solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:38.270] [info] Found a goal state: [0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0] (cost=6; best=6) [2024-05-31 10:51:38.270] [info] IW(3) finished to solve from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] in 0.456724 seconds. [2024-05-31 10:51:38.275] [info] IW finished to solve from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] in 0.000687 seconds. [2024-05-31 10:51:38.279] [info] Running sequential IW solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:38.279] [info] Running sequential IW(1) solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:38.314] [info] IW(1) could not find a solution from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:38.314] [info] Running sequential IW(2) solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:38.479] [info] IW(2) could not find a solution from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:38.480] [info] Running sequential IW(3) solver from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [2024-05-31 10:51:38.946] [info] Found a goal state: [0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0] (cost=6; best=6) [2024-05-31 10:51:38.946] [info] IW(3) finished to solve from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] in 0.466679 seconds. [2024-05-31 10:51:38.951] [info] IW finished to solve from state [1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] in 0.000672 seconds.
2024-05-31 10:51:38,953 | skdecide.utils | DEBUG | Action: action stack_b_a { preconditions = [ holding(b) clear(a) ] effects = [ holding(b) := false clear(a) := false clear(b) := true handempty := true on(b, a) := true ] } 2024-05-31 10:51:38,991 | skdecide.utils | DEBUG | Action: action pick-up_c { preconditions = [ clear(c) ontable(c) handempty ] effects = [ ontable(c) := false clear(c) := false handempty := false holding(c) := true ] } 2024-05-31 10:51:39,029 | skdecide.utils | DEBUG | Action: action stack_c_b { preconditions = [ holding(c) clear(b) ] effects = [ holding(c) := false clear(b) := false clear(c) := true handempty := true on(c, b) := true ] } 2024-05-31 10:51:39,067 | skdecide.utils | DEBUG | Action: action pick-up_d { preconditions = [ clear(d) ontable(d) handempty ] effects = [ ontable(d) := false clear(d) := false handempty := false holding(d) := true ] } 2024-05-31 10:51:39,104 | skdecide.utils | DEBUG | Action: action stack_d_c { preconditions = [ holding(d) clear(c) ] effects = [ holding(d) := false clear(c) := false clear(d) := true handempty := true on(d, c) := true ] } 2024-05-31 10:51:39,105 | skdecide.utils | DEBUG | Episode 1 terminated after 7 steps. 2024-05-31 10:51:39,105 | skdecide.utils | INFO | The goal was reached in episode 1.
Using scikit-decide solvers from Unified Planning¶
Scikit-decide provides a Unified Planning engine which converts a Unified Planning domain into a skdecide.hub.domain.UPDomain
, then forward the solving process to a compatible scikit-decide's solver.
First, we must retrieve the up-skdecide
code from AIPlan4EU's GitHub project.
!pip install git+https://github.com/aiplan4eu/up-skdecide.git
In the following, we define a robot moving problem with simulated action effects which are typically hard to be handled by PDDL solvers. Scikit-decide solvers like Reinforcement Learning ones or Iterated Width are not specific to PDDL logics, and are thus generally (much) less efficient than PDDL-specific solvers, but they can naturally handle simulated action effects.
In the example below, we simulate the battery discharge of the robot when it is moving, which is usually the result of complex underlying physics simulation that cannot be easily modeled in basic PDDL in real problems.
Location = UserType("Location")
robot_at = up.model.Fluent("robot_at", BoolType(), l=Location)
battery_charge = Fluent('battery_charge', IntType(0, 100))
connected = up.model.Fluent(
"connected", BoolType(), l_from=Location, l_to=Location
)
move = up.model.InstantaneousAction(
"move", l_from=Location, l_to=Location
)
l_from = move.parameter("l_from")
l_to = move.parameter("l_to")
move.add_precondition(connected(l_from, l_to))
move.add_precondition(robot_at(l_from))
move.add_precondition(GE(battery_charge(), 10))
move.add_effect(robot_at(l_from), False)
move.add_effect(robot_at(l_to), True)
def fun(problem, state, actual_params):
value = state.get_value(battery_charge()).constant_value()
return [Int(value - 10)]
move.set_simulated_effect(SimulatedEffect([battery_charge()], fun))
problem = up.model.Problem("robot")
problem.add_fluent(robot_at, default_initial_value=False)
problem.add_fluent(connected, default_initial_value=False)
problem.add_action(move)
NLOC = 10
locations = [up.model.Object("l%s" % i, Location) for i in range(NLOC)]
problem.add_objects(locations)
problem.set_initial_value(robot_at(locations[0]), True)
for i in range(NLOC - 1):
problem.set_initial_value(connected(locations[i], locations[i + 1]), True)
problem.set_initial_value(battery_charge(), 100)
problem.add_goal(robot_at(locations[-1]))
problem.add_quality_metric(
up.model.metrics.MinimizeActionCosts({move: 1})
)
Now we call scikit-decide's implementation of Iterated Width on this problem, using Unified Planning's engine calling process and standards. We pass the parameters to be given to skdecide.hub.solver.IW
, especially the state encoding required to compute the novelty measure, in the config
field of the params
dictionary of the OneshotPlanner
.
get_environment().factory.add_engine("skdecide", "up_skdecide.engine", "EngineImpl")
with OneshotPlanner(problem_kind=problem.kind,
name='skdecide',
params={
"solver": IW,
"config": {"state_encoding": 'vector', "state_features": lambda d, s: s},
},) as planner:
result = planner.solve(problem)
print("%s returned: %s" % (planner.name, result.plan))
*** Credits *** * In operation mode `OneshotPlanner` at line 3 of `/var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/ipykernel_42964/3575256087.py`, you are using the following planning engine: * Engine name: Scikit-decide * Developers: Airbus AI Research * Description: Scikit-decide is an AI framework for Reinforcement Learning, Automated Planning and Scheduling. [2024-05-31 11:02:46.856] [info] Running sequential IW solver from state [ 1 100 0 0 0 0 0 0 0 0 0] [2024-05-31 11:02:46.856] [info] Running sequential IW(1) solver from state [ 1 100 0 0 0 0 0 0 0 0 0] SkDecide returned: SequentialPlan: move_l0_l1 move_l1_l2 move_l2_l3 move_l3_l4 move_l4_l5 move_l5_l6 move_l6_l7 move_l7_l8 move_l8_l9 [2024-05-31 11:02:46.904] [info] Found a goal state: [ 0 10 0 0 0 0 0 0 0 0 1] (cost=9; best=9) [2024-05-31 11:02:46.904] [info] IW(1) finished to solve from state [ 1 100 0 0 0 0 0 0 0 0 0] in 0.0481272 seconds. [2024-05-31 11:02:46.904] [info] IW finished to solve from state [ 1 100 0 0 0 0 0 0 0 0 0] in 4.8e-05 seconds.
/Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/unified_planning/engines/mixins/oneshot_planner.py:76: UserWarning: We cannot establish whether SkDecide can solve this problem! warn(msg)
We show below that solving the same Unified Planning problem with RLlib's DQN algorithm comes to just change one line of code.
with OneshotPlanner(
problem_kind=problem.kind,
name="skdecide",
params={
"solver": RayRLlib,
"config": {"state_encoding": "vector", "action_encoding": "int", "algo_class": DQN, "train_iterations": 1},
},
) as planner:
result = planner.solve(problem)
print("%s returned: %s" % (planner.name, result.plan))
*** Credits *** * In operation mode `OneshotPlanner` at line 1 of `/var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/ipykernel_42964/2555211931.py`, you are using the following planning engine: * Engine name: Scikit-decide * Developers: Airbus AI Research * Description: Scikit-decide is an AI framework for Reinforcement Learning, Automated Planning and Scheduling.
2024-05-31 11:03:06,177 INFO worker.py:1749 -- Started a local Ray instance. /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/ray/rllib/algorithms/algorithm.py:521: RayDeprecationWarning: This API is deprecated and may be removed in future Ray releases. You could suppress this warning by setting env variable PYTHONWARNINGS="ignore::DeprecationWarning" `UnifiedLogger` will be removed in Ray 2.7. return UnifiedLogger(config, logdir, loggers=None) /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/ray/tune/logger/unified.py:53: RayDeprecationWarning: This API is deprecated and may be removed in future Ray releases. You could suppress this warning by setting env variable PYTHONWARNINGS="ignore::DeprecationWarning" The `JsonLogger interface is deprecated in favor of the `ray.tune.json.JsonLoggerCallback` interface and will be removed in Ray 2.7. self._loggers.append(cls(self.config, self.logdir, self.trial)) /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/ray/tune/logger/unified.py:53: RayDeprecationWarning: This API is deprecated and may be removed in future Ray releases. You could suppress this warning by setting env variable PYTHONWARNINGS="ignore::DeprecationWarning" The `CSVLogger interface is deprecated in favor of the `ray.tune.csv.CSVLoggerCallback` interface and will be removed in Ray 2.7. self._loggers.append(cls(self.config, self.logdir, self.trial)) /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/ray/tune/logger/unified.py:53: RayDeprecationWarning: This API is deprecated and may be removed in future Ray releases. You could suppress this warning by setting env variable PYTHONWARNINGS="ignore::DeprecationWarning" The `TBXLogger interface is deprecated in favor of the `ray.tune.tensorboardx.TBXLoggerCallback` interface and will be removed in Ray 2.7. self._loggers.append(cls(self.config, self.logdir, self.trial)) 2024-05-31 11:03:12,782 WARNING deprecation.py:50 -- DeprecationWarning: `WorkerSet(num_workers=... OR local_worker=...)` has been deprecated. Use `EnvRunnerGroup(num_env_runners=... AND local_env_runner=...)` instead. This will raise an error in the future! 2024-05-31 11:03:12,783 WARNING deprecation.py:50 -- DeprecationWarning: `max_num_worker_restarts` has been deprecated. Use `AlgorithmConfig.max_num_env_runner_restarts` instead. This will raise an error in the future! 2024-05-31 11:03:12,824 WARNING catalog.py:740 -- Custom ModelV2 should accept all custom options as **kwargs, instead of expecting them in config['custom_model_config']! 2024-05-31 11:03:12,827 WARNING catalog.py:740 -- Custom ModelV2 should accept all custom options as **kwargs, instead of expecting them in config['custom_model_config']! 2024-05-31 11:03:13,330 WARNING util.py:61 -- Install gputil for GPU system monitoring.
SkDecide returned: SequentialPlan: move_l0_l1 move_l1_l2 move_l2_l3 move_l3_l4 move_l4_l5 move_l5_l6 move_l6_l7 move_l7_l8 move_l8_l9
Solving a flight planning problem modeled in numeric PDDL¶
Our final experiment with PDDL planning in scikit-decide consists in solving a simplified planning problem over a waypoint graph and wind drift.
We first install the folium package which brings nice graph rendering over Earth maps.
!pip install folium
We then import map plotting and cost computation functions from the flight planning utils script.
if not os.path.exists('flight_planning_utils.py'):
!wget https://raw.githubusercontent.com/fteicht/icaps24-skdecide-tutorial/main/notebooks/flight_planning_utils.py
from flight_planning_utils import (
H_Action,
V_Action,
plot_map,
cost
)
Computing the transition cost between 2 waypoints, which represents the flown distance in the air mass, requires to do some trigonometric maths in the Earth spherical coordinate system and its projection on the tangential plane of the aircraft as depicted in the following image:
It begins with the computtion of the coordinates of the direction vector, i.e. the vector linking two successive waypoints, by using trigonometric formulas in the Earth sphere.
We note:
- $\mathbf{W}$ the wind speed vector
- $\mathbf{V}$ the true aircraft speed vector in the air
- $\mathbf{D}$ the direction vector (obtained with the trigonometric formulas above)
- $\mathbf{U}$ the projected speed of the aircraft on the direction vector
- $\mathbf{u}=\frac{\mathbf{U}}{\Vert \mathbf{U} \Vert} = \frac{\mathbf{D}}{\Vert \mathbf{D} \Vert}$ the unitary direction vector
We known $\mathbf{D}$, $\mathbf{W}$ and $\mathbf{\Vert \mathbf{V} \Vert}$, but we don't known $\mathbf{V}$.
We have: $\mathbf{V} = \mathbf{U} - \mathbf{W}$
Thus: $\Vert \mathbf{V} \Vert^2 = \Vert \mathbf{U} \Vert \; \mathbf{u} \cdot \mathbf{V} - \mathbf{W} \cdot \mathbf{V}$
But also: $\mathbf{V} \cdot \mathbf{u} = \Vert \mathbf{U} \Vert - \mathbf{W} \cdot {u}$
As well as: $\mathbf{V} \cdot \mathbf{W} = \Vert \mathbf{U} \Vert \; \mathbf{u} \cdot \mathbf{W} - \Vert \mathbf{W} \Vert^2$
Therefore: $\Vert \mathbf{U} \Vert^2 - 2 \; \mathbf{u} \cdot \mathbf{W} \; \Vert \mathbf{U} \Vert + \Vert \mathbf{W} \Vert^2 - \Vert \mathbf{V} \Vert^2 = 0$
Finally: $\Vert \mathbf{U} \Vert = \mathbf{W} \cdot \mathbf{u} + \sqrt{(\mathbf{W} \cdot \mathbf{u})^2 + \Vert \mathbf{V} \Vert^2 - \Vert \mathbf{W} \Vert^2}$
Now, if we note $t$ the flying time between the 2 successive waypoints, we can compute the flown distance in the air, i.e. in the direction of $\mathbf{V}$ as: $\Vert \mathbf{V} \Vert \times t = \Vert \mathbf{V} \Vert \times \frac{\Vert \mathbf{D} \Vert}{\Vert \mathbf{U} \Vert} = \frac{\Vert \mathbf{V} \Vert}{\Vert \mathbf{U} \Vert} \Vert \mathbf{D} \Vert$
With headwind, the flown distance will be greater than the direct distance. With tailwind, it is the contrary.
This is exactly what the imported cost
function computes.
We are now ready to model the flight planning numeric problem.
This problem (in this simplified version) is a classical planning problem with floating-point action costs.
We could solve it with the ENHSP planner, which would yet require to install java. For simplicity reasons, we will thus make later on in the problem instance all the floating-point costs rounded to their 3rd digit then scale by 1e3 to make them all integers. Doing so, the problem is now solvable by the fast-downward-opt
Unified Planning engine. Therefore, we can define the type of the Cost
fluent to be IntType
.
problem = Problem("flight_planning")
#Objects
waypoint = UserType("waypoint")
#Fluents
Cost = Fluent('COST', IntType(), l_from=waypoint, l_to= waypoint)
Connected = Fluent('CONNECTED', BoolType(), l_from=waypoint, l_to= waypoint)
at = Fluent('at', BoolType(), w=waypoint)
problem.add_fluent(Cost,default_initial_value=1000000)
problem.add_fluent(Connected,default_initial_value=False)
problem.add_fluent(at,default_initial_value=False)
#Actions
GoTo = InstantaneousAction("goto", fromwp = waypoint, towp=waypoint)
fromwp = GoTo.parameter('fromwp')
towp = GoTo.parameter('towp')
GoTo.add_precondition(Connected(fromwp,towp))
GoTo.add_precondition(at(fromwp))
GoTo.add_effect(at(towp),True)
GoTo.add_effect(at(fromwp),False)
problem.add_action(GoTo)
problem.add_quality_metric(
up.model.metrics.MinimizeActionCosts({GoTo:Cost(fromwp,towp)})
)
To create the actual flight planning problem instance, we will leverage the skdecide.hub.domain.flight_planning.FlightPlanningDomain
. This domain is much more realistic - but also ways more complex ! - than our simplified PDDL domain: it uses the aircraft performance model to compute the real fuel consumption of the aircraft based on its speed, altitude and mass at each waypoint in the graph. Even if we won't solve this more realistic domain (we are in a PDDL tutorial notebook!), we will still use its capability to extract the waypoint graph and actual weather of the current date (yes, today's weather data!).
origin = "LFPG"
destination = "LFLL"
aircraft = "A320"
today = datetime.date.today()
month = 1 // 4 * 4 + 1 # will result in january, may, or september
year = today.year
day = 1
weather_date = WeatherDate(day=day, month=month, year=year)
heuristic = "lazy_fuel"
cost_function = "fuel"
realistic_fp_domain = FlightPlanningDomain(
origin,
destination,
aircraft,
weather_date=weather_date,
heuristic_name=heuristic,
objective=cost_function,
fuel_loop=False,
graph_width="large",
)
L = list()
x=0
y=0
z=0
for x1 in realistic_fp_domain.network:
for x2 in x1:
for x3 in range(1):
L.append((x,y,z))
z+=1
z=0
y+=1
y=0
x+=1
G = nx.Graph()
for point in L:
G.add_node(point)
for i in range(len(L)):
x1, y1, z = L[i]
for j in range(len(L)):
x2, y2, z = L[j]
if (x2 == x1 + 1) and ( (y2 == y1-1) or (y2 == y1) or (y2 == y1+1) ):
G.add_edge(L[i], L[j])
locations = {str(l) : Object(str(l),waypoint) for l in G.nodes}
problem.add_objects(locations.values())
DEST = str((40, 10, 0))
problem.set_initial_value(at(locations[str((0,0,0))]),True)
problem.set_initial_value(at(locations[str((0,1,0))]),True)
problem.set_initial_value(at(locations[str((0,2,0))]),True)
problem.set_initial_value(at(locations[str((0,3,0))]),True)
problem.set_initial_value(at(locations[str((0,4,0))]),True)
problem.set_initial_value(at(locations[str((0,5,0))]),True)
problem.set_initial_value(at(locations[str((0,6,0))]),True)
problem.set_initial_value(at(locations[str((0,7,0))]),True)
problem.set_initial_value(at(locations[str((0,8,0))]),True)
problem.set_initial_value(at(locations[str((0,9,0))]),True)
problem.set_initial_value(at(locations[str((0,10,0))]),True)
problem.add_goal(Or(at(locations[str((40, 0, 0))]),
at(locations[str((40, 1, 0))]),
at(locations[str((40, 2, 0))]),
at(locations[str((40, 3, 0))]),
at(locations[str((40, 4, 0))]),
at(locations[str((40, 5, 0))]),
at(locations[str((40, 6, 0))]),
at(locations[str((40, 7, 0))]),
at(locations[str((40, 8, 0))]),
at(locations[str((40, 9, 0))]),
at(locations[str((40, 10, 0))]) ))
for (f,t) in G.edges:
problem.set_initial_value(Connected(locations[str(f)],locations[str(t)]), True)
c = cost(realistic_fp_domain,f,t)
problem.set_initial_value(Cost(locations[str(f)],locations[str(t)]), int(round(c, ndigits=3)*1e3))
We can now solve the flight planning problem by defining the UPDomain
embedding our flight planning Unified Planning problem, and calling the fast-downward-opt
engine from the UPSolver
.
domain_factory = lambda: UPDomain(problem)
with UPSolver(
domain_factory=domain_factory,
operation_mode=OneshotPlanner,
name="fast-downward-opt",
engine_params={"output_stream": sys.stdout},
) as solver:
print('Solving the problem...')
solver.solve()
print('Extracting plan...')
plan = solver.get_plan()
fr = []
to = []
actions = []
for ai in plan:
fr.append( tuple(int(i) for i in str(ai.up_parameters[0]).strip('(').strip(')').split(',')))
to.append( tuple( int(i) for i in str(ai.up_parameters[1]).strip('(').strip(')').split(',')))
for t in range(len(fr)):
if to[t][1] == fr[t][1] -1:
a1 = H_Action.down
if to[t][1] == fr[t][1]:
a1 = H_Action.straight
if to[t][1] == fr[t][1] +1:
a1 = H_Action.up
if to[t][2] == fr[t][2] -1:
a2 = V_Action.descent
if to[t][2] == fr[t][2]:
a2 = V_Action.cruise
if to[t][2] == fr[t][2] +1:
a2 = V_Action.climb
actions.append((a1, a2))
plot_map(to, G, realistic_fp_domain)
Solving the problem... *** Credits *** * In operation mode `OneshotPlanner` at line 65 of `/Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/skdecide/hub/solver/up/up.py`, you are using the following planning engine: * Engine name: Fast Downward * Developers: Uni Basel team and contributors (cf. https://github.com/aibasel/downward/blob/main/README.md) * Description: Fast Downward is a domain-independent classical planning system. INFO planner time limit: None INFO planner memory limit: None INFO Running translator. INFO translator stdin: None INFO translator time limit: None INFO translator memory limit: None INFO translator command line string: /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/bin/python /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/up_fast_downward/downward/builds/release/bin/translate/translate.py /var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/tmp74ssrao7/domain.pddl /var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/tmp74ssrao7/problem.pddl --sas-file output.sas Parsing... Parsing: [2.470s CPU, 2.479s wall-clock] Normalizing task... [0.010s CPU, 0.020s wall-clock] Instantiating... Generating Datalog program... [0.050s CPU, 0.050s wall-clock] Normalizing Datalog program... Normalizing Datalog program: [0.000s CPU, 0.002s wall-clock] Preparing model... [0.010s CPU, 0.007s wall-clock] Generated 27 rules. Computing model... [0.010s CPU, 0.014s wall-clock] 4297 relevant atoms 1691 auxiliary atoms 5988 final queue length 6798 total queue pushes Completing instantiation... [0.090s CPU, 0.083s wall-clock] Instantiating: [0.160s CPU, 0.157s wall-clock] Computing fact groups... Finding invariants... 3 initial candidates Finding invariants: [0.000s CPU, 0.000s wall-clock] Checking invariant weight... [0.010s CPU, 0.017s wall-clock] Instantiating groups... [0.000s CPU, 0.000s wall-clock] Collecting mutex groups... [0.000s CPU, 0.000s wall-clock] Choosing groups... 452 uncovered facts Choosing groups: [0.000s CPU, 0.000s wall-clock] Building translation key... [0.000s CPU, 0.001s wall-clock] Computing fact groups: [0.010s CPU, 0.019s wall-clock] Building STRIPS to SAS dictionary... [0.010s CPU, 0.000s wall-clock] Building dictionary for full mutex groups... [0.000s CPU, 0.000s wall-clock] Building mutex information... Building mutex information: [0.000s CPU, 0.000s wall-clock] Translating task... Processing axioms... Simplifying axioms... [0.000s CPU, 0.000s wall-clock] Translator axioms removed by simplifying: 0 Computing negative axioms... [0.000s CPU, 0.000s wall-clock] Processing axioms: [0.000s CPU, 0.001s wall-clock] Translating task: [0.030s CPU, 0.035s wall-clock] 1240 effect conditions simplified 0 implied preconditions added Detecting unreachable propositions... 0 operators removed 0 axioms removed 0 propositions removed Detecting unreachable propositions: [0.010s CPU, 0.010s wall-clock] Reordering and filtering variables... 452 of 452 variables necessary. 0 of 0 mutex groups necessary. 1251 of 1251 operators necessary. 0 of 0 axiom rules necessary. Reordering and filtering variables: [0.000s CPU, 0.005s wall-clock] Translator variables: 452 Translator derived variables: 0 Translator facts: 904 Translator goal facts: 1 Translator mutex groups: 0 Translator total mutex groups size: 0 Translator operators: 1251 Translator axioms: 0 Translator task size: 6350 warning: could not determine peak memory Writing output... [0.000s CPU, 0.007s wall-clock] Done! [2.710s CPU, 2.733s wall-clock] translate exit code: 0 INFO Running search (release). INFO search stdin: output.sas INFO search time limit: None INFO search memory limit: None INFO search command line string: /Users/teichteil_fl/Projects/SkDecide/skdecide-icaps24-tutorial/.env/lib/python3.10/site-packages/up_fast_downward/downward/builds/release/bin/downward --search 'astar(lmcut())' --internal-plan-file /var/folders/nh/hzyt86t51fxcj7rdyzbqhf280000gn/T/tmp74ssrao7/plan.txt < output.sas [t=0.00273237s, 33747876 KB] reading input... [t=0.0323017s, 33878948 KB] done reading input! [t=0.0362185s, 34018212 KB] Initializing landmark cut heuristic... [t=0.0362927s, 34018212 KB] Building successor generator...done! [t=0.0368138s, 34018212 KB] peak memory difference for successor generator creation: 0 KB [t=0.03682s, 34018212 KB] time for successor generation creation: 0.000492208s [t=0.0368339s, 34018212 KB] Variables: 452 [t=0.0368406s, 34018212 KB] FactPairs: 904 [t=0.0368441s, 34018212 KB] Bytes per state: 60 [t=0.0368705s, 34018212 KB] Conducting best first search with reopening closed nodes, (real) bound = 2147483647 [t=0.0495739s, 34018212 KB] New best heuristic value for lmcut(): 218889 [t=0.0495857s, 34018212 KB] g=0, 1 evaluated, 0 expanded [t=0.0497824s, 34018212 KB] f = 218889, 1 evaluated, 0 expanded [t=0.0497982s, 34018212 KB] Initial heuristic value for lmcut(): 218889 [t=0.0498039s, 34018212 KB] pruning method: none [t=0.0628993s, 34027428 KB] New best heuristic value for lmcut(): 213947 [t=0.0629275s, 34027428 KB] g=5765, 2 evaluated, 1 expanded [t=0.0756547s, 34027428 KB] New best heuristic value for lmcut(): 213556 [t=0.0756725s, 34027428 KB] g=5571, 3 evaluated, 1 expanded [t=0.100975s, 34027428 KB] New best heuristic value for lmcut(): 213477 [t=0.100993s, 34027428 KB] g=5508, 5 evaluated, 1 expanded [t=0.138245s, 34027428 KB] New best heuristic value for lmcut(): 213446 [t=0.138257s, 34027428 KB] g=5468, 8 evaluated, 1 expanded [t=0.175551s, 34035620 KB] New best heuristic value for lmcut(): 213438 [t=0.175565s, 34035620 KB] g=5451, 11 evaluated, 1 expanded [t=0.633235s, 34044836 KB] New best heuristic value for lmcut(): 208047 [t=0.633269s, 34044836 KB] g=10938, 48 evaluated, 2 expanded [t=0.644996s, 34044836 KB] New best heuristic value for lmcut(): 207990 [t=0.645012s, 34044836 KB] g=10899, 49 evaluated, 2 expanded [t=1.03576s, 34044836 KB] New best heuristic value for lmcut(): 202665 [t=1.03578s, 34044836 KB] g=16438, 82 evaluated, 3 expanded [t=1.0469s, 34044836 KB] New best heuristic value for lmcut(): 202545 [t=1.04691s, 34044836 KB] g=16344, 83 evaluated, 3 expanded [t=1.4218s, 34054052 KB] New best heuristic value for lmcut(): 197308 [t=1.42184s, 34054052 KB] g=21958, 116 evaluated, 4 expanded [t=1.43249s, 34054052 KB] New best heuristic value for lmcut(): 197101 [t=1.43249s, 34054052 KB] g=21788, 117 evaluated, 4 expanded [t=1.791s, 34054052 KB] New best heuristic value for lmcut(): 191973 [t=1.79104s, 34054052 KB] g=27500, 150 evaluated, 5 expanded [t=1.80137s, 34054052 KB] New best heuristic value for lmcut(): 191658 [t=1.80139s, 34054052 KB] g=27231, 151 evaluated, 5 expanded [t=2.15868s, 34054052 KB] New best heuristic value for lmcut(): 186603 [t=2.15872s, 34054052 KB] g=33062, 185 evaluated, 6 expanded [t=2.16869s, 34054052 KB] New best heuristic value for lmcut(): 186214 [t=2.16871s, 34054052 KB] g=32675, 186 evaluated, 6 expanded [t=2.46588s, 34054052 KB] New best heuristic value for lmcut(): 181151 [t=2.46591s, 34054052 KB] g=38646, 216 evaluated, 7 expanded [t=2.4753s, 34054052 KB] New best heuristic value for lmcut(): 180769 [t=2.47532s, 34054052 KB] g=38120, 217 evaluated, 7 expanded [t=2.76134s, 34054052 KB] New best heuristic value for lmcut(): 175697 [t=2.76137s, 34054052 KB] g=44248, 247 evaluated, 8 expanded [t=2.77041s, 34054052 KB] New best heuristic value for lmcut(): 175323 [t=2.77044s, 34054052 KB] g=43566, 248 evaluated, 8 expanded [t=3.04392s, 34054052 KB] New best heuristic value for lmcut(): 170243 [t=3.04395s, 34054052 KB] g=49867, 278 evaluated, 9 expanded [t=3.05278s, 34054052 KB] New best heuristic value for lmcut(): 169876 [t=3.05279s, 34054052 KB] g=49013, 279 evaluated, 9 expanded [t=3.31404s, 34054052 KB] New best heuristic value for lmcut(): 164788 [t=3.31407s, 34054052 KB] g=55503, 309 evaluated, 10 expanded [t=3.32241s, 34054052 KB] New best heuristic value for lmcut(): 164429 [t=3.32244s, 34054052 KB] g=54460, 310 evaluated, 10 expanded [t=3.56733s, 34054052 KB] New best heuristic value for lmcut(): 159333 [t=3.56736s, 34054052 KB] g=61154, 340 evaluated, 11 expanded [t=3.57519s, 34054052 KB] New best heuristic value for lmcut(): 158981 [t=3.5752s, 34054052 KB] g=59908, 341 evaluated, 11 expanded [t=3.80553s, 34054052 KB] New best heuristic value for lmcut(): 153877 [t=3.80556s, 34054052 KB] g=66818, 371 evaluated, 12 expanded [t=3.81287s, 34054052 KB] New best heuristic value for lmcut(): 153533 [t=3.81288s, 34054052 KB] g=65356, 372 evaluated, 12 expanded [t=4.03108s, 34054052 KB] New best heuristic value for lmcut(): 148420 [t=4.03111s, 34054052 KB] g=72495, 402 evaluated, 13 expanded [t=4.03819s, 34054052 KB] New best heuristic value for lmcut(): 148084 [t=4.03821s, 34054052 KB] g=70805, 403 evaluated, 13 expanded [t=4.24579s, 34054052 KB] New best heuristic value for lmcut(): 142962 [t=4.24581s, 34054052 KB] g=78181, 433 evaluated, 14 expanded [t=4.25304s, 34054052 KB] New best heuristic value for lmcut(): 142635 [t=4.25305s, 34054052 KB] g=76254, 434 evaluated, 14 expanded [t=4.44729s, 34054052 KB] New best heuristic value for lmcut(): 137506 [t=4.44732s, 34054052 KB] g=83876, 464 evaluated, 15 expanded [t=4.45338s, 34054052 KB] New best heuristic value for lmcut(): 137395 [t=4.4534s, 34054052 KB] g=81494, 465 evaluated, 15 expanded [t=4.63763s, 34054052 KB] New best heuristic value for lmcut(): 132052 [t=4.63765s, 34054052 KB] g=89516, 495 evaluated, 16 expanded [t=4.64907s, 34054052 KB] New best heuristic value for lmcut(): 131998 [t=4.64908s, 34054052 KB] g=89657, 497 evaluated, 16 expanded [t=4.81782s, 34054052 KB] New best heuristic value for lmcut(): 126598 [t=4.81786s, 34054052 KB] g=95155, 526 evaluated, 17 expanded [t=4.82319s, 34054052 KB] New best heuristic value for lmcut(): 126289 [t=4.82321s, 34054052 KB] g=92600, 527 evaluated, 17 expanded [t=5.04218s, 34090916 KB] New best heuristic value for lmcut(): 121144 [t=5.04223s, 34090916 KB] g=101008, 557 evaluated, 18 expanded [t=5.05185s, 34090916 KB] New best heuristic value for lmcut(): 120842 [t=5.05189s, 34090916 KB] g=98047, 558 evaluated, 18 expanded [t=5.26191s, 34090916 KB] New best heuristic value for lmcut(): 115689 [t=5.26195s, 34090916 KB] g=106729, 588 evaluated, 19 expanded [t=5.26665s, 34090916 KB] New best heuristic value for lmcut(): 115394 [t=5.26668s, 34090916 KB] g=103495, 589 evaluated, 19 expanded [t=5.40509s, 34090916 KB] New best heuristic value for lmcut(): 110232 [t=5.40512s, 34090916 KB] g=112464, 619 evaluated, 20 expanded [t=5.40941s, 34090916 KB] New best heuristic value for lmcut(): 109942 [t=5.40942s, 34090916 KB] g=108947, 620 evaluated, 20 expanded [t=5.538s, 34090916 KB] New best heuristic value for lmcut(): 104759 [t=5.53802s, 34090916 KB] g=117645, 650 evaluated, 21 expanded [t=5.54205s, 34090916 KB] New best heuristic value for lmcut(): 104483 [t=5.54206s, 34090916 KB] g=114406, 651 evaluated, 21 expanded [t=5.66142s, 34090916 KB] New best heuristic value for lmcut(): 99278 [t=5.66144s, 34090916 KB] g=122840, 681 evaluated, 22 expanded [t=5.66519s, 34090916 KB] New best heuristic value for lmcut(): 99018 [t=5.6652s, 34090916 KB] g=119871, 682 evaluated, 22 expanded [t=5.77613s, 34090916 KB] New best heuristic value for lmcut(): 93791 [t=5.77616s, 34090916 KB] g=128046, 712 evaluated, 23 expanded [t=5.7796s, 34090916 KB] New best heuristic value for lmcut(): 93547 [t=5.7796s, 34090916 KB] g=125342, 713 evaluated, 23 expanded [t=5.88224s, 34090916 KB] New best heuristic value for lmcut(): 88298 [t=5.88225s, 34090916 KB] g=133266, 743 evaluated, 24 expanded [t=5.88539s, 34090916 KB] New best heuristic value for lmcut(): 88069 [t=5.88539s, 34090916 KB] g=130820, 744 evaluated, 24 expanded [t=5.97928s, 34090916 KB] New best heuristic value for lmcut(): 82800 [t=5.97929s, 34090916 KB] g=138498, 774 evaluated, 25 expanded [t=5.98219s, 34090916 KB] New best heuristic value for lmcut(): 82585 [t=5.98219s, 34090916 KB] g=136304, 775 evaluated, 25 expanded [t=6.06946s, 34090916 KB] New best heuristic value for lmcut(): 77297 [t=6.06948s, 34090916 KB] g=143741, 805 evaluated, 26 expanded [t=6.07217s, 34090916 KB] New best heuristic value for lmcut(): 77097 [t=6.07218s, 34090916 KB] g=141792, 806 evaluated, 26 expanded [t=6.15034s, 34090916 KB] New best heuristic value for lmcut(): 71794 [t=6.15037s, 34090916 KB] g=148992, 836 evaluated, 27 expanded [t=6.15285s, 34090916 KB] New best heuristic value for lmcut(): 71609 [t=6.15287s, 34090916 KB] g=147280, 837 evaluated, 27 expanded [t=6.22412s, 34090916 KB] New best heuristic value for lmcut(): 66291 [t=6.22415s, 34090916 KB] g=154253, 867 evaluated, 28 expanded [t=6.22627s, 34090916 KB] New best heuristic value for lmcut(): 66121 [t=6.22628s, 34090916 KB] g=152768, 868 evaluated, 28 expanded [t=6.29054s, 34090916 KB] New best heuristic value for lmcut(): 60787 [t=6.29056s, 34090916 KB] g=159526, 898 evaluated, 29 expanded [t=6.29244s, 34090916 KB] New best heuristic value for lmcut(): 60632 [t=6.29245s, 34090916 KB] g=158257, 899 evaluated, 29 expanded [t=6.34897s, 34090916 KB] New best heuristic value for lmcut(): 55284 [t=6.34899s, 34090916 KB] g=164813, 929 evaluated, 30 expanded [t=6.35066s, 34090916 KB] New best heuristic value for lmcut(): 55143 [t=6.35066s, 34090916 KB] g=163746, 930 evaluated, 30 expanded [t=6.40015s, 34090916 KB] New best heuristic value for lmcut(): 49785 [t=6.40016s, 34090916 KB] g=170114, 960 evaluated, 31 expanded [t=6.40162s, 34090916 KB] New best heuristic value for lmcut(): 49653 [t=6.40162s, 34090916 KB] g=169236, 961 evaluated, 31 expanded [t=6.44488s, 34090916 KB] New best heuristic value for lmcut(): 44286 [t=6.4449s, 34090916 KB] g=175431, 991 evaluated, 32 expanded [t=6.44622s, 34090916 KB] New best heuristic value for lmcut(): 44165 [t=6.44624s, 34090916 KB] g=174724, 992 evaluated, 32 expanded [t=6.48403s, 34090916 KB] New best heuristic value for lmcut(): 38783 [t=6.48405s, 34090916 KB] g=180766, 1022 evaluated, 33 expanded [t=6.48511s, 34090916 KB] New best heuristic value for lmcut(): 38677 [t=6.48512s, 34090916 KB] g=180212, 1023 evaluated, 33 expanded [t=6.51692s, 34090916 KB] New best heuristic value for lmcut(): 33273 [t=6.51693s, 34090916 KB] g=186122, 1053 evaluated, 34 expanded [t=6.51781s, 34090916 KB] New best heuristic value for lmcut(): 33183 [t=6.51782s, 34090916 KB] g=185706, 1054 evaluated, 34 expanded [t=6.5439s, 34090916 KB] New best heuristic value for lmcut(): 27752 [t=6.54392s, 34090916 KB] g=191505, 1084 evaluated, 35 expanded [t=6.54463s, 34090916 KB] New best heuristic value for lmcut(): 27679 [t=6.54464s, 34090916 KB] g=191210, 1085 evaluated, 35 expanded [t=6.5653s, 34090916 KB] New best heuristic value for lmcut(): 22218 [t=6.56531s, 34090916 KB] g=196919, 1115 evaluated, 36 expanded [t=6.56584s, 34090916 KB] New best heuristic value for lmcut(): 22162 [t=6.56585s, 34090916 KB] g=196727, 1116 evaluated, 36 expanded [t=6.58116s, 34090916 KB] New best heuristic value for lmcut(): 16672 [t=6.58117s, 34090916 KB] g=202366, 1146 evaluated, 37 expanded [t=6.58153s, 34090916 KB] New best heuristic value for lmcut(): 16631 [t=6.58154s, 34090916 KB] g=202258, 1147 evaluated, 37 expanded [t=6.5922s, 34090916 KB] New best heuristic value for lmcut(): 11115 [t=6.59221s, 34090916 KB] g=207848, 1177 evaluated, 38 expanded [t=6.59241s, 34090916 KB] New best heuristic value for lmcut(): 11089 [t=6.59241s, 34090916 KB] g=207800, 1178 evaluated, 38 expanded [t=6.59855s, 34090916 KB] New best heuristic value for lmcut(): 5556 [t=6.59856s, 34090916 KB] g=213357, 1208 evaluated, 39 expanded [t=6.59866s, 34090916 KB] New best heuristic value for lmcut(): 5544 [t=6.59867s, 34090916 KB] g=213345, 1209 evaluated, 39 expanded [t=6.60172s, 34090916 KB] New best heuristic value for lmcut(): 1 [t=6.60172s, 34090916 KB] g=218888, 1239 evaluated, 40 expanded [t=6.60412s, 34090980 KB] New best heuristic value for lmcut(): 0 [t=6.60413s, 34090980 KB] g=218889, 1270 evaluated, 41 expanded [t=6.60414s, 34090980 KB] Solution found! [t=6.60415s, 34090980 KB] Actual search time: 6.55434s goto o__0__6__0_ o__1__5__0_ (5451) goto o__1__5__0_ o__2__5__0_ (5448) goto o__2__5__0_ o__3__5__0_ (5445) goto o__3__5__0_ o__4__5__0_ (5444) goto o__4__5__0_ o__5__5__0_ (5443) goto o__5__5__0_ o__6__5__0_ (5444) goto o__6__5__0_ o__7__5__0_ (5445) goto o__7__5__0_ o__8__5__0_ (5446) goto o__8__5__0_ o__9__5__0_ (5447) goto o__9__5__0_ o__10__5__0_ (5447) goto o__10__5__0_ o__11__5__0_ (5448) goto o__11__5__0_ o__12__5__0_ (5448) goto o__12__5__0_ o__13__5__0_ (5449) goto o__13__5__0_ o__14__5__0_ (5449) goto o__14__5__0_ o__15__5__0_ (5240) goto o__15__5__0_ o__16__5__0_ (5239) goto o__16__5__0_ o__17__5__0_ (5867) goto o__17__5__0_ o__18__5__0_ (5447) goto o__18__5__0_ o__19__5__0_ (5448) goto o__19__5__0_ o__20__5__0_ (5452) goto o__20__5__0_ o__21__5__0_ (5459) goto o__21__5__0_ o__22__5__0_ (5465) goto o__22__5__0_ o__23__5__0_ (5471) goto o__23__5__0_ o__24__5__0_ (5478) goto o__24__5__0_ o__25__5__0_ (5484) goto o__25__5__0_ o__26__5__0_ (5488) goto o__26__5__0_ o__27__5__0_ (5488) goto o__27__5__0_ o__28__5__0_ (5488) goto o__28__5__0_ o__29__5__0_ (5489) goto o__29__5__0_ o__30__5__0_ (5489) goto o__30__5__0_ o__31__5__0_ (5490) goto o__31__5__0_ o__32__5__0_ (5488) goto o__32__5__0_ o__33__5__0_ (5488) goto o__33__5__0_ o__34__5__0_ (5494) goto o__34__5__0_ o__35__5__0_ (5504) goto o__35__5__0_ o__36__5__0_ (5517) goto o__36__5__0_ o__37__5__0_ (5531) goto o__37__5__0_ o__38__5__0_ (5542) goto o__38__5__0_ o__39__5__0_ (5545) goto o__39__5__0_ o__40__4__0_ (5543) reach_goal0 (1) [t=6.60415s, 34090980 KB] Plan length: 41 step(s). [t=6.60415s, 34090980 KB] Plan cost: 218889 [t=6.60415s, 34090980 KB] Expanded 42 state(s). [t=6.60415s, 34090980 KB] Reopened 0 state(s). [t=6.60415s, 34090980 KB] Evaluated 1270 state(s). [t=6.60415s, 34090980 KB] Evaluations: 1270 [t=6.60415s, 34090980 KB] Generated 1269 state(s). [t=6.60415s, 34090980 KB] Dead ends: 0 state(s). [t=6.60415s, 34090980 KB] Expanded until last jump: 0 state(s). [t=6.60415s, 34090980 KB] Reopened until last jump: 0 state(s). [t=6.60415s, 34090980 KB] Evaluated until last jump: 1 state(s). [t=6.60415s, 34090980 KB] Generated until last jump: 0 state(s). [t=6.60415s, 34090980 KB] Number of registered states: 1270 [t=6.60415s, 34090980 KB] Int hash set load factor: 1270/2048 = 0.620117 [t=6.60415s, 34090980 KB] Int hash set resizes: 11 [t=6.60415s, 34090980 KB] Search time: 6.56728s [t=6.60415s, 34090980 KB] Total time: 6.60415s Solution found. Peak memory: 34090980 KB Remove intermediate file output.sas search exit code: 0 INFO Planner time: 9.35s Extracting plan...