Is there a search algorithm for this?

I’m hoping a search algorithm exists for what I want to do, but I just don’t know what it is…

Say I’ve got a tree made from a single root A. I have a bunch of ‘rules’ which can attach little sub-trees to certain existing nodes. Eg. rule 1 might attach to an A node and add children B and C, and rule 2 might attach to C and add E (via D).

My start state is an initial tree (eg. A at root and B, C, D as children) and a bunch of nodes that need to be in the tree (eg. W, X, Y, Z). The required nodes don’t have to be leaves, just in the tree somewhere. I ‘just’ need to figure out the rules needed to expand the first tree into one that satisfies the conditions of the second.

I thought I could use STRIPS ( http://en.wikipedia.org/wiki/STRIPS ) but unfortunately that seems to require some kind of heuristic to drive the internal A* routine, and I don’t think I can actually come up with a workable heuristic in this case. :frowning: So at the moment my only idea is a brute force approach, which is obviously going to be really slow.

Anyone any suggestions? Thanks.

Interesting. What are the variables?

I’m wondering if the starting and destination nodes change, and if the rules change?

Btw what you describe, with adding branches to a tree, sounds like a Lindenmayer system. But that info is not that helpful to your search problem!

I’m not very familiar with L-systems, but yes, I believe there is quite a bit of similarity.

This is an attempt at a mission generator. So the nodes (A, B, C, etc.) are objectives like ‘get the blue key’. The ‘rules’ are little sub-missions, like starting with a locked door and having to find the key to continue.

I’m wondering if the starting and destination nodes change, and if the rules change?
[/quote]
They’ll stay the same over the course of trying to construct the tree, but they’ll be different the next time a tree needs to be generated. The rules will be static though (they’ll be hand-made). The idea is to have lots of little hand-crafted rules and then combine them into interesting missions.

It’s actually more complicated under the hood, but I don’t want to give away too much detail right now.

Cool stuff.

Why can’t you use some kind of effort heuristic to guide an A* algorithm in its search to find the key within the tree?

I’m not sure what you mean by ‘effort heuristic’, could you elaborate?

At the moment I can’t come up with a suitable heuristic for A* because I can’t tell if any given rule is an improvement or not. It could be a good thing (ie. adding node D allows for rule 3 to be used to add node X), or it could be a complete dead end.

Sounds like applying pattern-transformation rules from a functional language or a computer algebra system.

Maybe? That’s awfully vague - have you got any links to elaborate on that? I’m not seeing how that helps solve the problem.

This sounds very similar to parsing Context Free Grammars (CFG). There are good algorithms for this that you can use. I remember that I read something about a good bottom-up, dynamic programming approach.

The dynamic programming algorithm that I mentioned in the previous post is called “chart parse” and I found it in the book “Artificial Intelligence - a modern approach” second edition.

Python Implementation

Lisp implementation

For the non-child symbols, just invent a rule that can take the childrens’ place.

Yes, I had BNF in mind while I was thinking some of this up (hence the ‘rules’). However I don’t think ‘chart parse’ is applicable here - that takes a string/sequence and parses it into the component rules. I want to start with the rules and generate a sequence that matches some additional criteria.

I see, then the “algorithm” is called Hierarchical Task Network (HTN) planning. There you can expand rules and have extra preconditions. It is like Strips but more expressive.
Strips can only generate plans that can be described with regular languages while HTN-planners can generate CFG languages.

Here is an HTN planner implemented in Java:

Simple hierarchical ordered planner

It is an academic planner which might make it useless for anything but toy problems though :slight_smile:

That sounds closer to what I want, but I suspect I can’t break my tasks down hierarchically (which is deliberate, otherwise the results I’d get would be very predictable). Maybe I can crowbar my tasks into some sort of hierarcy just for planning though.

If you don’t need the hierarchy, then you can use a Strips planner instead. There are many fast ones out there that I have tried myself. Try FF (fast forward), GraphPlan or some of the constraint-based such as SatPlan. You might want to look even further if you need to optimize.

I also found an open source implementation of FF in Java

Parsing grammars is an example a pattern-transformation rule system. I was thinking more along the lines of the systems one finds past that in CAS and functional systems which search for patterns in a tree like structures and then apply the matching rule. Note I’ve never played with the guts of any of these so I’m next to useless. Also I’m not quite sure that I understand your problem statement.

Which brings us full circle to my original post - I can’t use a Strips planner because I don’t have a suitable heuristic. Partly because I don’t know which intermediate states are better or worse than others, and partly because I’m not actually after a ‘shortest’ path, just a valid one.

There are two types of Strips planners: Optimal and non-optimal. All the planners that I mentioned in the previous post are non-optimal and you don’t have to provide a heuristic function, the planners use their own. Planners that are optimal use much weaker built-in heuristics because they have to be admissible.

So, if you don’t care about the optimal plan, you can for example use FF, which is very fast and has a good built-in heuristic. The other planners are also very good and they all use the same language, PPDL, so you can test them all with the same problem.

The Java implementation of FF posted there is actually very slow - I think it was just made for educational purposes. FF isn’t optimal but usually gives pretty reasonable results and optimality shouldn’t matter for game levels since a few extra tasks won’t hurt. Graphplan is optimal but if the problem is unsolvable there is no guarantee it will terminate.

The most popular heuristics for forward-searching planners are based on a relaxed planning graph. Basically you solve the whole problem using actions with the delete effects removed, and use the length of that solution as the heuristic distance for the actual problem. It works remarkably well. That’s what FF is using but with some greedy hill-climbing. HSP also uses it but isn’t optimal when actions have more than a single useful effect.

STRIPS is pretty much just a subset of PDDL and they’re both just used to describe a problem. There are tons of planners out there that can solve them once you’ve got it in that representation. Check out the annual planning contest that’s part of ICAPS.