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 one toys container located in hamburg, two fruit containers and one cheese container located in rotterdam, and so on,

container_wanted(hamburg, cheese, 1). ...

there's demand for a cheese container and a wheat container in hamburg, and there's demand for a coffee and a toys container in rotterdam, 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

?- 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:

?- 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 the Port 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 binds gas to Type; the third parameter to container() 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 for route()

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:

?- 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), !