Hi Ramin,
For this kind of problem, I would strongly encourage using answer-set
programming. It looks like prolog (but isn't), it uses modern SAT-solving
technology to get tremendous speed. The Univ Potsdam solver is maybe the
best one. It's excellent for solving constraint satisfaction problems.
Here's an example: instead of airplanes, its boats and oars. The
constraints are:
-- a race every 4 minutes
-- boat must be back in time to unload, reload, and get to starting line
viz 12 minutes
-- boat (and oars) obviously cannot be used by someone else while on the
water
-- boats are 1x, 2x, 2+, 2-, 4x, 4+, 4-, 8+ (these are different kinds of
boats)
-- oars must be a matched set, appropriate for that boat style.
-- boats are constrained by the race that they are in.
-- certain crews insist on using certain equipment, and have priority
-- certain crews can select only a subset (e.g. mens crews cannot use the
lightweight boats)
It turns out that the problem is not too hard, until you throw the oars
into the mix, and then it gets a lot harder.
Here's the solver (it works):
%
% regatta team equipment scheduling
%
% The problem of scheduling equipment for a regatta is a constraint
% problem -- two crews cannot use the same boat at the same time,
% and, indeed, there must be enough time between crews to rig the boat,
% launch it, warm up, race, and return to the dock, before the next
% crew can use it. Because this is a classic constraint problem,
% implementing this via answer-set programming seems like the easiest,
% most direct way to accomplish this.
%
% Initial version: Linas Vepstas April 2012
%
% Copyright (c) 2012 Linas Vepstas
% The GNU GPLv3 applies.
%
% -- List of fundamental boat classes. We must distinguish sweeps
% from sculls, and quads, doubles, singles, etc. in order to be
% able to count the number of oars needed, for oar reservations.
% That's why these are the "fundamental" types.
boat(BOAT) :- sweep_boat(BOAT).
boat(BOAT) :- scull_boat(BOAT).
sweep_boat(BOAT) :- eight(BOAT).
sweep_boat(BOAT) :- fourplus(BOAT).
sweep_boat(BOAT) :- fourminus(BOAT).
sweep_boat(BOAT) :- pair(BOAT).
scull_boat(BOAT) :- quad(BOAT).
scull_boat(BOAT) :- double(BOAT).
scull_boat(BOAT) :- single(BOAT).
%%% ========================================================== %%%
%% The actual scheduling algorithm. Short and simple, huh?
%% DO NOT MODIFY ANYTHING BELOW THIS LINE!
%% (Unless you really, really know what you're doing, and
%% you probably don't.) Just write me with questions, requests.
%%% ========================================================== %%%
% Some priority assignments:
boat_reserve_priority(12). % top priority
oar_reserve_priority(11). % 2nd highest priority
boat_hotseat_priority(10). % 3rd priority
oar_hotseat_priority(9). % 4th priority
boat_choice_priority(8).
oar_choice_priority(7).
num_boats_priority(6).
num_oars_priority(5).
% Below follows the core available/request/reserve logic.
% A boat is available if its not in use by any crew.
available(RACE, BOAT) :- racenum(RACE), crew(CREW), boat(BOAT),
not inuse(RACE, CREW, BOAT).
% Reserve the boat if it is requested and available.
reserve(RACE, CREW, BOAT) :- racenum(RACE), crew(CREW), boat(BOAT),
request(RACE, CREW, BOAT),
available(RACE, BOAT).
% If a boat is reserved, then it will be in use at least CENTER races
% beforehand. That is, the crew needs CENTER-1 races to launch and
% warmup before the race.
inuse(ONWATER, CREW, BOAT) :- reserve(RACE, CREW, BOAT),
heat(SCH, RACE),
SCHMN = SCH - N,
heat(SCHMN, ONWATER),
N = 1..CENTER-1,
center(CENTER).
% Its on the water for the next race, too.
inuse(ONWATER, CREW, BOAT) :- reserve(RACE, CREW, BOAT),
heat(SCH, RACE),
heat(SCH+1, ONWATER).
% Cannot reserve a boat that is in use.
:- reserve(RACE, CREW, BOAT), inuse(RACE, OTHER_CREW, BOAT),
racenum(RACE), crew(CREW), crew(OTHER_CREW), boat(BOAT).
% Cannot request a boat if its in use.
% This rule isn't needed right now, comment it out.
% :- request(RACE, CREW, BOAT), inuse(RACE, OTHER_CREW, BOAT).
% Two different crews cannot reserve same boat for the same race.
:- reserve(RACE, CREW, BOAT), reserve(RACE, OTHER_CREW, BOAT),
CREW != OTHER_CREW,
racenum(RACE), crew(CREW), crew(OTHER_CREW), boat(BOAT).
% ----------------------
% Preference indication.
% choice must be a number, 1 to 4.
choice(CHOICE) :- CHOICE=1..4.
% The total universe of all possible boat assignments, to a given
% crew and race. In this universe, only one boat is ever assigned.
1 { boat_universe(RACE, CREW, BOAT) : boat(BOAT) } 1 :-
crew(CREW), racenum(RACE).
% Out of a list of desired boats, choose only one boat.
request(RACE, CREW, BOAT) :- prefer(RACE, CREW, BOAT, CHOICE),
boat_universe(RACE, CREW, BOAT).
% A crew wants to race in a race if they've expressed a boat preference.
% or if they've requested a specific boat.
want_to_race(RACE, CREW) :- prefer(RACE, CREW, BOAT, CHOICE).
want_to_race(RACE, CREW) :- request(RACE, CREW, BOAT).
% A crew got a boat if it has a reservation.
got_a_boat(RACE, CREW) :- reserve(RACE, CREW, BOAT).
% We sure want every boat request to be granted. Must flag any crews
% that want to race a race, but we can't find them a boat.
% This flag must be highly visible.
boat_reservation_failure(RACE, CREW) :- want_to_race(RACE, CREW),
not got_a_boat(RACE, CREW).
% The above rules do allow a situation where some crews can't get
% a boat. Thus, we have to maximize for number of reservations
% granted. This must be at the highest priority, higher than the
% hot-seat avoidance priority.
#minimize [boat_reservation_failure(RACE, CREW)
: boat_reserve_priority(BRP)
: racenum(RACE)
: crew(CREW) @BRP ].
% We're going to try to honour everyone's top preferences.
% So CHOICE=1 is first choice, CHOICE=2 is second choice, etc.
#minimize [request(RACE, CREW, BOAT)
: boat_choice_priority(BCP)
: prefer(RACE, CREW, BOAT, CHOICE) = CHOICE@BCP ].
% ----------------------
% Hotseat notifications and minimization.
% Basically, we try to find assignments with the fewest hot-seats.
% True if boat will be hotseated at the dock.
hotseat(RACE, BOAT) :- reserve(RACE, CREW, BOAT),
reserve(OTHER_RACE, OTHER_CREW, BOAT),
heat(SCH, RACE),
heat(SCH-CENTER-M, OTHER_RACE),
center(CENTER),
M=0..HOTS, hotseat_warn(HOTS).
% True if crew should hurry back because boat is needed.
% Currently, not used for anything, except as a printout for the
% convenience of the crews.
hurry_back(RACE, CREW, BOAT) :-
reserve(RACE, CREW, BOAT),
reserve(OTHER_RACE, OTHER_CREW, BOAT),
heat(SCH, RACE),
heat(SCH+CENTER+M, OTHER_RACE),
center(CENTER),
M=0..HOTS, hotseat_warn(HOTS).
% Minimize the number of boats that are hot-seated.
% The @10 just means that minimizing the number of hot-seats is
% top priority -- higher priority than honoring desired boats.
#minimize [hotseat(RACE, BOAT) @BHP : boat_hotseat_priority(BHP)].
% ----------------------
% Equipment list. Stuff to take to the venue.
take_to_venue(BOAT) :- reserve(RACE, CREW, BOAT).
% This seems to make things run a bit slower... and yeilds nothing
% noteworthy, since specific boats are being aasked for in almost
% all cases, and so te below can't cut down on anything.
% It seems to add 5% or so tot toal run time ...
#minimize [take_to_venue(BOAT)
: num_boats_priority(NBP) @NBP ].
% ----------------------
% Look for a typo in the name of the boat, crew or race.
% Typos can screw everything up, so flag these.
bad_boat_name(BOAT) :- request(RACE,CREW,BOAT), not boat(BOAT).
bad_crew_name(CREW) :- request(RACE,CREW,BOAT), not crew(CREW).
bad_race_num(RACE) :- request(RACE,CREW,BOAT), not racenum(RACE).
bad_boat_name(BOAT) :- prefer(RACE,CREW,BOAT,CHOICE), not boat(BOAT).
bad_crew_name(CREW) :- prefer(RACE,CREW,BOAT,CHOICE), not crew(CREW).
bad_race_num(RACE) :- prefer(RACE,CREW,BOAT,CHOICE), not racenum(RACE).
bad_preference(CHOICE) :- prefer(RACE,CREW,BOAT,CHOICE), not choice(CHOICE).
#hide.
#show boat_reservation_failure/2.
#show bad_boat_name/1.
#show bad_crew_name/1.
#show bad_race_num/1.
#show bad_preference/1.
#show reserve/3.
#show hotseat/2.
#show hurry_back/3.
#show take_to_venue/1.
% #show request/2.
% #show inuse/2.
% #show available/2.
On Mon, Jan 1, 2018 at 7:02 AM, Ramin Barati <[email protected]> wrote:
> Hi Ben, Linas, etc
>
> I am trying to solve a resource allocation problem; assigning planes to
> flights.
>
> Here is the domain definition in PDDL:
>
> ------------------------------------------------------------
> -------------------------
> (define (domain flight-plan)
> (:requirements :strips :typing :action-costs)
> (:types
> location localable leg - object
> airport - location
> register - localable
> )
> (:predicates
> (at ?o - localable ?l - location)
> (assigned ?l - leg)
> (assigned-to ?l - leg ?r - register)
> (source ?l - leg ?a - airport)
> (destination ?l - leg ?a - airport)
> )
> (:functions
> (start ?l - leg) - number
> (duration ?l - leg ?r - register) - number
> (pax ?l - leg) - number
> (capacity ?r - register) - number
> (assignement-cost ?l - leg ?r - register) - number
> (timeline ?r - register) - number
> (total-cost) - number
> )
> (:action asgn
> :parameters (?l - leg ?r - register ?src ?dest - airport)
> :precondition (and
> (> (start ?l) (timeline ?r))
> (source ?l ?src)
> (destination ?l ?dest)
> (at ?r ?src)
> (not (assigned ?l))
> (> (capacity ?r) (pax ?l))
> )
> :effect (and
> (decrease (timeline ?r) (timeline ?r))
> (increase (timeline ?r) (+ (start ?l) (duration ?l ?r)))
> (not (at ?r ?src))
> (at ?r ?dest)
> (assigned ?l)
> (assigned-to ?l ?r)
> (increase (total-cost) (assignement-cost ?l ?r))
> )
> )
> (:action shift-left-sixty
> :parameters (?l - leg)
> :precondition (and
> (not (assigned ?l))
> (> (start ?l) 60)
> )
> :effect (and
> (decrease (start ?l) 60)
> )
> )
> (:action shift-right-sixty
> :parameters (?l - leg)
> :precondition (and
> (not (assigned ?l))
> (< (start ?l) 1380)
> )
> :effect (and
> (increase (start ?l) 60)
> )
> )
> )
> ------------------------------------------------------------
> -------------------------
>
> and here is a sample problem:
>
> ------------------------------------------------------------
> -------------------------
> (define (problem assignment)
> (:domain flight-plan)
> (:objects
> THR-SRY SRY-THR THR-ISF ISF-THR - leg
> MOC JHH MNT - register
> thr sry isf - airport
> )
> (:init
> (= (total-cost) 0)
> (at MOC thr)
> (at JHH thr)
> (at MNT thr)
> (= (capacity MOC) 100)
> (= (timeline MOC) 0)
> (= (capacity JHH) 200)
> (= (timeline JHH) 0)
> (= (capacity MNT) 280)
> (= (timeline MNT) 0)
> (source THR-SRY thr)
> (destination THR-SRY sry)
> (= (start THR-SRY) 600)
> (= (pax THR-SRY) 90)
> (source SRY-THR sry)
> (destination SRY-THR thr)
> (= (start SRY-THR) 720)
> (= (pax SRY-THR) 150)
> (source THR-ISF thr)
> (destination THR-ISF isf)
> (= (start THR-ISF) 720)
> (= (pax THR-ISF) 220)
> (source ISF-THR isf)
> (destination ISF-THR thr)
> (= (start ISF-THR) 900)
> (= (pax ISF-THR) 190)
> (= (assignement-cost THR-SRY MOC) 1)
> (= (assignement-cost SRY-THR MOC) 1)
> (= (assignement-cost THR-ISF MOC) 1)
> (= (assignement-cost ISF-THR MOC) 1)
> (= (assignement-cost THR-SRY JHH) 1)
> (= (assignement-cost SRY-THR JHH) 1)
> (= (assignement-cost THR-ISF JHH) 1)
> (= (assignement-cost ISF-THR JHH) 1)
> (= (assignement-cost THR-SRY MNT) 1)
> (= (assignement-cost SRY-THR MNT) 1)
> (= (assignement-cost THR-ISF MNT) 1)
> (= (assignement-cost ISF-THR MNT) 1)
> (= (duration THR-SRY MOC) 180)
> (= (duration SRY-THR MOC) 180)
> (= (duration THR-ISF MOC) 120)
> (= (duration ISF-THR MOC) 120)
> (= (duration THR-SRY JHH) 180)
> (= (duration SRY-THR JHH) 180)
> (= (duration THR-ISF JHH) 120)
> (= (duration ISF-THR JHH) 120)
> (= (duration THR-SRY MNT) 180)
> (= (duration SRY-THR MNT) 180)
> (= (duration THR-ISF MNT) 120)
> (= (duration ISF-THR MNT) 120)
> )
> (:goal (and
> (at MOC thr)
> (at JHH thr)
> (at MNT thr)
> (assigned THR-SRY)
> (assigned SRY-THR)
> (assigned THR-ISF)
> (assigned ISF-THR)
> ))
> (:metric minimize (total-cost))
> )
> ------------------------------------------------------------
> -------------------------
>
> Is it possible to use OpenCog planner and Atomese to solve this problem?
>
> Regards,
> Ramin
>
> --
> You received this message because you are subscribed to the Google Groups
> "opencog" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> Visit this group at https://groups.google.com/group/opencog.
> To view this discussion on the web visit https://groups.google.com/d/
> msgid/opencog/CAHmauB6Wh6DEJcF_2KoCSD%2BapWaeJtkKSPCT7%2Bd5K96c_
> tuRnA%40mail.gmail.com
> <https://groups.google.com/d/msgid/opencog/CAHmauB6Wh6DEJcF_2KoCSD%2BapWaeJtkKSPCT7%2Bd5K96c_tuRnA%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
> For more options, visit https://groups.google.com/d/optout.
>
--
*"The problem is not that artificial intelligence will get too smart and
take over the world," computer scientist Pedro Domingos writes, "the
problem is that it's too stupid and already has." *
--
You received this message because you are subscribed to the Google Groups
"opencog" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/opencog.
To view this discussion on the web visit
https://groups.google.com/d/msgid/opencog/CAHrUA36wEGB3B7cdn9AuDbdL77PRD8qpnZPVqbPSrAtm3t%3DsVA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
