MOSES Based Planning

From OpenCog

This post describes an approach to planning that would leverage Shujing's work on modifying GraphPlan for OpenCog, plus Jade's work on simple planning and temporal reasoning in PLN … but incorporating both of these in a more powerful plan-learning framework.

An underlying concept here is that:

  • Planning should ultimately be done in OpenCog as a case of more general learning, rather than having a specialized planning algorithm.
  • However, it may also be valuable to maintain a specialized planning-focused data structure to guide general learning mechanisms toward more efficient learning in a planning context.

This may sound a bit contradictory; but I hope it will sound less so once you've read the details of the following.

The basic approach I suggest is

  • use MOSES for the core plan learning algorithm. That is, MOSES would maintain a population of "candidate partial plans", and evolve this population in an effort to find effective complete plans.
  • use PLN to help in the fitness evaluation of candidate partial plans. That is, PLN would be used to estimate the probability that a partial plan can be extended into a high-quality complete plan.
  • use a GraphPlan-style planning graph, to record information about candidate plans, and to propagate information about mutual exclusion between actions. The planning graph would be used to help guide both MOSES and PLN.

Note that MOSES already has a scalable, multi-processor, multi-machine implementation. So unless the algorithmic inefficiency of this approach is extreme, its practical efficiency should be able to be made acceptable.

One can think of this as being a bit like PGraphPlan, except that

  • MOSES is being used in place of forward or backward chaining search, enabling a more global search of the plan space (mixing forward and backward learning freely)
  • PLN is being used to estimate the value of partial plans, replacing heuristic methods of value propagation

Regarding PLN, we would want to [explicitly, or in effect] create a special API function looking something like

EstimateSuccessProbability(PartialPlan PP, Goal G) 

(assuming the goal statement contains information about the time allotted to achieve the goal). Of course, such a function could be used within many non-MOSES approaches to planning also.

Put simply, the estimation of the success probability is "just" a matter of asking the PLN backward-chainer to figure out the truth value of a certain ImplicationLink, i.e.

PredictiveImplication (do PP) G [time-lag T] 

But of course, this may be a very difficult inference without some special guidance to help the backward chainer. The GraphPlan-style planning graph could be used by PLN to guide it in doing the inference, via telling it what variables to look at, in doing its inferences. This sort of reasoning also requires PLN to have a fairly robust capability to reason about time intervals and events occurring therein (i.e., basic temporal inference).

Regarding MOSES, given a candidate plan, it could look into the planning graph to aid with program tree expansion. That is, given a population of partial plans, MOSES would progressively add new nodes to each plan, representing predecessors or successors to the actions already described in the plans. In choosing which nodes to add, it could be probabilistically biased toward adding nodes suggested by the planning graph.

So, overall what we have is an approach to doing planning via MOSES, with PLN for fitness estimation -- but using a GraphPlan-style planning graph to guide MOSES's exploration of the neighborhood of partial plans, and to guide PLN's inferences regarding the success likelihood of partial plans.

I think this is at least *a* "right" way to do planning within OpenCog. I realize this sort of thing is a lot of work to implement. But I think it's quite do-able. I also think that, as folks implement other, simpler planning algorithms for (important) short-term reasons, it may pay to keep in mind the possibility of the approach described here being taken in the medium term.