From acc9c2c99ca3c2889cd9558f36396cc80b98ea1f Mon Sep 17 00:00:00 2001 From: Jean Privat Date: Wed, 5 Aug 2015 11:51:24 -0400 Subject: [PATCH] contrib: add a simple planner that use lib/ai Signed-off-by: Jean Privat --- contrib/simplan/.gitignore | 6 + contrib/simplan/Makefile | 18 ++ contrib/simplan/plan1.txt | 42 +++ contrib/simplan/plan2.txt | 46 +++ contrib/simplan/prob1.txt | 175 +++++++++++ contrib/simplan/prob2.txt | 177 +++++++++++ contrib/simplan/simplan.nit | 639 +++++++++++++++++++++++++++++++++++++++ contrib/simplan/simplan.sablecc | 36 +++ 8 files changed, 1139 insertions(+) create mode 100644 contrib/simplan/.gitignore create mode 100644 contrib/simplan/Makefile create mode 100644 contrib/simplan/plan1.txt create mode 100644 contrib/simplan/plan2.txt create mode 100644 contrib/simplan/prob1.txt create mode 100644 contrib/simplan/prob2.txt create mode 100644 contrib/simplan/simplan.nit create mode 100644 contrib/simplan/simplan.sablecc diff --git a/contrib/simplan/.gitignore b/contrib/simplan/.gitignore new file mode 100644 index 0000000..9ab9e7a --- /dev/null +++ b/contrib/simplan/.gitignore @@ -0,0 +1,6 @@ +*_lexer.nit +*_parser.nit + +*.dot +*.out +simplan diff --git a/contrib/simplan/Makefile b/contrib/simplan/Makefile new file mode 100644 index 0000000..530c25e --- /dev/null +++ b/contrib/simplan/Makefile @@ -0,0 +1,18 @@ +NITC=../../bin/nitc +NITCC=../nitcc/src/nitcc + +all: simplan + +simplan: simplan.nit simplan_parser.nit + ${NITC} simplan.nit + +check: simplan + ./simplan prob1.txt | tee plan1.txt.out + ./simplan prob1.txt plan1.txt + diff plan1.txt plan1.txt.out + +simplan_parser.nit: ${NITCC} simplan.sablecc + ${NITCC} simplan.sablecc + +${NITCC}: + ${MAKE} -C ../nitcc diff --git a/contrib/simplan/plan1.txt b/contrib/simplan/plan1.txt new file mode 100644 index 0000000..f6e32d5 --- /dev/null +++ b/contrib/simplan/plan1.txt @@ -0,0 +1,42 @@ +# 50 locations +# 216 roads +# 1 robot +# 3 parcels +# 1 goal +# size of the problem: 6250000 +SimplePlan { +Drive(r0,l28,l13); +Drive(r0,l13,l45); +Drive(r0,l45,l30); +Drive(r0,l30,l14); +Load(r0,b1); +Drive(r0,l14,l42); +Drive(r0,l42,l25); +Load(r0,b2); +Drive(r0,l25,l20); +Drive(r0,l20,l21); +Drive(r0,l21,l1); +Drive(r0,l1,l2); +Drive(r0,l2,l49); +Unload(r0,b1); +Drive(r0,l49,l2); +Drive(r0,l2,l34); +Drive(r0,l34,l18); +Drive(r0,l18,l22); +Drive(r0,l22,l23); +Unload(r0,b2); +Drive(r0,l23,l43); +Drive(r0,l43,l27); +Load(r0,b0); +Drive(r0,l27,l43); +Drive(r0,l43,l7); +Drive(r0,l7,l10); +Drive(r0,l10,l42); +Drive(r0,l42,l46); +Drive(r0,l46,l30); +Drive(r0,l30,l47); +Unload(r0,b0); +} +# plan in 31 steps; cost=3613.363 + +# solver infos: steps=63740 nodes=165751 todo=95238 n=374949 (bf=5.882) mem=228651 last=#63740/165750 d=31 f=3613.363 g=3613.363 h=0.0: l47,l47,l49,l23 diff --git a/contrib/simplan/plan2.txt b/contrib/simplan/plan2.txt new file mode 100644 index 0000000..d972e1d --- /dev/null +++ b/contrib/simplan/plan2.txt @@ -0,0 +1,46 @@ +# 50 locations +# 216 roads +# 1 robot +# 4 parcels +# 1 goal +# size of the problem: 312500000 +SimplePlan { +Drive(r0,l28,l13); +Drive(r0,l13,l29); +Drive(r0,l29,l24); +Drive(r0,l24,l9); +Drive(r0,l9,l25); +Load(r0,b2); +Load(r0,b3); +Drive(r0,l25,l10); +Drive(r0,l10,l7); +Drive(r0,l7,l23); +Unload(r0,b2); +Drive(r0,l23,l43); +Drive(r0,l43,l27); +Load(r0,b0); +Drive(r0,l27,l43); +Drive(r0,l43,l7); +Drive(r0,l7,l10); +Drive(r0,l10,l42); +Drive(r0,l42,l46); +Drive(r0,l46,l30); +Drive(r0,l30,l47); +Unload(r0,b0); +Drive(r0,l47,l30); +Drive(r0,l30,l14); +Load(r0,b1); +Unload(r0,b3); +Drive(r0,l14,l26); +Drive(r0,l26,l10); +Drive(r0,l10,l7); +Drive(r0,l7,l22); +Drive(r0,l22,l18); +Drive(r0,l18,l34); +Drive(r0,l34,l2); +Drive(r0,l2,l49); +Unload(r0,b1); +} +# plan in 35 steps; cost=3817.866 + +# solver infos: steps=642940 nodes=1735072 todo=1028967 n=3826575 (bf=5.952) mem=2275189 last=#642940/1735070 d=35 f=3817.866 g=3817.866 h=0.0: l49,l47,l49,l23,l14 diff --git a/contrib/simplan/prob1.txt b/contrib/simplan/prob1.txt new file mode 100644 index 0000000..3244b30 --- /dev/null +++ b/contrib/simplan/prob1.txt @@ -0,0 +1,175 @@ +Locations { + l0 54.0 157.0; + l1 142.0 322.0; + l2 17.625145191109436 362.7287804981639; + l3 8.752924683883949 652.4538767470752; + l4 280.29942326716036 112.84657877925903; + l5 280.07476562437296 316.83759171242434; + l6 352.0 383.0; + l7 427.7973423614033 534.5569693075433; + l8 645.0 50.0; + l9 594.1567879434075 207.08971743408088; + l10 551.1448100068717 396.37036744450734; + l11 689.6923649366455 606.8179646038893; + l12 798.2444364374692 172.9460838932327; + l13 1041.0 208.0; + l14 730.0 503.0; + l15 764.0 650.0; + l16 109.0 106.0; + l17 176.23541418756668 217.45343995171842; + l18 174.0 449.0; + l19 185.86325364192228 636.4256578638509; + l20 456.0 158.0; + l21 251.036774762431 216.80730259283249; + l22 279.0 486.0; + l23 376.78872928105346 637.727566657247; + l24 649.5978269032476 173.14673180434525; + l25 522.0 293.0; + l26 621.0 484.0; + l27 665.0 673.0; + l28 993.0 58.0; + l29 759.1098336783851 230.9431550946424; + l30 784.6590413371292 406.09174619635155; + l31 846.7583112657318 585.1443328897806; + l32 189.0 71.0; + l33 70.0 287.0; + l34 52.0 454.0; + l35 19.0 573.0; + l36 283.82289949208706 56.855981241276524; + l37 394.0 316.0; + l38 243.0 381.0; + l39 259.50875035171345 689.0999806128916; + l40 593.1572931438346 143.91140279750383; + l41 674.0 289.0; + l42 633.0542256736045 382.3427298569007; + l43 493.32885850446525 649.6309903737257; + l44 824.0 43.0; + l45 896.7591861159066 286.66409701463397; + l46 703.024710767699 376.0847997537542; + l47 822.5827054085579 548.0316713994954; + l48 49.81730069726453 28.577354623284567; + l49 9.259029707623585 256.40948013940505; +} +Roads { +l0 l16; +l0 l17; +l0 l48; +l1 l17; +l1 l18; +l1 l2; +l1 l21; +l1 l38; +l1 l5; +l1 l6; +l10 l25; +l10 l26; +l10 l41; +l10 l42; +l10 l7; +l11 l15; +l11 l27; +l11 l43; +l12 l29; +l13 l28; +l13 l29; +l13 l44; +l13 l45; +l14 l26; +l14 l30; +l14 l42; +l14 l46; +l15 l27; +l16 l17; +l16 l32; +l16 l48; +l17 l20; +l17 l21; +l17 l32; +l17 l4; +l17 l5; +l18 l22; +l18 l34; +l18 l38; +l18 l5; +l18 l6; +l19 l23; +l19 l3; +l19 l35; +l19 l39; +l2 l33; +l2 l34; +l2 l49; +l20 l21; +l20 l25; +l20 l32; +l20 l36; +l20 l37; +l20 l4; +l20 l40; +l20 l41; +l20 l5; +l20 l6; +l20 l8; +l20 l9; +l21 l32; +l21 l4; +l21 l5; +l22 l23; +l22 l38; +l22 l6; +l22 l7; +l23 l39; +l23 l43; +l23 l7; +l24 l29; +l24 l40; +l24 l8; +l24 l9; +l25 l41; +l25 l42; +l25 l9; +l26 l30; +l26 l42; +l27 l43; +l28 l44; +l29 l45; +l3 l35; +l30 l45; +l30 l46; +l30 l47; +l31 l47; +l32 l48; +l33 l34; +l33 l49; +l36 l4; +l37 l38; +l37 l5; +l37 l6; +l37 l7; +l38 l5; +l38 l6; +l38 l7; +l39 l7; +l40 l8; +l40 l9; +l41 l42; +l41 l9; +l42 l46; +l43 l7; +l45 l46; +l5 l6; +l6 l7; +} +Robots{ + r0 l28; +} +Parcels{ + b0 l27; + b1 l14; + b2 l25; +} +Goals{ + b0 l47; + b1 l49; + b2 l23; +} diff --git a/contrib/simplan/prob2.txt b/contrib/simplan/prob2.txt new file mode 100644 index 0000000..172b276 --- /dev/null +++ b/contrib/simplan/prob2.txt @@ -0,0 +1,177 @@ +Locations { + l0 54.0 157.0; + l1 142.0 322.0; + l2 17.625145191109436 362.7287804981639; + l3 8.752924683883949 652.4538767470752; + l4 280.29942326716036 112.84657877925903; + l5 280.07476562437296 316.83759171242434; + l6 352.0 383.0; + l7 427.7973423614033 534.5569693075433; + l8 645.0 50.0; + l9 594.1567879434075 207.08971743408088; + l10 551.1448100068717 396.37036744450734; + l11 689.6923649366455 606.8179646038893; + l12 798.2444364374692 172.9460838932327; + l13 1041.0 208.0; + l14 730.0 503.0; + l15 764.0 650.0; + l16 109.0 106.0; + l17 176.23541418756668 217.45343995171842; + l18 174.0 449.0; + l19 185.86325364192228 636.4256578638509; + l20 456.0 158.0; + l21 251.036774762431 216.80730259283249; + l22 279.0 486.0; + l23 376.78872928105346 637.727566657247; + l24 649.5978269032476 173.14673180434525; + l25 522.0 293.0; + l26 621.0 484.0; + l27 665.0 673.0; + l28 993.0 58.0; + l29 759.1098336783851 230.9431550946424; + l30 784.6590413371292 406.09174619635155; + l31 846.7583112657318 585.1443328897806; + l32 189.0 71.0; + l33 70.0 287.0; + l34 52.0 454.0; + l35 19.0 573.0; + l36 283.82289949208706 56.855981241276524; + l37 394.0 316.0; + l38 243.0 381.0; + l39 259.50875035171345 689.0999806128916; + l40 593.1572931438346 143.91140279750383; + l41 674.0 289.0; + l42 633.0542256736045 382.3427298569007; + l43 493.32885850446525 649.6309903737257; + l44 824.0 43.0; + l45 896.7591861159066 286.66409701463397; + l46 703.024710767699 376.0847997537542; + l47 822.5827054085579 548.0316713994954; + l48 49.81730069726453 28.577354623284567; + l49 9.259029707623585 256.40948013940505; +} +Roads { +l0 l16; +l0 l17; +l0 l48; +l1 l17; +l1 l18; +l1 l2; +l1 l21; +l1 l38; +l1 l5; +l1 l6; +l10 l25; +l10 l26; +l10 l41; +l10 l42; +l10 l7; +l11 l15; +l11 l27; +l11 l43; +l12 l29; +l13 l28; +l13 l29; +l13 l44; +l13 l45; +l14 l26; +l14 l30; +l14 l42; +l14 l46; +l15 l27; +l16 l17; +l16 l32; +l16 l48; +l17 l20; +l17 l21; +l17 l32; +l17 l4; +l17 l5; +l18 l22; +l18 l34; +l18 l38; +l18 l5; +l18 l6; +l19 l23; +l19 l3; +l19 l35; +l19 l39; +l2 l33; +l2 l34; +l2 l49; +l20 l21; +l20 l25; +l20 l32; +l20 l36; +l20 l37; +l20 l4; +l20 l40; +l20 l41; +l20 l5; +l20 l6; +l20 l8; +l20 l9; +l21 l32; +l21 l4; +l21 l5; +l22 l23; +l22 l38; +l22 l6; +l22 l7; +l23 l39; +l23 l43; +l23 l7; +l24 l29; +l24 l40; +l24 l8; +l24 l9; +l25 l41; +l25 l42; +l25 l9; +l26 l30; +l26 l42; +l27 l43; +l28 l44; +l29 l45; +l3 l35; +l30 l45; +l30 l46; +l30 l47; +l31 l47; +l32 l48; +l33 l34; +l33 l49; +l36 l4; +l37 l38; +l37 l5; +l37 l6; +l37 l7; +l38 l5; +l38 l6; +l38 l7; +l39 l7; +l40 l8; +l40 l9; +l41 l42; +l41 l9; +l42 l46; +l43 l7; +l45 l46; +l5 l6; +l6 l7; +} +Robots{ + r0 l28; +} +Parcels{ + b0 l27; + b1 l14; + b2 l25; + b3 l25; +} +Goals{ + b0 l47; + b1 l49; + b2 l23; + b3 l14; +} diff --git a/contrib/simplan/simplan.nit b/contrib/simplan/simplan.nit new file mode 100644 index 0000000..ba32497 --- /dev/null +++ b/contrib/simplan/simplan.nit @@ -0,0 +1,639 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# A simple planning problem solver using A* for a robot that delivers parcels. +# +# A map is made of `Location`s (with cartesian coordinates) connected with `Road`s. +# Some parcels and a robot are placed on the map. +# +# The goal of the robot is to plan the delivery of the parcels to their destination in the most +# efficient way knowing that: +# +# * the robot has a given speed to drive +# * the loading and unloading of parcels take time +# * the capacity of the robot is limited +module simplan + +import ai::search + +private import simplan_lexer +private import simplan_parser + +# The description of the planing problem to solve +class PlanProblem + super SearchProblem[State, Action] + + # Some parameters of the problem + + # The speed on the road. + # Used for the action `Drive` + var speed = 1.0 + + # Cost of loading a parcel in a robot + # Used for the action `Load` + var duration_loading = 30.0 + + # Cost of unloading a parcel in a robot + # Used for the action `Unload` + var duration_unloading = 30.0 + + # How many parcels can a robot transport at the same time? + var capacity = 2 + + # The name of the robot + var robot_name = "r0" + + # Locations on the map, by their names + var locations = new HashMap[String, Location] + + # All the parcels, by their `id` + var parcels = new Array[Parcel] + + # All the parcels, by their names + var parcel_by_name = new HashMap[String, Parcel] + + # +infinite, used to initialize some floats with the maximum value. + private var infinite: Float = 1.0 / 0.0 + + # The starting state + redef var initial_state: State is noinit + + # Parse and initialize a problem from description `text` + fun parse(text: String) + do + var l = new Lexer_simplan(text) + var p = new Parser_simplan + p.tokens.add_all l.lex + var n = p.parse + if n isa NError then + print n.message + exit 1 + end + n = n.children.first.children.first.as(not null) + if n isa Nplan then + print "Error: expected a problem, got a plan." + exit 1 + end + assert n isa Nproblem + + # Load all locations + for n2 in n.n_locations.n_list.children do + var e = new Location(locations.length, n2.n_name.text, n2.n_x.text.to_f, n2.n_y.text.to_f) + assert not locations.has_key(e.name) + locations[e.name] = e + end + print "# {locations.length} locations" + + # Load all roads + var nbr = 0 + for n2 in n.n_roads.n_list.children do + var o = locations.get_or_null(n2.n_orig.text) + var d = locations.get_or_null(n2.n_dest.text) + assert o != null and d != null + var r = new Road(o,d) + o.roads.add(r) + r = new Road(d,o) + d.roads.add(r) + nbr += 2 + end + print "# {nbr} roads" + + # Compute all road durations + for e in locations.values do + e.durations = new Array[Float].filled_with(infinite, locations.length) + e.durations[e.id] = 0.0 + for r in e.roads do + e.durations[r.dest.id] = r.distance / speed + end + end + + # Close the duration relation between each pair of locations + for k in locations.values do + for i in locations.values do + for j in locations.values do + var d = i.durations[k.id] + k.durations[j.id] + if i.durations[j.id] > d then + i.durations[j.id] = d + end + end + end + end + + # Load the robot + var robot = null + for n2 in n.n_robots.n_list.children do + var name = n2.n_name.text + robot = locations.get_or_null(n2.n_emplacement.text) + assert name == robot_name and robot != null + end + assert robot != null + print "# 1 robot" + + # Load the parcels + var parcel_locations = new Array[nullable Location] + for n2 in n.n_parcels.n_list.children do + var name = n2.n_name.text + var e = locations.get_or_null(n2.n_emplacement.text) + assert e != null + var parcel = new Parcel(parcels.length, name, e, e) + parcels.add parcel + parcel_locations.add e + parcel_by_name[name] = parcel + + end + print "# {parcels.length} parcels" + + # Load the goal of parcels + for n2 in n.n_goal.n_list.children do + var parcel = parcel_by_name.get_or_null(n2.n_name.text) + var e = locations.get_or_null(n2.n_emplacement.text) + assert parcel != null and e != null + parcel.goal = e + end + print "# 1 goal" + + print "# size of the problem: {locations.length.to_f.pow(parcels.length.to_f+1.0).to_precision(0)}" + + initial_state = new State(self, robot, parcel_locations, 0) + end + + # Parse a plan for a given problem + fun parse_plan(text: String): Plan + do + var l = new Lexer_simplan(text) + var p = new Parser_simplan + p.tokens.add_all l.lex + var n = p.parse + if n isa NError then + print n.message + exit 1 + end + n = n.children.first.children.first.as(not null) + if n isa Nproblem then + print "Error: expected a plan, got a problem." + exit 1 + end + assert n isa Nplan + + var res = new Plan(self) + var e = initial_state + var cost = 0.0 + for n2 in n.n_actions.children do + if n2 isa Naction_load then + var parcel = parcel_by_name.get_or_null(n2.n_parcel.text) + assert parcel != null + var a = new Load(self, parcel) + res.actions.add(a) + e = a.trans(e) + cost += a.cost + else if n2 isa Naction_unload then + var parcel = parcel_by_name.get_or_null(n2.n_parcel.text) + assert parcel != null + var a = new Unload(self, parcel) + res.actions.add(a) + e = a.trans(e) + cost += a.cost + else if n2 isa Naction_drive then + var o = locations.get_or_null(n2.n_orig.text) + var d = locations.get_or_null(n2.n_dest.text) + assert o != null and d != null + var road: nullable Road = null + for r in o.roads do if r.dest == d then + road = r + break + end + assert road != null + var a = new Drive(self, road) + res.actions.add(a) + e = a.trans(e) + cost += a.cost + else abort + end + print "# loaded plan in {res.actions.length} steps; cost = {cost}" + return res + end + + redef fun actions(state) + do + var res = new Array[Action] + + # Driving? + for road in state.robot.roads do + res.add(new Drive(self, road)) + end + + # Loading? + for i in [0..state.parcels.length[ do + if state.parcels[i] == state.robot and state.nb_parcels < self.capacity and self.parcels[i].goal != state.robot then + res.add(new Load(self, parcels[i])) + end + end + + # Unloading? + for i in [0..state.parcels.length[ do + # Unloading is always a valid action, + # even if dropping a parcel outside of its goal is unlikely (but possible) + # to be a part of an optimal plan. + if state.parcels[i] == null then #and self.parcels[i].goal == state.robot then + res.add(new Unload(self, parcels[i])) + end + end + + return res + end + + redef fun apply_action(state, action) do return action.trans(state) + + redef fun cost(state1, action, state2) do return action.cost + + redef fun is_goal(state) + do + for i in [0..parcels.length[ do + if state.parcels[i] != parcels[i].goal then return false + end + return true + end + + redef fun heuristic(state) + do + # Combination (maximum) of two heuristic: + # Heuristic 1: maximum driving time to take and deliver a single parcel + var max_for_one = 0.0 + # Heuristic 2: driving time to take the nearest parcel, then deliver all parcels + var total_deliver_drive = 0.0 + var min_take_one = infinite + # Total loading/unloading time (incompressible cost, added to both heuristics) + var total_load = 0.0 + + for i in [0..parcels.length[ do + # The parcel location + var c = state.parcels[i] + + # Its goal location + var b = parcels[i].goal + + # Parcel is fine, nothing to do. + if c == b then continue + + # Driving time to take and deliver this parcel + var t = 0.0 + + # Current position of the parcel (somewhere or in the robot) + var current: Location + + if c == null then + # The parcel is in the robot + current = state.robot + min_take_one = 0.0 + else + # The parcel is somewhere + current = c + # So go get it. + var tt = state.robot.duration(c) + total_load += duration_loading + + t += tt + if tt < min_take_one then min_take_one = tt + end + + # Drive and unload the parcel + var td = current.duration(b) + total_load += duration_unloading + + t += td + if t > max_for_one then max_for_one = t + total_deliver_drive += td + end + + # Since one robot can transport several parcels at the same time, + # the best optimistic scenario is to deliver at full capacity + if min_take_one == infinite then min_take_one = 0.0 + var res = min_take_one + total_deliver_drive / capacity.to_f + + # Get best of both heuristics + if res < max_for_one then res = max_for_one + + # Add incompressible (un)loading costs + res += total_load + + return res + end + + redef fun make_memory + do + var res = super + res.add new RBTreeMap[State, SearchNode[State, Action]] + res.add new BinTreeMap[State, SearchNode[State, Action]] + return res + end +end + +# A node on the map +class Location + # Indexed identifier, starting at 0 + # Used to access locations in arrays. + var id: Int + + # The name of the location, from the problem description + var name: String + + # The x-coordinate of the location + var x: Float + + # The y-coordinate of the location + var y: Float + + # All roads from this location + var roads = new Array[Road] + + # Drive duration to any other location on the map + fun duration(dest: Location): Float + do + return durations[dest.id] + end + + private var durations = new Array[Float] + + redef fun to_s do return "{id}({x}, {y})" +end + +# A directed road segment between two locations +class Road + # The origin + var orig: Location + + # The destination + var dest: Location + + # The distance according to the coordinates of the locations. + var distance: Float is noautoinit + + init + do + var dx = orig.x-dest.x + var dy = orig.y-dest.y + distance = (dx*dx + dy*dy).sqrt + end +end + +# A parcel to move +class Parcel + # Indexed identifier, starting by 0 + # Used to access parcels in arrays. + var id: Int + # The name of the parcel according to the problem description + # Used for output + var name: String + # The starting location + var start: Location + # The goal location + var goal: Location +end + + +# A plan on a problem +class Plan + # The original problem + var problem: PlanProblem + + # The sequence of actions in the plan + var actions = new Array[Action] + + # Check and write the plan + fun dump(verbose: Bool) + do + var e = problem.initial_state + print "SimplePlan \{" + var cost = 0.0 + if verbose then print "#{e} {cost}" + for a in actions do + print "{a}" + e = a.trans(e) + cost += a.cost + if verbose then + print "#{e} {cost}" + if a isa Drive then + print "#{a.road.orig} -- {a.road.dest}: {a.road.distance}" + end + end + + end + print "\}" + if not problem.is_goal(e) then + print "# /!\\ Goal Failed" + end + print "# plan in {actions.length} steps; cost={cost}\n" + end +end + +# A primitive movement +abstract class Action + # The unitary cost of the action + fun cost: Float is abstract + + # The state resulting to the application of the action + fun trans(e: State): State is abstract + + # The original problem + var problem: PlanProblem +end + +# A loading of a parcel +class Load + super Action + + # The loaded parcel + var parcel: Parcel + + redef fun cost do return problem.duration_loading + + redef fun to_s do return "Load({problem.robot_name},{parcel.name});" + + redef fun trans(e) + do + var res = e.clone + assert res.parcels[parcel.id] == res.robot + res.parcels = res.parcels.clone + res.parcels[parcel.id] = null + assert res.nb_parcels < problem.capacity + res.nb_parcels += 1 + return res + end +end + +# A unloading of a parcel +class Unload + super Action + + # The unloaded parcel + var parcel: Parcel + + redef fun cost do return problem.duration_unloading + + redef fun to_s do return "Unload({problem.robot_name},{parcel.name});" + + redef fun trans(e) + do + var res = e.clone + assert res.parcels[parcel.id] == null + res.parcels = res.parcels.clone + res.parcels[parcel.id] = res.robot + assert res.nb_parcels > 0 + res.nb_parcels -= 1 + return res + end +end + +# A road driving +class Drive + super Action + + # The road drove on + var road: Road + + redef fun cost do return road.distance / problem.speed + + redef fun to_s do return "Drive({problem.robot_name},{road.orig.name},{road.dest.name});" + + redef fun trans(e) + do + var res = e.clone + assert res.robot == road.orig + res.robot = road.dest + return res + end +end + +# Where each robot and parcel are? +class State + super Comparable + redef type OTHER: State + + # The original problem + var problem: PlanProblem + + # Where is the robot + var robot: Location + + # Where each parcel is + # `null` if the parcel is loaded + var parcels: Array[nullable Location] + + # Number of loaded parcels + # Must be consistent with `parcels` + var nb_parcels: Int + + # Clone of the state + # Used by `Action::trans` + # + # Warning: the `parcels` array is not cloned for efficiency. + # You need to clone it if you mutate it + private fun clone: State + do + var res = new State(problem, robot, parcels, nb_parcels) + return res + end + + redef fun hash + do + var res = hash_cache + if res != 0 then return res + res = robot.hash * 23 + parcels.hash * 7 + hash_cache = res + return res + end + + private var hash_cache = 0 + + redef fun ==(o) + do + if not o isa State then return false + return robot == o.robot and parcels == o.parcels + end + + redef fun <(o) do return (self <=> o) < 0 + + redef fun <=>(o) do + var res = robot.id <=> o.robot.id + if res != 0 then return res + for i in [0..parcels.length[ do + var c = parcels[i] + var oc = o.parcels[i] + if c == oc then continue + if c == null then return -1 + if oc == null then return 1 + res = c.id <=> oc.id + if res != 0 then return res + end + return 0 + end + + redef fun to_s + do + var res = "{robot.name}" + for c in parcels do + res += "," + if c != null then + res += c.name + end + end + return res + end +end + +# --configs +var configs = false +if not args.is_empty and args.first == "--configs" then + configs = true + args.shift +end + +# Usage +if args.is_empty then + print "Usage: plan [--configs] problem.txt [plan.txt]\nSearch, or apply, a plan to a problem." + exit 0 +end + +var problem = new PlanProblem + +# Load +var problem_text = args.first.to_path.read_all +problem.parse(problem_text) + +# Apply a plan +if args.length == 2 then + var plan_text = args[1].to_path.read_all + var plan = problem.parse_plan(plan_text) + plan.dump(false) + exit 0 +end + +# run --configs? +if configs then + problem.run_configs(100000) + exit 0 +end + +# Solve the plan +var solver = problem.astar +solver.memorize = true +var res = solver.run +if res == null then + print "No plan found :(" + return +end +var plan = new Plan(problem) +plan.actions.add_all res.plan +plan.dump(false) +print "# solver infos: {solver}" diff --git a/contrib/simplan/simplan.sablecc b/contrib/simplan/simplan.sablecc new file mode 100644 index 0000000..ca02f34 --- /dev/null +++ b/contrib/simplan/simplan.sablecc @@ -0,0 +1,36 @@ +Grammar simplan; + +Lexer + +letter = 'a'..'z'|'a'..'Z'; +digit = '0'..'9'; +name = letter (letter|digit)*; +nb = digit* '.' digit+ | digit+; + +eol = #10 | #13 | #10 #13; +comment = '#' (Any-eol)* eol?; + +blank = #9 | #10 | #13 | ' ' | comment; + +Parser + +Ignored blank; + +file = problem | plan ; + +problem = locations roads robots parcels goal; +locations = 'Locations' '{' [list:]location* '}'; +location = name [x:]nb [y:]nb ';'; +roads = 'Roads' '{' [list:]road* '}'; +road = [orig:]name [dest:]name ';' ; +robots = 'Robots' '{' [list:]robot* '}'; +robot = name [emplacement:]name ';'; +parcels = 'Parcels' '{' [list:]parcel* '}'; +parcel = name [emplacement:]name ';'; +goal = 'Goals' '{' [list:]parcel* '}'; + +plan = 'SimplePlan' '{' [actions:]action* '}'; +action = + {load:} 'Load' '(' [robot:]name ',' [parcel:]name ')' ';' | + {unload:} 'Unload' '(' [robot:]name ',' [parcel:]name ')' ';' | + {drive:} 'Drive' '(' [robot:]name ',' [orig:]name ',' [dest:]name ')' ';' ; -- 1.7.9.5