Writing a Planner to solve a tricky programming optimization problem

Suppose a monkey is in one corner of a room, a box is in another corner of a room, and a banana is hanging from the ceiling in the middle of the room. The monkey can’t reach the banana without standing on the box, but he first has to move the box under the banana. The problem of how to get a computer to work out that the monkey has to move the box first, then climb on the box second, was solved by Nils Nilsson’s STRIPS system in 1971. STRIPS is now an A.I. standard, and is used in game A.I. and elsewhere.

Suppose you have a disk image template that you want to uncompress, convert to another format, and resize. You can run xzcat, followed by qemu-img convert followed by virt-resize. But virt-resize can also do format conversion, so you don’t need to run qemu-img convert. Unless the user was happy with the original size, in which case qemu-img convert is faster than virt-resize. But what if the original template isn’t compressed and is already in the right format and size? You can just run cp.

How can a computer work out the right sequence of steps to convert the disk image most efficiently? Virt-builder has exactly this problem, and it solves it using a STRIPS-inspired planner.

The STRIPS planner in virt-builder is only 50 lines of code, was easy to write, finds the near optimal plan for almost any user input, and is a useful technique that can be applied to many programming problems. This article will explain how it works. I have changed some of the academic terms and simplified things to make this easier to understand.

First of all I’ll introduce tags on the original template. These define the state of that template:

Input tags: ✚xz ✚template ✚size=4G ✚format=raw

Secondly I’ll set up my goal state:

Goal tags: ❌xz ❌template ✚size=4G ✚format=qcow2

where means the tag MUST NOT exist in the final state.

I want my planner to find me the best path from my input state to my goal. As it can’t go straight from the input to the goal in one step, I have to tell the planner what transitions are possible, using a function:

transitions (input_tags) {
  if ✚xz then {
    you could run 'xzcat'
        which will ❌xz and ❌template;
  }
  else /* no xz tag */ {
    you could run 'virt-resize'
       which will change ✚format and ✚size, and ❌template;
    or:
    you could run 'qemu-img convert'
       which will change ✚format, and ❌template;
    or:
    etc...
  }

  or:
  you could run 'cp'
      which will ❌template;
}

Notice that the transitions function returns a list of all possible transitions from the input state. It’s not judgemental about which one should be taken, although it won’t return impossible transitions (for example, running virt-resize is not possible on xz-compressed files). The actual transitions function also returns a weight for each transition, so that the planner can choose the least expensive plan if there are several plans possible.

The ✚template tag may appear a bit mysterious. It’s there to make sure that the planner always copies the original template, even if the original template already has the desired goal size and format. Since xzcat, virt-resize and qemu-img convert always copy the disk image, they drop the template tag (❌template).

The transitions function in virt-builder can be found here.

The planner does a breadth-first search over the tree of transitions, starting with the input state, finishing when it finds any branch that satisfies the output goals, or when it reaches a maximum depth in which case it gives up (and the user sees an error message).

The planner in virt-builder (50 lines of code) can be found here.

If the planner finds several paths that satisfy the goals, the planner chooses the one with the smallest weight. However my planner is not clever enough to look deeper in the tree to see if a longer path might have a smaller weight (it’s not very likely in virt-builder).

Also my planner is not smart enough to prune bogus paths. For example, if a path runs cp in adjacent steps, then that path should be pruned.

Nevertheless the planner always gets the right result, and it is considerably simpler than the original hand-written code. The old code had become unmaintainable and wasn’t even efficient: it sometimes made unnecessary copies in order to make the code simpler, wasting end-user time. Because of the ease of maintenance I was able to add new functionality: virt-builder can now run qemu-img resize to expand a disk by < 256 MB, a case where virt-resize doesn’t work (previously the user would have got an error).

Applying old academic techniques like this one doesn’t need to be hard and can help with real world problems. I hope this technique helps others with similar optimization problems.

Edit: The Hacker News discussion includes links to alternative solving tools.

About these ads

8 Comments

Filed under Uncategorized

8 responses to “Writing a Planner to solve a tricky programming optimization problem

  1. Foo

    This isn’t really a planner: it’s a forward situation-space searching tool. Typical planners (including the venerable STRIPS) are regression, plan-space planners and bear no relationship with this.

    Additionally, STRIPS isn’t a standard. It’s an old planning tool no one uses, and was neither sound nor complete even in its heyday. What’s a standard is the STRIPS *problem definition language*, which also influenced later languages such as ADL and PDDL.

    Finally your problem isn’t an optimization problem. It’s a search problem. In search problems, you have something you are searching *for*, and when you find it, you stop. In an optimization problem, you’re trying to optimize a function, and you don’t know when to stop and don’t expect to ever find the optimum (in a typical problem anyway). Planning is search.

    • rich

      Can you back this up? Google turns up nothing of substance for searches involving “forward situation-space searching tool” nor “regression, plan-space planners” and similar.

      I’m aware of PDDL. There’s also discussion of it in the HN thread I linked to above. I didn’t want to rely on an external tool since virt-builder has to be very portable.

  2. Foo

    Maybe situation-space isn’t the right term exactly. The difference I’m getting at is this. You’re doing state-space search (in your case, BFS), where the nodes of the state graph are *situations* you can be in and the edges are *operations* which go from situation to situation. That is, you first do FOO, leading to the situation where FOO has been performed, then you do BAR, leading to the situation where FOO and BAR have been performed, and so on. It’s how you might perform “planning”, so to speak, with the Situation Calculus as well. But that’s not how most planners work. Most (not all) planners search through *plan space*, where the nodes are incomplete plans, and edges from node to node indicate things added to the plan or modified in the plan in order to achieve a new goal, thus introducing new subgoals which need to be met. It’s a totally different approach.

    Also your tool is a forward searcher whereas most planners (not all, but certainly including STRIPS) are regression, (or “backwards”, or “means-ends”) searchers. That is, they start with the goal and then search backwards from it, like this: I want to do X. What will achieve X? Y will achieve X. Okay, how do I achieve Y? And so on.

    Finally, no planner is gonna do BFS. BFS is ridiculously inefficient. Planners will use A* or a constraint satisfaction search procedure.

    Russell and Norvig have pretty good coverage of partial-order and HTN planners in two chapters.

    • Foo

      It’s worth mentioning that not all planners are regression planners. There are forward-chaining planners too, though perhaps less common. For example, on HN there’s a pointer to POPF, a forward-chaining partial-order planner which is an example of this breed.

      • Foo

        Also: planners are for nasty problems, often with lots of operations and states, where achieving certain goals with operations will produce new goals that have to be met. This doesn’t sound like your problem. Rather you have a single goal, with no *interacting* subgoals, and need to just find the shortest path to get to it. It sounds to me like you’ve hit on a perfectly reasonable approach to solving it, though I wouldn’t call it a planner per se.

        Speaking of which, your BFS approach is reasonable, though I would try Iterated Deepening Search instead. And also consider this. It seems that you’re looking for the shortest number of *procedures*. But maybe you’ve found a very short number of procedures but they take a long time to run (or use a lot of memory). Perhaps a better measure of the quality of a string of procedures would be how long it takes to run them. In this case BFS won’t work. But if you have a way of estimating the runtime of various procedures on different kinds of input, you could use, at the very least, Dijkstra’s (A* is overkill) instead of BFS. That’d be a much more useful tool to you I’d warrant.

  3. Richard,

    As an academic who works in planning and loves OCaml, I was delighted to see this post – thanks very much for sharing your work. There are lots of kinds of planning problems and lots of kinds of planners, and it’s great that you found something that works for you.

    If you want to find the cheapest plan, instead of the one with the fewest actions, then I’d like to second the previous poster’s suggestion of using a Dijkstra-style search (also called “uniform-cost search” in the AI literature). This requires implementing a priority queue (a binary heap using an array works fine), but other than that it’s very simple. Iterative deepening can be a fragile technique and I don’t generally recommend it.

    Best wishes.

    • rich

      My planner certainly sucks, no doubt about that. However the code is much cleaner and better now, and the planner could be improved in future without changing any other aspects.

  4. Pingback: libguestfs 1.26 released | Richard WM Jones

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s