Hybrid Multi-agent Planning - Multiagent System Technologies - page 26

Ta b l e 2 . Results for the Satellite domain

PLM HMAP
Dependent Independent
Planning Time Planning Time Planning Time Merging Time Total Planning Time Merging Time Total

PANDA

Problem

Satellite-P1 62 60 65 0 65 69 0 69

Satellite-P2 788 708 14 3 17 272 5 277

Satellite-P3 2035 2027 29 7 36 327 26 353

Satellite-P4 - - 42 10 52 342 26 369

Satellite-P5 - - 582 26 608 512 26 539

Satellite-P6 - - 483 19 502 557 26 582

Satellite-P7 - - 473 27 501 593 34 627

Satellite-P8 - - 28 7 35 386 23 409

Satellite-P9 1699 1474 247 0 247 15 0 15

Satellite-P10 3053 3062 356 6 362 26 4 31

Satellite-P11 - - 364 12 376 30 6 36

Satellite-P12 - - 529 9 538 37 7 44

Satellite-P13 - - 820 35 855 52 11 63

Satellite-P14 - - 643 50 693 70 23 93

different primitive ones. We have chosen these domain models because of the prob-
lem characteristics they induce. On the other hand, Satellite problems typically become
difficult when modeling a repetition of observations, which means that a small num-
ber of methods is used multiple times in different contexts of a plan. UM-Translog
problems, on the other hand, typically differ in terms of the decomposition structure,
because specific transportation goods are treated differently, e.g., toxic liquids in trains
require completely different methods than transporting regular packages in trucks. We
consequently defined our experiments on qualitatively different problems by specifying
various transportation means and goods. The number of tasks in the initial plan of these
planning problems ranges from one to six tasks.
Tables 1 and 2 show the runtime behavior of our system in terms of the planning
and merging time (in seconds) consumption for the problems in the UM-Translog and
Satellite domains, respectively. The planning time includes the time of breaking up the
planning problem, the time used to solve sub-problems and the preprocessing time.
Dashes indicate that the plan generation process did not find a solution within the al-
lowed maximum number of seconds and has therefore been

canceled. The column PANDA refers to the reference system behavior [11], the PLM to
the version that performs a preprocessing phase and HMAP to the version that performs
our hybrid MAP. The column HMAP considers clustering the planning problem by two
different clustering techniques Dep and Ind . Our experiments in the UM-Translog and
satellite domains show poor performance (cf. Tables 1 and 2) in PANDA and PLM ver-
sions, as it is difficult to solve planning problems which have a large number of abstract
tasks in the initial plan. The experiments show that, dividing the planning problem into
smaller clusters either by Dep or Ind technique are easier to solve than the original
problem. Consequently, we are able to solve the problems for which the competing sys-
tems could not find a solution within the given resource bounds. For example, for the
UM-Translog problems that have a single abstract task in the initial plan (Translog-P1
to P4) , the average performance improvement of HMAP is about

10 , 000 plans and 18 , 000

in compari-
son with PANDA planner. In those problems, the PLM improves the results by

59%

2%