Advanced combinatorical planning

As an improvement to our basic solution from part 1, we're going to use the vardb feature available with Quantum Prolog for actual combinatorical optimization.

Looking closer at our program, we can see that all it produces is a plan for our vessel to travel counter-clockwise from Hamburg to London, then from there to Le Havre, to Rotterdam, and back to Hamburg again, with a final tour to London, always picking up and discharging whatever container is offered or in demand at the respective harbor. We're forcing this by essentially allowing only that particular moves in our route(From, To) facts. Technically, we also allow our ship to travel from Hamburg to Rotterdam rather than to London first, but this route is never taken since the first route(From, To) chosen (the first route fact in the Prolog program) will pick London, which is already an acceptable destination harbor to discharge something at, and once comiited to that action, our program doesn't consider alternatives anymore.

Our program thus can't deal with the possibility to travel to a destination having containers to discharge and pickup as usual, but then not being able to travel to a further destination where at least a single container can be discharged. We can change our program to run into this situation by merely exchanging the two lines

route(hamburg, london).
route(hamburg, rotterdam).


route(hamburg, rotterdam).
route(hamburg, london).

Now with this change, our program doesn't complete with an acceptable plan anymore, because it considers travelling to Rotterdam first, where it happily discharges toys and picks up fruit and cheese, but then can only travel to Le Havre from there where none of the goods our vessel is carrying at that time (gas, fruit, or cheese) is in demand. Since our program isn't allowed to "do nothing" and travel to another destination, Prolog terminates without reporting success.

Now Prolog can in principle enumerate all combinatorically possible plans relying on backtracking, just as described in part 1 in the context of picking a container type, where Prolog attempts to select a container(Port, Type, N) fact only to reconsider and pick another choice because the number N of containers of the first chosen type was 0, violating the condition that N be greater than 0.

But we've painted ourselves somewhat into a corner here since we've used Prolog's built-in retract/1 and assertz/1 predicates to manage states. retract/1 and assertz/1 work destructively: once we've invoked retract/1, the retracted clause is permanently deleted from Prolog's database, and Prolog can not backtrack (automatically undo) retract/1 executions to restore the Prolog database to its previous state, and same with assertz/1. Hence, once Prolog has taken an action and stored its post-conditions into the database, it can not reconsider that action and choose a different one to arrive at alternative plans.

Sufficienlty complex planning problem formulations for Prolog where an isolated action can't guarantee success of the plan composed of multiple isolated actions have thus avoided using assertz/asserta/retract, and resorted to using ad-hoc state information passed as arguments into and out of action predicates such as our pickup(..) and discharge(...) predicates.

Enter Quantum Prolog's vardb feature, which is a very general and natural way to do just that, by passing Prolog programs themselves, or at least the clauses representing state, into and out of action predicates. For example, where in our regular Prolog we use the following terms as clauses to represent our initial state:

container(hamburg, gas, 1).
container(hamburg, toys, 1).
container(london, meat, 1).
container(london, cocoa, 2).


container_wanted(hamburg, cheese, 1).
container_wanted(hamburg, wheat, 1).
container_wanted(london, gas, 1).
container_wanted(london, fruit, 1).



in a Quantum Prolog Prolog program making use of the vardb feature, we pass exactly the same list of clause-terms as arguments to action predicates, and also have action terms produce an output list of clause-terms representing the state of execution after the action. For example, after having travelled to London and completed discharges and pickups, ready to head towards Le Havre as in our initial example, the state as output term list looks like:

container(hamburg, gas, 0).
container(hamburg, toys, 0).
container(london, meat, 0).
container(london, cocoa, 0).


container_wanted(hamburg, cheese, 1).
container_wanted(hamburg, wheat, 1).
container_wanted(london, gas, 0).
container_wanted(london, fruit, 1).


Our actions now make use of a variant form of regular Prolog callable where the database to query against is explicitly specified, rather than assumed to be the global database that is normally parsed from Prolog code text and/or created dynamically via asserta and assertz.

For example, querying

	( container(hamburg, gas, 1).
	  vessel(hamburg). ) ?- vessel(Location)

results in


Here, (container(hamburg, gas, 1). vessel(hamburg).) is a list of fact-like terms, and vessel(Location) a goal-term, just like in ordinary Prolog programs. However, unlike regular Prolog, Quantum Prolog with the vardb feature enabled can evaluate callables with principal functor '?-'/2 having both the goal and the database to evaluate against specified explicitly.

In particular, both the left (the list-like database of clause-terms) and the right parameter (the callable) can be or contain variables. Note that callables having principal functor '?-'/2 must be wrapped in call/1 predicates to be evaluated, just like regular dynamic callables in ISO Prolog have to. Also, note that the '?-'/2 operator (or functor when used in functional notation) must appear syntactically in the call/1 argument in Prolog source. That is, in a term call(X) (while otherwise valid ISO Prolog), Quantum Prolog will not consider X for vardb evaluation; only call(X ?- Z) appearing syntactically in source will make the vardb feature work. To enable the vardb feature, the source file must be included via the ensure_loaded directive, and the vardb_init goal must be executed via the initialization/1 directive or directly as part of a top-level goal.

Our container planning program converted to make use of the vardb feature looks like this (where we just wrapped our state clauses into the state predicate):

:- dynamic(solve/2).
:- dynamic(pickup/3).
:- dynamic(discharge/3).
:- dynamic(desired_state_reached/1).

% boilerplate to make the vardb feature work
:- ensure_loaded('src/test/prolog/metakb/').
:- initialization(vardb_init).

desired_state_reached(State) :-
	call(State ?- container_wanted(hamburg, cheese, 0)), !,
	call(State ?- container_wanted(hamburg, wheat, 0)), !,
	call(State ?- container_wanted(rotterdam, coffee, 0)),
	call(State ?- container_wanted(rotterdam, toys, 0)), !,
	call(State ?- container_wanted(lehavre, meat, 0)), !,
	call(State ?- container_wanted(lehavre, cocoa, 0)), !,
	call(State ?- container_wanted(london, gas, 0)), !,
	call(State ?- container_wanted(london, fruit, 0)), !.

	container(hamburg, gas, 1).
	container(hamburg, toys, 1).
	container(rotterdam, fruit, 1).
	container(rotterdam, cheese, 1).
	container(lehavre, coffee, 1).
	container(lehavre, wheat, 1).
	container(london, meat, 1).
	container(london, cocoa, 1).

	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).


pickup(Port, InitialState, TerminalState) :-
	call(InitialState ?- onboard(fruit, Nfruit)), !,
	call(InitialState ?- onboard(coffee, Ncoffee)), !,
	call(InitialState ?- onboard(gas, Ngas)), !,
	call(InitialState ?- onboard(cocoa, Ncocoa)), !,
	call(InitialState ?- onboard(toys, Ntoys)), !,
	call(InitialState ?- onboard(wheat, Nwheat)), !,
	call(InitialState ?- onboard(cheese, Ncheese)), !,
	call(InitialState ?- onboard(meat, Nmeat)), !,
	Nall is Nfruit + Ncoffee + Ngas + Ncocoa
		+ Ntoys + Nwheat + Ncheese + Nmeat,
	Nall < 3,
	call(InitialState ?- container(Port, Type, Navailable)),
	Navailable > 0,
	call(InitialState ?- onboard(Type, AlreadyOnboard)),
	AlreadyOnboard < 2,
	NavailableNew is Navailable - 1,
	NewOnboard is AlreadyOnboard + 1,
	write('PICKUP'(Type, Port)),
		[ container(Port, Type, Navailable),
			onboard(Type, AlreadyOnboard) ],
	TerminalState = (
		container(Port, Type, NavailableNew).
		onboard(Type, NewOnboard).

discharge(Port, InitialState, TerminalState) :-
	call(InitialState ?- onboard(Type, NType)),
	NType > 0,
	call(InitialState ?- container_wanted(Port, Type, Nwanted)),
	Nwanted > 0,
	NewWanted is Nwanted - 1,
	NewOnboard is NType - 1,
	write('DISCHARGE'(Type, Port)),
		[ onboard(Type, NType), container_wanted(Port, Type, Nwanted) ],
	TerminalState = (
		container_wanted(Port, Type, NewWanted).
		onboard(Type, NewOnboard). UpdatedState

route(hamburg, london).
route(hamburg, rotterdam).
route(london, lehavre).
route(rotterdam, hamburg).
route(lehavre, rotterdam).

solve(State, State) :-
	\+ var(State),

solve(InitialState, FinalState) :-
	call(InitialState ?- vessel(From)), !,
	(pickup(From, InitialState, IntermediateStateA) ;
		IntermediateStateA = InitialState),
	(pickup(From, IntermediateStateA, IntermediateStateB) ;
		IntermediateStateB = IntermediateStateA),
	route(From, To),
		[ vessel(From) ], IntermediateStateBB),
	IntermediateStateC = (vessel(To). IntermediateStateBB),
	discharge(To, IntermediateStateC, IntermediateStateD),
	( discharge(To, IntermediateStateD, IntermediateStateE) ; IntermediateStateE = IntermediateStateD ),
	solve(IntermediateStateE, FinalState).

And our query against that program can look like this:

    solve(InitialState, TerminalState)

Note that, where in our plain Prolog program our action/state transition predicates used retract() and assertz() to represent the state after the action, manipulating the global Prolog database, in the vardb-variant we pass state into (as InitialState) and out of (TerminalState), respectively, our action predicates, using regular Prolog list manipulation predicates such as subtract(...) and basic term construction (as in TerminalState = (onboard(Type, NewOnboard). UpdatedState)) to form a new state that we're then propagating into the next action predicate.

If we now, as discussed above, exchange route(hamburg, rotterdam) with route(hamburg, london), then we'll see that the vardb variant, in contrast to our regular Prolog program, will find the expected plan to arrive at a state where all demands have been satisfied.

This is specifically due to the vardb program being able to backtrack beyond choosing route(hamburg, london) and try route(hamburg, rotterdam) instead, fully making use of Prolog backtracking, whereas our regular Prolog program can't backtrack in this situation, since it has destructively changed state using retract()/assertz().

Though we're not expanding on this here, I hope you can see that not only can our vardb-using program arrive at a solution at all, it also allows enumerating all possible plans and pick an optimal one, according to some cost function yet to be defined.