Planning container shipping using Prolog
This is a simple demo using Prolog to solve a toy example problem for constraint solving. The goal is as follows: given an initial situation with four ports having containers with various freights, and having demands for those freights at other ports, find a sequence of actions for a vessel that will satisfy those demands, by moving containers to other ports, with the vessel able to transport up to 2 containers at a time.
Representing a state in Prolog is easy. We choose the following Prolog clause representation to capture our initial state:
container(hamburg, gas, 1).
container(hamburg, toys, 1).
container(rotterdam, fruit, 2).
container(rotterdam, cheese, 1).
container(lehavre, coffee, 1).
container(lehavre, wheat, 2).
container(london, meat, 1).
container(london, cocoa, 2).
container_wanted(hamburg, cheese, 1).
container_wanted(hamburg, wheat, 1).
container_wanted(rotterdam, coffee, 1).
container_wanted(rotterdam, toys, 1).
container_wanted(lehavre, meat, 1).
container_wanted(lehavre, cocoa, 1).
container_wanted(london, gas, 1).
container_wanted(london, fruit, 1).
onboard(fruit, 0).
onboard(coffee, 0).
onboard(gas, 0).
onboard(cocoa, 0).
onboard(toys, 0).
onboard(cheese, 0).
onboard(wheat, 0).
onboard(meat, 0).
route(hamburg, london).
route(hamburg, rotterdam).
route(london, lehavre).
route(rotterdam, hamburg).
route(lehavre, rotterdam).
vessel(hamburg).
These Prolog predicates express rules for atoms like
hamburg
, which in Prolog are represented by names starting
with a lowercase letter. We intend the rules to mean
container(hamburg, gas, 1). ...
there's one
gas
and onetoys
container located inhamburg
, twofruit
containers and onecheese
container located inrotterdam
, and so on,
container_wanted(hamburg, cheese, 1). ...
there's demand for a
cheese
container and awheat
container inhamburg
, and there's demand for acoffee
and atoys
container inrotterdam
, and so on,
onboard(..., 0).
there's currently no container of any type loaded,
route(X, Y)
we allow our vessel to travel from Hamburg to London, from London to Le Havre, and so on,
vessel(hamburg).
our vessel is located in Hamburg currently.
Loading this clause database into a Prolog engine, we can ask queries about it. For example, instructing Prolog to execute the query
Run in browser?- vessel(Port)
will tell us about the current location of our vessel:
{"Port" : "hamburg"}
The result, when run with Quantum Prolog on this web site,
will be returned as JSON, mapping our Port
query
variable to the value(s) Prolog found.
A traditional Prolog command-line application will answer
Port = hamburg
instead, as does Quantum Prolog when run natively on a computer rather than in the browser.
Here, we're using a Prolog variable (any word starting
with an uppercase letter or the underscore letter), and Prolog
attempts to find a matching clause in the database for
vessel(X)
, then binds the corresponding argument
of the found clause to the Port
variable.
We can also instruct Prolog to query multiple solutions.
For example, the following query for requesting the type
and number of containers in Hamburg will return two variable
binding pairs for the respective container
clauses
in our database, if we let Prolog fetch two solutions by
clicking "Next Solution"):
?- container(hamburg, What, HowMany)
What = gas, HowMany = 1
What = toys, HowMany = 1
Finally, if no variables (only atoms) appear at all
in our query, Prolog merely responds with true
or fail
, depending on whether what we're
checking is or isn't known to be true, respectively.
When run in the browser, the JSON result representing
true
is the empty object {}
, and a fail
Prolog
response is reported by a no result (a null
return
value), and thus not shown at all.
?- container(hamburg, gas, 1)
yes
Using backtracking to find loading plans
Based on our definitions so far, we can already sketch a query to make Prolog figure out the steps needed to choose a container of a suitable type at our start harbor that we could ship to another directly reachable harbor where the respective freight is in demand:
Run in browser?- vessel(Port),
container(Port, Type, _),
route(Port, NextPort),
container_wanted(NextPort, Type, _)
We're combining several goals into a conjunction using the comma operator here, meaning we expect Prolog to satisfy all these conditions simultaneously:
vessel(Port)
we start again by fetching the current harbor of our vessel, binding
hamburg
to thePort
variable,
container(hamburg, Type, _)
then query a container in stock at that port; as we've already seen above, Prolog chooses the first
container(...)
clause and bindsgas
toType
; the third parameter tocontainer()
is an underscore, interpreted as anonymous variable Prolog doesn't bind any value to
route(hamburg, NextPort)
similarly, Prolog finds
route(hamburg, london)
as the first matching clause forroute()
container_wanted(london, gas, _)
the
gas
container we picked in Hamburg happens to be in demand in London, and Prolog can complete the compound query answering
{"Port" : "hamburg", "Type" : "gas", "NextPort" : "london"}
Now that's the happy path, but what happens if Prolog
at any point doesn't find a suitable matching clause?
We can simulate this by assuming there's no demand for gas
in London, removing
container_wanted(london, gas, 1).
from our clause database. The query we're asking Prolog to satisfy remains the same as before:
Run in browser?- vessel(Port),
container(Port, Type, _),
route(Port, NextPort),
container_wanted(NextPort, Type, _)
What Prolog is doing here when noticing container_wanted(london, gas, _)
isn't satisfiable is to reconsider clauses chosen previously,
a process known as backtracking:
In this case, Prolog first re-executes route(hamburg, NextPort)
,
finding route(hamburg, rotterdam)
as alternative. With rotterdam
bound to NextPort
, Prolog then fails to find
container_wanted(rotterdam, gas, _)
in the next step, so
Prolog further attempts alternatives, going all the way back to choosing
a different type of container to pickup at the starting harbor. Finding
container(hamburg, toys, 1)
as alternative container,
Prolog then proceeds to attempt to ship to London
again, only to find out that toys
aren't in demand. Then,
analogously to before, Prolog attempts to re-execute
route(hamburg, NextPort)
, where rotterdam
is found
as alternative to london
. Finally, since
container_wanted(rotterdam, toys, _)
can be satisfied,
Prolog succeeds, answering
{"Port" : "hamburg", "Type" : "toys", "NextPort" : "rotterdam"}
Finding loading plans with multiple stops
With a rough idea what to do, we now want to extend our solution such that it will be able to find a sequence of pickup/ship/discharge actions for stops at multiple harbors.
Since our queries rely on the predicates container()
and container_wanted()
to report up-to-date figures
for the respective quantities, and also on vessel()
to
tell us the current location of our vessel,
we're going to have to modify clauses for those predicates
in our database during the course of the Prolog program to
reflect changed state once we've picked up or
discharged containers.
To this end, Prolog allows dynamic creation and removal
of clauses using the assertz()
and retract()
predicates. For example,
retract(vessel(hamburg))
removes the
vessel(hamburg)
clause from the database, and
assertz(vessel(london))
adds a new
vessel(london)
clause to the database.
We're going to use retract()
and assertz()
on container()
and container_wanted()
clauses
with decremented and incremented values for the
respective quantities. In Prolog, we can perform arithmetic
operations using the is
predicate: for example,
a goal X is 1 + 2
will bind the value 3
to X
.
With dynamically updated container()
and container_wanted()
clauses now potentially reporting a value of zero for the
respective quantity, we can no longer rely on merely
querying those predicates and ignoring actual bound values
like we did above using anonymous variables. Instead, we
must check the bound value and calculate figures
for the number of containers currently loaded, and
for the number of containers in stock or in demand
at a port. Below, we're somewhat verbosely doing this
by querying onboard()
goals individually for every
freight type, and then summing up the numbers obtained.
For the sake of simplicity, we keep on doing this here,
but in a realistic Prolog program, we'd be using more
compact Prolog code employing findall()
and similar
predicates able to query all onboard()
solutions in
a single invocation.
We're now going to define action predicates that we can perform to
change state. An action here will just represent the loading of
a single container (pickup
) of a freight type that's being
on stock at our current harbor, to be followed by traveling
to another port, to be followed by unloading a single container
(discharge
) of a freight type in demand at that other port.
We're using Prolog commenting syntax here to document the individual
parts of our rule: everything following after the percent-sign %
until the end of the line is ignored by Prolog:
pickup(Port) :-
% ensure that no more than 2 containers
% are loaded at any time
onboard(fruit, Nfruit),
onboard(coffee, Ncoffee),
onboard(gas, Ngas),
onboard(cocoa, Ncocoa),
onboard(toys, Ntoys),
onboard(wheat, Nwheat),
onboard(cheese, Ncheese),
onboard(meat, Nmeat),
Nall is Nfruit + Ncoffee + Ngas + Ncocoa
+ Ntoys + Nwheat + Ncheese + Nmeat,
Nall < 3,
% choose a container at the current port
container(Port, Type, Navailable),
Navailable > 0,
% calculate new available and onboard
% figures after our pickup action
onboard(Type, AlreadyOnboard),
AlreadyOnboard < 2,
NavailableNew is Navailable - 1,
NewOnboard is AlreadyOnboard + 1,
!,
% write out our pickup action
write('PICKUP'(Type, Port)),
write('\n'),
% change state: replace old container() and
% onboard() clauses by new ones reflecting
% the state after our pickup action
retract(container(Port, Type, Navailable)),
assertz(container(Port, Type, NavailableNew)),
retract(onboard(Type, AlreadyOnboard)),
assertz(onboard(Type, NewOnboard)).
Likewise, we define a discharge()
predicate to
represent a discharge action:
discharge(Port) :-
% choose any container loaded onto our vessel
% and check if it's in demand at the current port
onboard(Type, NType),
NType > 0,
container_wanted(Port, Type, Nwanted),
Nwanted > 0,
NewWanted is Nwanted - 1,
NewOnboard is NType - 1,
!,
% write out our unloading action
write('DISCHARGE'(Type, Port)),
write('\n'),
% change state: replace old container_wanted() and
% onboard() clauses by new ones reflecting
% the state after our discharge action
retract(container_wanted(Port, Type, Nwanted)),
assertz(container_wanted(Port, Type, NewWanted)),
retract(onboard(Type, NType)),
assertz(onboard(Type, NewOnboard)).
Like before, Prolog employs backtracking for satisfying the portion
container(Port, Type, Navailable),
Navailable > 0,
...
in pickup/1
: Prolog tries the first known container/3
state fact and binds the Type
variable with a freight
type such as gas
and the Navailable
variable
with the number of containers of that freight type at the current
port, then proceeds to the next conjunct Navailable > 0
. At that
point, it rejects (Port
, Type
) bindings where Navailable
is 0
and automatically re-attempts to fulfill previous goals,
starting with the immediately preceding container(Port, Type, Navailable)
goal to obtain an alternative binding for the container
Type
and Navailable
count for that Type
at the port.
Backtracking is also performed in discharge/1
:
onboard(Type, NType),
NType > 0,
container_wanted(Port, Type, Nwanted),
Nwanted > 0,
...
Here, Prolog binds a container loaded onto the vessel
using onboard/2
, then checks to see if a container
of that freight type is in demand at the current
port. If it isn't, it picks another container according to
onboard/2
and re-checks if, according to container_wanted/3
,
that other container freight type is in demand, and so on,
until it finds a satisfying container type, or fails completely.
Code following that portion is only ever entered if a
satisfying assignment to Type
, NType
, and Nwanted
is achieved; Prolog carries out backtracking implicitly.
Note the !
exclamation mark operator after we've
determined a container to pickup or discharge, respectively.
This is Prolog's cut operator: it makes evaluation of
the current Prolog predicate not reconsider earlier alternative
choice points, limiting backtracking to everything appearing
after the cut. We do this since we're updating our
database states using retract
(to remove the argument clause
from the database) and assertz
(to add the argument clause
to the database) after this point, so we couldn't go back to an
earlier choice point using regular backtracking anyway,
since assertz()
and retract()
are changing the database
permanently.
Effectively, we're employing a so-called committed choice strategy here, meaning that after everything that comes before the cut can be satisfied, we're sticking to that choice. For this reason, our program can't find an "optimal" routing for our vessel; it can at best find the first satisfiable one.
Now to conclude our small example, we just need to implement
a simple generate-and-test cycle where up to two pickup
actions
are considered, followed by traveling to another port
according to route/2
, followed by up to two discharge
actions:
solve :-
% determine the whereabouts of our vessel
vessel(From),
% allow up to two pickup actions;
% the '; true' part will make Prolog
% skip the action alltogether
% if it can't be satisfied
(pickup(From) ; true),
(pickup(From) ; true),
% pick a port to travel to,
% and reflect our choice of port
% by updating the Prolog database
route(From, To),
retract(vessel(From)),
assertz(vessel(To)),
% now allow one or two discharge actions
% at the destination port
discharge(To),
( discharge(To) ; true),
% recursively plan our next
% pickup-ship-discharge cycle
solve.
We allow any single, or all pickup
/discharge
actions
to be omitted in case there are no more containers to pickup
at a port, or not all containers being shipped are in
demand at the current port. At the end, we then recursively call
our solve
predicate, now operating on the changed state
as initial state.
So that we know when to stop the program, we're going to need an additional predicate to check if our current state satisfies our desired state. This is as simple as
desired_state_reached :-
container_wanted(hamburg, cheese, 0),
container_wanted(hamburg, wheat, 0),
container_wanted(rotterdam, coffee, 0),
container_wanted(rotterdam, toys, 0),
container_wanted(lehavre, meat, 0),
container_wanted(lehavre, fruit, 0),
container_wanted(london, gas, 0),
container_wanted(london, cocoa, 0).
which checks whether all demands expressed through
container_wanted()
predicates are at 0, that is, have been
met. Like our pickup()
and discharge()
action predicates,
this takes the form of a Prolog rule as opposed
to the facts we've used for representing the state itself.
A rule such as desired_state_reached
is satisfied if all the
conjuncts in its body (the terms separated by commas
following after the :-
operator) can be satisfied.
We need to add an additional solve
clause before our main
solve
clause such that the program terminates as soon as
we've found a state (and corresponding sequence of actions)
that satisfies our desired state. This solve
clause is
invoked by recursive invocations from solve
itself
as the last conjunct, and will stop Prolog from running
into our main solve
clause once desired_state_reached
is true:
solve :-
desired_state_reached, !.
To now run the program, we simply invoke solve
like this:
?- solve
The program will output our pickup and discharge actions
as these are taken, and as instructed to do so via our
write/1
invocations, and finally answering with yes
in response to our ?- solve
main query which doesn't
bind any variables:
PICKUP: gas hamburg
PICKUP: toys hamburg
DISCHARGE: gas london
PICKUP: meat london
PICKUP: cocoa london
DISCHARGE: meat lehavre
DISCHARGE: cocoa lehavre
PICKUP: coffee lehavre
PICKUP: wheat lehavre
DISCHARGE: toys rotterdam
DISCHARGE: coffee rotterdam
PICKUP: fruit rotterdam
PICKUP: cheese rotterdam
DISCHARGE: wheat hamburg
DISCHARGE: cheese hamburg
DISCHARGE: fruit london
1: yes
Note to run this program in the browser, we
need to add a write()
predicate, since the browser
version of Quantum Prolog lacks any form of I/O.
We're implementing write(Msg)
by appending to
an atom retrieved using messages()
we keep
up-to-date as new write()
goals are invoked
using the built-in atom_concat()
predicate:
messages('').
write(Msg) :-
retract(messages(M0)),
atom_concat(M0, Msg, M1),
assertz(messages(M1)).
In our top-level query, after having invoked solve
,
we then query messages()
such that the accumulated
message buffer is bound to a Message
variable for
display. While the output appears a bit messed up
compared to regular Prolog write()
, we can still
see the list of actions our program found:
{"Messages" :
"PICKUP: gas hamburg\n
PICKUP: toys hamburg\n
DISCHARGE: gas london\n
PICKUP: meat london\n
PICKUP: cocoa london\n
DISCHARGE: meat lehavre\n
DISCHARGE: cocoa lehavre\n
PICKUP: coffee lehavre\n
PICKUP: wheat lehavre\n
DISCHARGE: toys rotterdam\n
DISCHARGE: coffee rotterdam\n
PICKUP: fruit rotterdam\n
PICKUP: cheese rotterdam\n
DISCHARGE: wheat hamburg\n
DISCHARGE: cheese hamburg\n
DISCHARGE: fruit london\n"}
The final load planning program
For reference, here's the complete container planning
program, also including :- dynamic
directives needed
for allowing state representation predicates to be removed
and asserted dynamically:
:- dynamic(container/3).
:- dynamic(container_wanted/3).
:- dynamic(onboard/2).
:- dynamic(vessel/1).
:- dynamic(messages/1).
container(hamburg, gas, 1).
container(hamburg, toys, 1).
container(rotterdam, fruit, 2).
container(rotterdam, cheese, 1).
container(lehavre, coffee, 1).
container(lehavre, wheat, 2).
container(london, meat, 1).
container(london, cocoa, 2).
container_wanted(hamburg, cheese, 1).
container_wanted(hamburg, wheat, 1).
container_wanted(rotterdam, coffee, 1).
container_wanted(rotterdam, toys, 1).
container_wanted(lehavre, meat, 1).
container_wanted(lehavre, cocoa, 1).
container_wanted(london, gas, 1).
container_wanted(london, fruit, 1).
onboard(fruit, 0).
onboard(coffee, 0).
onboard(gas, 0).
onboard(cocoa, 0).
onboard(toys, 0).
onboard(cheese, 0).
onboard(wheat, 0).
onboard(meat, 0).
route(hamburg, london).
route(hamburg, rotterdam).
route(london, lehavre).
route(rotterdam, hamburg).
route(lehavre, rotterdam).
vessel(hamburg).
pickup(Port) :-
% ensure that no more than 2 containers
% are loaded at any time
onboard(fruit, Nfruit),
onboard(coffee, Ncoffee),
onboard(gas, Ngas),
onboard(cocoa, Ncocoa),
onboard(toys, Ntoys),
onboard(wheat, Nwheat),
onboard(cheese, Ncheese),
onboard(meat, Nmeat),
Nall is Nfruit + Ncoffee + Ngas + Ncocoa
+ Ntoys + Nwheat + Ncheese + Nmeat,
Nall < 3,
% choose a container at the current port
container(Port, Type, Navailable),
Navailable > 0,
% calculate new available and onboard
% figures after our pickup action
onboard(Type, AlreadyOnboard),
AlreadyOnboard < 2,
NavailableNew is Navailable - 1,
NewOnboard is AlreadyOnboard + 1,
!,
% write out our pickup action
write('PICKUP: '), write(Type), write(' '), write(Port),
write('\n'),
% change state: replace old container() and
% onboard() clauses by new ones reflecting
% the state after our pickup action
retract(container(Port, Type, Navailable)),
assertz(container(Port, Type, NavailableNew)),
retract(onboard(Type, AlreadyOnboard)),
assertz(onboard(Type, NewOnboard)).
discharge(Port) :-
% choose any container loaded onto our vessel
% and check if it's in demand at the current port
onboard(Type, NType),
NType > 0,
container_wanted(Port, Type, Nwanted),
Nwanted > 0,
NewWanted is Nwanted - 1,
NewOnboard is NType - 1,
!,
% write out our unloading action
write('DISCHARGE: '), write(Type), write(' '), write(Port),
write('\n'),
% change state: replace old container_wanted() and
% onboard() clauses by new ones reflecting
% the state after our discharge action
retract(container_wanted(Port, Type, Nwanted)),
assertz(container_wanted(Port, Type, NewWanted)),
retract(onboard(Type, NType)),
assertz(onboard(Type, NewOnboard)).
desired_state_reached :-
container_wanted(hamburg, cheese, 0),
container_wanted(hamburg, wheat, 0),
container_wanted(rotterdam, coffee, 0),
container_wanted(rotterdam, toys, 0),
container_wanted(lehavre, meat, 0),
container_wanted(lehavre, cocoa, 0),
container_wanted(london, gas, 0),
container_wanted(london, fruit, 0).
solve :-
desired_state_reached, !.
solve :-
% determine the whereabouts of our vessel
vessel(From),
% allow up to two pickup actions;
% the '; true' part will make Prolog
% skip the action alltogether
% if it can't be satisfied
(pickup(From) ; true),
(pickup(From) ; true),
% pick a port to travel to,
% and reflect our choice of port
% by updating the Prolog database
route(From, To),
retract(vessel(From)),
assertz(vessel(To)),
% now allow one or two discharge actions
% at the destination port
discharge(To),
( discharge(To) ; true),
% recursively plan our next
% pickup-ship-discharge cycle
solve.
messages('').
write(Msg) :-
retract(messages(M0)),
atom_concat(M0, Msg, M1),
assertz(messages(M1)).
?- solve, messages(Messages), !