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).
into
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).
...
vessel(hamburg).
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).
vessel(london).
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
call(
( container(hamburg, gas, 1).
vessel(hamburg). ) ?- vessel(Location)
)
results in
Location=hamburg
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 vardb_trans.pl
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/vardb_trans.pl').
:- 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)), !.
state(
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).
vessel(hamburg).
).
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)),
write('\n'),
subtract(InitialState,
[ container(Port, Type, Navailable),
onboard(Type, AlreadyOnboard) ],
UpdatedState),
TerminalState = (
container(Port, Type, NavailableNew).
onboard(Type, NewOnboard).
UpdatedState).
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)),
write('\n'),
subtract(InitialState,
[ onboard(Type, NType), container_wanted(Port, Type, Nwanted) ],
UpdatedState),
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),
desired_state_reached(State).
solve(InitialState, FinalState) :-
call(InitialState ?- vessel(From)), !,
(pickup(From, InitialState, IntermediateStateA) ;
IntermediateStateA = InitialState),
(pickup(From, IntermediateStateA, IntermediateStateB) ;
IntermediateStateB = IntermediateStateA),
route(From, To),
subtract(IntermediateStateB,
[ 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:
state(InitialState),
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.