On the suboptimality of the Optimal Planning Track at IPC (Comments welcome!)
It is undeniable that the planning competition has been a great influence on the planning community. While most of it has been for the good, there are some mixed blessings..
One case in point is the "Optimality track"--which has been run for the second time this year.
Not only is the way this track is being run profoundly misguided (IMHO), but it also has lead to equally erroneous conclusions (e.g. "optimal planning" = "SAT planning").
The first time it was run, the organizers allowed entrants to choose the optimality metric they want to guarantee (which, if you read "performance metrics 101" is a big no-no!). The obvious effect was that several entrants--especially the bounded-length planners--chose the "easiest for them to ensure" metric--which is the "step-optimality".
Notice that the choice of step-optimality has no compelling justification for classical planning--where the only reasonable metrics are cost-oriented--find the plan with the lowest cumulative action cost ---with "sequential optimality" being the special case when actions have uniform cost. (One usual argument in favor of step-optimality is that it is akin to "make-span" in temporal planning. I don't buy this unless we are actually doing temporal planning benchmarks--which pose a whole slew of additional challenges to bounded length SAT-style planners.)
The second time it was run (which was this year), the organizers let people continue using step optimality as the optimality metric.
The result is that we now have two optimal planning competitions where the performance metric is very hard to justify from the users' point of view, and the winners of the track--the bounded length SAT planners--are arguably only good at step-optimality (that, arguably, no real users would ever care about!).
Other approaches, such as heuristic planners using admissible heuristics, which can actually provide cost-optimal plans, are naturally shut-out, since step-optimal plans can have lengths that are upto a factor of n less than sequential or cost-optimal plans.
This state-of-affairs has been mistakenly interpreted to mean that optimal planning = SAT planning (and Henry Kautz--in his recent AAAI talk--went as far as to suggest that we should all focus on optimal planning, and this means SAT planning is pretty much the way to go..)
Arguably, if the track measures cost-optimality, bounded length planners are not likely to have that much of a performance edge. This is because the performance of bounded length planners such as SAT depends crucially on the length of the encoding over which they need to search. With sequential optimality, they will have to search increasingly larger sized encodings. With cost-optimality, they would have to do branch-and-bound search at each encoding level.
I think it is time optimal track focused on optimality metrics that make sense to the users (rather than to the planners). This might in turn let us all focus on novel techniques that really solve the optimal planning problem (rather than lull us into the false complacency that optimal planning can be handled by current SAT planners).
Rao
7/25
---------
One post script. My beef (or carrot--since I am a vegetarian), is not with bounded length planning (which is a great idea), but rather with the way optimality track has been run. I think it is possible for heuristic search and bounded length planners to play complementary roles. Bounded length planners may still be best at showing that plans below a certain cost do not exist, thus providing useful lower bounds.
One case in point is the "Optimality track"--which has been run for the second time this year.
Not only is the way this track is being run profoundly misguided (IMHO), but it also has lead to equally erroneous conclusions (e.g. "optimal planning" = "SAT planning").
The first time it was run, the organizers allowed entrants to choose the optimality metric they want to guarantee (which, if you read "performance metrics 101" is a big no-no!). The obvious effect was that several entrants--especially the bounded-length planners--chose the "easiest for them to ensure" metric--which is the "step-optimality".
Notice that the choice of step-optimality has no compelling justification for classical planning--where the only reasonable metrics are cost-oriented--find the plan with the lowest cumulative action cost ---with "sequential optimality" being the special case when actions have uniform cost. (One usual argument in favor of step-optimality is that it is akin to "make-span" in temporal planning. I don't buy this unless we are actually doing temporal planning benchmarks--which pose a whole slew of additional challenges to bounded length SAT-style planners.)
The second time it was run (which was this year), the organizers let people continue using step optimality as the optimality metric.
The result is that we now have two optimal planning competitions where the performance metric is very hard to justify from the users' point of view, and the winners of the track--the bounded length SAT planners--are arguably only good at step-optimality (that, arguably, no real users would ever care about!).
Other approaches, such as heuristic planners using admissible heuristics, which can actually provide cost-optimal plans, are naturally shut-out, since step-optimal plans can have lengths that are upto a factor of n less than sequential or cost-optimal plans.
This state-of-affairs has been mistakenly interpreted to mean that optimal planning = SAT planning (and Henry Kautz--in his recent AAAI talk--went as far as to suggest that we should all focus on optimal planning, and this means SAT planning is pretty much the way to go..)
Arguably, if the track measures cost-optimality, bounded length planners are not likely to have that much of a performance edge. This is because the performance of bounded length planners such as SAT depends crucially on the length of the encoding over which they need to search. With sequential optimality, they will have to search increasingly larger sized encodings. With cost-optimality, they would have to do branch-and-bound search at each encoding level.
I think it is time optimal track focused on optimality metrics that make sense to the users (rather than to the planners). This might in turn let us all focus on novel techniques that really solve the optimal planning problem (rather than lull us into the false complacency that optimal planning can be handled by current SAT planners).
Rao
7/25
---------
One post script. My beef (or carrot--since I am a vegetarian), is not with bounded length planning (which is a great idea), but rather with the way optimality track has been run. I think it is possible for heuristic search and bounded length planners to play complementary roles. Bounded length planners may still be best at showing that plans below a certain cost do not exist, thus providing useful lower bounds.
posted by Rao | 10:49 AM
|
8 comments
