Project IFT702

Performance Analysis with Metric-FF



More we add tasks in the goals list, more planner takes time and memory to resolve the problem. For the Scientific Conference domain, it's difficult to plan problem with more than 5 or 6 goals. We identify many sources that may explains inefficiently.

1. Navigation

Navigation is one hypothesis about what could be the bottleneck. An idea to boost planner performance is to add the possibility to navigate to anypoint (the planner don't care about path planning). The idea is to reduce plan-length.

In some case, it's reduce planning time and in other case, it's increase planning time. So, this is not a good solution. With option -E (no enforcement hill-climbing), doing full navigation seems to be always faster.

Test Case
 (planner do navigation)
test?.fct
 (planner don't do navigation)
test?_nav.fct
test1
 0.55
 6.24
test2
 2.30
 8.77
test3
 9.70
 21.37
(Test by Metric-FF without EHC)


2. Time

Doing time scheduling seems to be the main place where the planner spend time to find solution. To verify it, we tried to remove all time constraints (ScientificConf_notime.pddl).

Test Case
 With Time
Scheduling
 Without Time
Scheduling
test1.fct
 0.55
 0.21
test2.fct
 2.30
 0.96
test3.fct
 9.70
 3.78
test4.fct
 (too long)
 56.83
test5.fct
 (too long)
 (too long)
test5_nav.fct
13.90

3. Heuristic of Metric-FF

A reason why Metric-FF have some problems with time scheduling is the way it work. Metric-FF use an heuristic to guide the forward search. The strategy is the same as non-numeric version of FF. The main idea is to take an estimate of plan-length as heuristic. Plan-length can be computed with a GraphPlan relaxed algorithm by ignoring delete list. See our presentation...