
| Problem   | #blocks   | min. #moves (=#steps)   | upper bound #steps   | DLVK   | DLVK   |        |        |
|-----------|-----------|-------------------------|----------------------|--------|--------|--------|--------|
| P0        | 6         | 5                       | 6                    | 0.48s  | 0.29s  | 4.65s  | 21.45s |
| P1        | 4         | 4                       | 4                    | 0.05s  | 0.08s  | 3.02s  | 0.13s  |
| P2        | 5         | 6                       | 7                    | 0.24s  | 0.27s  | 4.02s  | 8.44s  |
| P3        | 8         | 8                       | 10                   | 25.32s | 2.33s  | 10.07s | -      |
| P4        | 11        | 9                       | 16                   | -      | 8.28s  | 27.19s | -      |
| P5        | 11        | 11                      | 16                   | -      | 12.63s | 32.27s | -      |

Table 1: Sequential Blocks World - shortest plans

| Problem   | #blocks   | #steps(fixed)   | min. #moves   | DLVK   |
|-----------|-----------|-----------------|---------------|--------|
| P0        | 6         | 2               | 6             | 0.05s  |
| P0        | 6         | 3               | 5             | 0.09s  |
| P1        | 4         | 3               | 4             | 0.04s  |
| P2        | 5         | 5               | 6             | 0.10s  |
| P3        | 8         | 4               | 9             | 0.21s  |
| P4        | 11        | 5               | 13            | 0.81s  |
| P5        | 11        | 7               | 15            | 327s   |

Table 2 shows the execution times for parallel blocks world with fixed plan length where the number of moves is minimized, i.e. problem (α) in Section 5.1. We used the encoding in Figure 2, which generates parallel serializable plans. As CCALC and CMBP do not allow for optimizing other criteria than plan length, we only have results for DLVK here.

Next, Table 3 shows some results for finding a shortest parallel plan, i.e. problem (β) in Section 5.1. First, the minimal possible number of steps is given. We processed each instance (i) using the encoding Pβ from Section 5.1, (ii) without costs by iteratively increasing the plan length and
(iii) using CCALC, by iteratively increasing the plan length until a plan is found. For every result, the number of moves of the first plan computed is reported separately. As CMBP only supports sequential planning, it is not included in this comparison.

Finally, Table 4 shows the results for the combined optimizations (γ) and (δ) for parallel Blocks World as outlined in Section 5.1. The second column again contains the upper bound for the plan Table 3: Parallel Blocks World - shortest plan (β)

| upper bound   | min. #steps   | DLVK   | DLVK inc   | CCALC   |      |       |    |        |
|---------------|---------------|--------|------------|---------|------|-------|----|--------|
| #moves        | time          | #moves | time       | #moves  | time |       |    |        |
| P0            | 6             | 2      | 6          | 0.52s   | 6    | 0.09s | 6  | 4.05s  |
| P1            | 4             | 3      | 5          | 0.07s   | 5    | 0.08s | 4  | 2.95s  |
| P2            | 7             | 5      | 9          | 0.39s   | 9    | 0.21s | 6  | 3.70s  |
| P3            | 10            | 4      | -          | -       | 12   | 0.43s | 9  | 7.69s  |
| P4            | 16            | 5      | -          | -       | 18   | 1.54s | 13 | 20.45s |
| P5            | 16            | 7      | -          | -       | 26   | 3.45s | 15 | 23.22s |
