Today I'm studying AIMA's chapter on decision networks and trying to extend Genifer's inference algorithm to cover decisions and planning.
It seems that we need to add 2 new types of nodes to the Bayes net:
1. utility nodes -- these are new
2. decision nodes -- represent possible actions that can be taken
One drawback of this approach noted in AIMA is the lack of advanced planning techniques.
I do not think this is necessarily a drawback. As you may know, I like to cite the example of Graphplan, a planning algorithm which appeared in the late 90s and trumped all the existing special-purpose algorithms by just applying standard constraint satisfaction algorithms to the "plan graph," a translation of the planning problem into a constraint graph. The point is, sometimes there can be a lot to gain by giving up special-purpose algorithms for a problem and falling back on more general methods... especially when the more-general methods are more thoroughly researched.
ReplyDeleteObviously this is not always the case; usually, narrow-purpose algorithms are more efficient. However, I think this is because narrow algorithms are usually only constructed when the narrow domain really is an easier problem. For planning, it is not clear that this is the case! So, it may make sense to just apply more general combinatorial optimization procedures to try and find good plans...
There's also the "deductive planning" idea, of course. Rather than treating planning as a general optimization problem, we might treat it as a general inference problem. I'm still not entirely sure that'll work as hoped for the probabilistic generalization. Deductive planning works on finding constructive existence proofs of a path from A to B (say). For probabilistic existence proofs, though, the best *inference* strategy may not be to look for the highest-confidence single path; it may be to look for a large number of lower-confidence paths. So, good optimization heuristics may be quite different from good inference heuristics.
I also think that, in principle, inference heuristics should be a special case of planning rather than the other way around.
I think planning and inference should be unified, but am not sure how yet.
ReplyDeletePLANGRAPH is actually one of those "advanced planning techniques" that I referred to. A simple decision network is pretty much like a Bayes net, so a simple planning problem is reduced to BN inference. This kind of planning is state-space search, which is the simplest planning technique. PLANGRAPH involves partial-order planning. Another advanced technique is HTN (hierarchical task network). I'm trying to decide on a planning method that can be unified with inference and yet doesn't lose the advantages of those latter techniques.
I'm now more inclined towards your view -- that inference should be a special case of planning rather than the other way round (ie, deductive planning). But this is a new idea I have to think through.
Finally, you talk about "confidence" as if it's a well-defined concept. What do you mean by it? In my mind I'm still uncertain about confidence =)
I just meant probability :P :) In any case, it would be interesting if deductive planning could be made to work... I'm just not sure it will. Mutual recursion between the two is not impossible, either.
ReplyDeleteHey, it's just the ouroboros again: planning can do inference, inference can do planning, planning can do inference...
ReplyDeleteThere is a solution: we need to pick a simple base-case and stick to it, and stop thinking in a loop.
Re confidence: Searching only for high-probability conclusions is definitely not a viable option. Some conclusions are of low probability yet very significant in reasoning. For example: "It is VERY UNLIKELY that a cop will be around here at this time, therefore I double park."
Ouroboros is not necessarily a bad thing, it's just recursive programming. :)
ReplyDeleteIn your example, a low probability is just part of a larger high-probability inference... that doesn't change the idea that we're looking for an overall plan which yields a high probability of a good result.
In any case, I'll think about it.