4.2 Logistics

The task in the logistics domain is to transport several packages from their initial location to their desired destinations. We used a version of the logistics-strips planning domain of the AIPS98 planning competition which we restricted to using only trucks but not planes.¹⁴ The domain is shown in Figure 23. A package is transported from one location to another by loading it into a truck, driving the truck to the destination, and unloading the truck. A truck can load any number of packages. The cost function is the (parallel) time to deliver all packages (measured as the number of operators in the critical path of a plan).

Figure 23: Operators for Logistics

(define (operator LOAD-TRUCK) :parameters (?obj ?truck ?loc) :precondition (:and (obj ?obj) (truck ?truck) (location ?loc) (at ?truck ?loc) (at ?obj ?loc)) :effect (:and (:not (at ?obj ?loc)) (in ?obj ?truck)))	(define (operator UNLOAD-TRUCK) :parameters (?obj ?truck ?loc) :precondition (:and (obj ?obj) (truck ?truck) (location ?loc) (at ?truck ?loc) (in ?obj ?truck)) :effect (:and (:not (in ?obj ?truck)) (at ?obj ?loc)))
(define (operator DRIVE-TRUCK) :parameters (?truck ?loc-from ?loc-to ?city) :precondition (:and (truck ?truck) (location ?loc-from) (location ?loc-to) (city ?city) (at ?truck ?loc-from) (in-city ?loc-from ?city) (in-city ?loc-to ?city)) :effect (:and (:not (at ?truck ?loc-from)) (at ?truck ?loc-to)))

We compare three planners on this domain:

IPP:

IPP [52] produces optimal plans in this domain.

Initial:

The initial plan generator picks a distinguished location and delivers packages one by one starting and returning to the distinguished location. For example, assume that truck t1 is at the distinguished location l1, and package p1 must be delivered from location l2 to location l3. The plan would be: drive-truck(t1 l1 l2 c), load-truck(p1 t1 l2), drive-truck(t1 l2 l3 c), unload-truck(p1 t1 l3), drive-truck(t1 l3 l1 c). The initial plan generator would keep producing these circular trips for the remaining packages. Although this algorithm is very efficient it produces plans of very low quality.

PbR:

PbR starts from the plan produced by Initial and uses the plan rewriting rules shown in Figure 24 to optimize plan quality. The loop rule states that driving to a location and returning back immediately after is useless. The fact that the operators must be adjacent is important because it implies that no intervening load or unload was performed. In the same vein, the triangle rule states that it is better to drive directly between two locations than through a third point if no other operation is performed at such point. The load-earlier rule captures the situation in which a package is not loaded in the truck the first time that the package's location is visited. This occurs when the initial planner was concerned with a trip for another package. The unload-later rule captures the dual case. PbR applies a first improvement search strategy with only one run (no restarts).

Figure 24: Logistics Rewriting Rules

(define-rule :name loop :if (:operators ((?n1 (drive-truck ?t ?l1 ?l2 ?c)) (?n2 (drive-truck ?t ?l2 ?l1 ?c))) :links ((?n1 ?n2)) :constraints ((adjacent-in-critical-path ?n1 ?n2))) :replace (:operators (?n1 ?n2)) :with NIL)	(define-rule :name triangle :if (:operators ((?n1 (drive-truck ?t ?l1 ?l2 ?c)) (?n2 (drive-truck ?t ?l2 ?l3 ?c))) :links ((?n1 ?n2)) :constraints ((adjacent-in-critical-path ?n1 ?n2))) :replace (:operators (?n1 ?n2)) :with (:operators ((?n3 (drive-truck ?t ?l1 ?l3 ?c)))))
(define-rule :name load-earlier :if (:operators ((?n1 (drive-truck ?t ?l1 ?l2 ?c)) (?n2 (drive-truck ?t ?l3 ?l2 ?c)) (?n3 (load-truck ?p ?t ?l2))) :links ((?n2 ?n3)) :constraints ((adjacent-in-critical-path ?n2 ?n3) (before ?n1 ?n2))) :replace (:operators (?n3)) :with (:operators ((?n4 (load-truck ?p ?t ?l2))) :links ((?n1 ?n4))))	(define-rule :name unload-later :if (:operators ((?n1 (drive-truck ?t ?l1 ?l2 ?c)) (?n2 (unload-truck ?p ?t ?l2)) (?n3 (drive-truck ?t ?l3 ?l2 ?c))) :links ((?n1 ?n2)) :constraints ((adjacent-in-critical-path ?n1 ?n2) (before ?n2 ?n3))) :replace (:operators (?n2)) :with (:operators ((?n4 (unload-truck ?p ?t ?l2))) :links ((?n3 ?n4))))

Figure 25: Experimental Results: Logistics, Scaling the Number of Packages

We compared the performance of IPP, Initial, and PbR on a set of logistics problems involving up to 50 packages. Each problem instance has the same number of packages, locations, and goals. There was a single truck and a single city. The performance results are shown in Figure 25. In these graphs each data point is the average of 20 problems for each given number of packages. All the problems were satisfiable. IPP could only solve problems up to 7 packages (it also solved 10 out of 20 for 8 packages, and 1 out of 20 for 9 packages, but these are not shown in the figure). Figure 25(a) shows the average planning time. Figure 25(b) shows the average cost for the 50 packages range. The results are similar to the previous experiment. Initial is efficient but highly suboptimal. PbR is able to considerably improve the cost of these plans and approach the optimal.