Tuesday, March 18, 2008

Why is this still a problem?

What is the main problem in doing an analysis on the ruleset before the planner gets to work to determine which constraints are reasonable to disregard during the planning process? Does it make programming the ruleset too hard up front? The number of available resources has to be defined anyway right? So the only extra work is providing an estimation of the usage of each resource or an estimation of its availability. If there's 10 taxi in the city you have an impression that you won't be able to find one because more than 10 people use a taxi in an your travel window to get from place to place. In a more cognitively plausible sense we just have an impression that taxi's will be available from past experience.

If it is unreasonable to expect someone to tell us this availability information directly there is still easy work that could be done. There are easy cases that could be taken care of up front. In the blocks world example, if the world has four arms, and you only have 3 blocks, its evident enough that the number of arms aren't a restriction and so this responsibility can be passed on to the scheduler.

In a more realistic project planning example you could create a graphplan for a few levels deep and count the number of actions that are done in parallel on each level and compare this to resource availability to determine which constraints are unnecessary. Using this information you could change the domain on the planner side to be simpler and then proceed using whatever method you wish from there.

So, why is this concept at the forefront of research? There seem to be obvious places to make initial progress, I would think it would be standard in implementations by now.


Kartik said...

I don't know if discrete resource usage will be a problem, but modelling the usage and/or production of continuous resources has and continues to be a problem for most implemented (non-vapourware) systems. Even if you have resource profiles, if the interacting resources are continuous, you are forced to consider branching over dense time to find an optimal (and sometimes just *a*) solution.

This is somewhat analogous to the problem of branching over dense-time when it comes to action start-points; as Dave Smith's paper points out, ZENO manages to reason with derivatives, but it has its own restrictions on interacting actions.

It is precisely the cognitively plausible information that is the hardest to give to the planner/system in a way that it can use to cut down its search and reasoning. Just as it seems true that there are obvious places to make progress, it is equally true that very few implemented planning systems even reason about these kinds of resource profiles etc., mostly because it would make them unbearably slow.

Tuan A. Nguyen said...
This comment has been removed by the author.
Tuan A. Nguyen said...

Hi Mike,

Some of my thoughts about your interesting questions: If we roughly consider resources as preconditions of actions, how to separate planning and scheduling (i.e what you mentioned about disregarding constraints) is related to how to do planning with abstraction strategies. An ideal abstraction hierarchy is one such that we can refine a/an (abstract) plan P (found by the planner) to a more concrete one P' (found by the scheduler with new assigning actions supporting resource requirement in P) without violating any ordering constraints posed in P (this is what Knobblock called "ordered monotonicity property" in his paper about abstraction). The problem is that such abstraction hierarchy does not exist in general for all problems (what we shortly mentioned in class is backtracking to find another plan).

Moreover, I think the scenarios in scheduling is even more complicated, since the resources, while can be considered as preconditions of actions, could be affected/shared by/with another actions. In my view, this in turn raises another similar difficult issues in planning: goal interactions, which not only affects the quality of the schedule (as quality of plan in planning) but the correctness of the plan (as an input to the scheduler) as well.