Difficulty Levels

Difficulty Levels

In the competition, there are three levels of difficulty for MDACI:

1. No numerical powers. At this level, the problem is essentially identical to that of the IPC-4 competition setting: given a faulty power system, the goal is to resupply all lines that can be, if possible in the minimum number of steps. Any plan creating a loop is treated as invalid. To be able to easily rank plans produced by participants, we give them a cost of: 

 

  • nb lines not fed in the final plan state;
  • nb devices in the network;
  • nb plan steps.

 

A plan optimizing that cost feeds all lines that can be fed, and does so in the minimal number of steps possible.

 

Provided a non-trivial analysis, this problem can be solved in polynomial time (Helmert 2006). There is al- ready plenty of scope to illustrate the benefits of a knowledge engineering tool at this level, for instance in facilitating the modeling of the effects of actions (which is non-trivial, see (Hoffmann et al. 2006; Thiebaux, Hoffmann, & Nebel 2005)) and in discovering and exploiting the structure that makes the problem polynomial.

 

2. Power constraints and optimization using the simple cost model. At this level, numerical powers, capacity constraints and all the optimization criteria are taken into account to compute the cost of a plan following the simple cost model defined earlier. Any plan violating the constraints (or creating a loop) is treated as invalid. Here the additional challenge is the modeling of the numerical power propagation, of the constraints and optimization criteria, and the exploitation of the model for constrained optimization. Note that maximizing the number of lines (or merely critical lines) resupplied under the capacity constraints is already NP-hard, regardless of whether a shortest plan is sought (Helmert, personal communication).

 

3. Power constraints and optimization using the sequential cost model. This is as in level 2, but the sequential cost model is used in place of the simple one. It could be argued that, unless intermediate states have costs, the fully observable version of PSR is more a constrained optimization problem than a planning problem. This is due to the facts that, under those assumptions, there is a trivial ordering of actions that guarantee validity (namely perform all openings first) and that the order in which, actions are executed does not affect the cost. This third difficulty level remedies this, making PSR a true sequential optimization problem

Copyright Notice © 2011 MDA Capital Invest, a.s. All rights reserved.