Solving Planning Problems with Fast Downward and Haskell

In this post I’ll demonstrate my new fast-downward library and show how it can be used to solve planning problems. The name comes from the use of the backend solver - Fast Downward. But what’s a planning problem?

Roughly speaking, planning problems are a subclass of AI problems where we need to work out a plan that moves us from an initial state to some goal state. Typically, we have:

Planning problems are essentially state space search problems, and crop up in all sorts of places. The common examples are that of moving a robot around, planning logistics problems, and so on, but they can be used for plenty more! For example, the Beam library uses state space search to work out how to converge a database from one state to another (automatic migrations) by adding/removing columns.

State space search is an intuitive approach - simply build a graph where nodes are states and edges are state transitions (effects), and find a path (possibly shortest) that gets you from the starting state to a state that satisfies some predicates. However, naive enumeration of all states rapidly grinds to a halt. Forming optimal plans (least cost, least steps, etc) is an extremely difficult problem, and there is a lot of literature on the topic (see ICAPS - the International Conference on Automated Planning and Scheduling and recent International Planning Competitions for an idea of the state of the art). The fast-downward library uses the state of the art Fast Downward solver and provides a small DSL to interface to it with Haskell.

In this post, we’ll look at using fast-downward in the context of solving a small planning problem - moving balls between rooms via a robot. This post is literate Haskell, here’s the context we’ll be working in:

{-# language DisambiguateRecordFields #-}

module FastDownward.Examples.Gripper where

import Control.Monad
import qualified FastDownward.Exec as Exec
import FastDownward.Problem

If you’d rather see the Haskell in it’s entirety without comments, simply head to the end of this post.

Modelling The Problem

Defining the Domain

As mentioned, in this example, we’ll consider the problem of transporting balls between rooms via a robot. The robot has two grippers and can move between rooms. Each gripper can hold zero or one balls. Our initial state is that everything is in room A, and our goal is to move all balls to room B.

First, we’ll introduce some domain specific types and functions to help model the problem. The fast-downward DSL can work with any type that is an instance of Ord.

data Room = RoomA | RoomB
  deriving (Eq, Ord, Show)

adjacent :: Room -> Room
adjacent RoomA = RoomB
adjacent RoomB = RoomA

data BallLocation = InRoom Room | InGripper
  deriving (Eq, Ord, Show)

data GripperState = Empty | HoldingBall
  deriving (Eq, Ord, Show)

A ball in our model is modelled by its current location. As this changes over time, it is a Var - a state variable.

type Ball = Var BallLocation

A gripper in our model is modelled by its state - whether or not it’s holding a ball.

type Gripper = Var GripperState

data Action = PickUpBall | SwitchRooms | DropBall
  deriving (Show)

With this, we can now begin modelling the specific instance of the problem. We do this by working in the Problem monad, which lets us introduce variables (Vars) and specify their initial state.

Setting the Initial State

problem :: Problem (SolveResult Action)
problem = do

First, we introduce a state variable for each of the 4 balls. As in the problem description, all balls are initially in room A.

  balls <- replicateM 4 (newVar (InRoom RoomA))

Next, introduce a variable for the room the robot is in - which also begins in room A.

  robotLocation <- newVar RoomA

  grippers <- replicateM 2 (newVar Empty)

This is sufficient to model our problem. Next, we’ll define some effects to change the state of the world.

Defining Effects

Effects are computations in the Effect monad - a monad that allows us to read and write to variables, and also fail (via MonadPlus). We could define these effects as top-level definitions (which might be better if we were writing a library), but here I’ll just define them inline so they can easily access the above state variables.

Effects may be used at any time by the solver. Indeed, that’s what solving planning problems is all about! The hard part is choosing effects intelligently, rather than blindly trying everything. Fortunately, you don’t need to worry about that - Fast Downward will take care of that for you!

Picking Up Balls

The first effect takes a ball and a gripper, and attempts to pick up that ball with that gripper.

    pickUpBallWithGripper :: Ball -> Gripper -> Effect Action
    pickUpBallWithGripper b gripper = do
      Empty <- readVar gripper                  -- (1)

      robotRoom <- readVar robotLocation        -- (2)
      ballLocation <- readVar b
      guard (ballLocation == InRoom robotRoom)  -- (3)

      writeVar b InGripper                      -- (4)
      writeVar gripper HoldingBall

      return PickUpBall                         -- (5)

Moving Between Rooms

    moveRobotToAdjacentRoom :: Effect Action
    moveRobotToAdjacentRoom = do
      modifyVar robotLocation adjacent

      return SwitchRooms

This is an “unconditional” effect as we don’t have any explicit guards or pattern matches. We simply flip the current location by an adjacency function.

Again, we finish by returning some information to use when this effect is chosen.

Dropping Balls

    dropBall :: Ball -> Gripper -> Effect Action
    dropBall b gripper = do
      HoldingBall <- readVar gripper     -- (1)
      InGripper <- readVar b

      robotRoom <- readVar robotLocation -- (2)
      writeVar gripper Empty             -- (3)
      writeVar b (InRoom robotRoom)      -- (4)

      return DropBall                    -- (5)

Solving Problems

With our problem modelled, we can now attempt to solve it. We invoke solve with a particular search engine (in this case A* with landmark counting heuristics). We give the solver two bits of information:

  solve
    cfg
    ( [ pickUpBallWithGripper b g | b <- balls, g <- grippers ]
        ++ [ dropBall b g | b <- balls, g <- grippers ]
        ++ [ moveRobotToAdjacentRoom ]
    )
    [ b ?= InRoom RoomB | b <- balls ]

So far we’ve been working in the Problem monad. We can escape this monad by using runProblem :: Problem a -> IO a. In our case, a is SolveResult Action, so running the problem might give us a plan (courtesy of solve). If it did, we’ll print the plan.

main :: IO ()
main = do
  res <- runProblem problem
  case res of
    Solved plan -> do
      putStrLn "Found a plan!"
      zipWithM_ 
        ( \i step -> putStrLn ( show i ++ ": " ++ show step ) ) 
        [ 1::Int .. ] 
        ( totallyOrderedPlan plan )

    _ ->
      putStrLn "Couldn't find a plan!"

fast-downward allows you to extract a totally ordered plan from a solution, but can also provide a partiallyOrderedPlan. This type of plan is a graph (partial order) rather than a list (total order), and attempts to recover some concurrency. For example, if two effects do not interact with each other, they will be scheduled in parallel.

Well, Did it Work?!

Behind The Scenes

It might be interesting to some readers to understand what’s going on behind the scenes. Fast Downward is a C++ program, yet somehow it seems to be running Haskell code with nothing but an Ord instance - there are no marshalling types involved!

First, let’s understand the input to Fast Downward. Fast Downward requires an encoding in its own SAS format. This format has a list of variables, where each variable contains a list of values. The contents of the values aren’t actually used by the solver, rather it just works with indices into the list of values for a variable. This observations means we can just invent values on the Haskell side and careful manage mapping indices back and forward.

Next, Fast Downward needs a list of operators which are ground instantiations of our effects above. Ground instantiations of operators mention exact values of variables. Recounting our gripper example, pickUpBallWithGripper b gripper actually produces 2 operators - one for each room. However, we didn’t have to be this specific in the Haskell code, so how are we going to recover this information?

fast-downward actually performs expansion on the given effects to find out all possible ways they could be called, by non-deterministically evaluating them to find a fixed point.

A small example can be seen in the moveRobotToAdjacentRoom Effect. This will actually produce two operators - one to move from room A to room B, and one to move from room B to room A. The body of this Effect is (once we inline the definition of modifyVar)

  readVar robotLocation >>= writeVar robotLocation . adjacent

Initially, we only know that robotLocation can take the value RoomA, as that is what the variable was initialised with. So we pass this in, and see what the rest of the computation produces. This means we evaluate adjacent RoomA to yield RoomB, and write RoomB into robotLocation. We’re done for the first pass through this effect, but we gained new information - namely that robotLocation might at some point contain RoomB. Knowing this, we then rerun the effect, but the first readVar gives us two paths:

readVar robotLocation 
  >>= \RoomA -> writeVar robotLocation RoomB                     -- If we read RoomA
  >>= \RoomB -> writeVar robotLocation (adjacent RoomB -> RoomA) -- If we read RoomB

This shows us that robotLocation might also be set to RoomA. However, we already knew this, so at this point we’ve reached a fixed point.

In practice, this process is ran over all Effects at the same time because they may interact - a change in one Effect might cause new paths to be found in another Effect. However, because fast-downward only works with finite domain representations, this algorithm always terminates. Unfortunately, I have no way of enforcing this that I can see, which means a user could infinitely loop this normalisation process by writing modifyVar v succ, which would produce an infinite number of variable assignments.

Conclusion

CircuitHub are using this in production (and I mean real, physical production!) to coordinate activities in its factories. By using AI, we have a declarative interface to the production process – rather than saying what steps are to be performed, we can instead say what state we want to end up in and we can trust the planner to find a suitable way to make it so.

Haskell really shines here, giving a very powerful way to present problems to the solver. The industry standard is PDDL, a Lisp-like language that I’ve found in practice is less than ideal to actually encode problems. By using Haskell, we:

fast-downward is available on Hackage now, and I’d like to express a huge thank you to CircuitHub for giving me the time to explore this large space and to refine my work into the best solution I could think of. This work is the result of numerous iterations, but I think it was worth the wait!

Appendix: Code Without Comments

{-# language DisambiguateRecordFields #-}

module FastDownward.Examples.Gripper where

import Control.Monad
import qualified FastDownward.Exec as Exec
import FastDownward.Problem


data Room = RoomA | RoomB
  deriving (Eq, Ord, Show)


adjacent :: Room -> Room
adjacent RoomA = RoomB
adjacent RoomB = RoomA


data BallLocation = InRoom Room | InGripper
  deriving (Eq, Ord, Show)


data GripperState = Empty | HoldingBall
  deriving (Eq, Ord, Show)


type Ball = Var BallLocation


type Gripper = Var GripperState

  
data Action = PickUpBall | SwitchRooms | DropBall
  deriving (Show)


problem :: Problem (Maybe [Action])
problem = do
  balls <- replicateM 4 (newVar (InRoom RoomA))
  robotLocation <- newVar RoomA
  grippers <- replicateM 2 (newVar Empty)

  let
    pickUpBallWithGripper :: Ball -> Gripper -> Effect Action
    pickUpBallWithGripper b gripper = do
      Empty <- readVar gripper
  
      robotRoom <- readVar robotLocation
      ballLocation <- readVar b
      guard (ballLocation == InRoom robotRoom)
  
      writeVar b InGripper
      writeVar gripper HoldingBall
  
      return PickUpBall


    moveRobotToAdjacentRoom :: Effect Action
    moveRobotToAdjacentRoom = do
      modifyVar robotLocation adjacent
      return SwitchRooms


    dropBall :: Ball -> Gripper -> Effect Action
    dropBall b gripper = do
      HoldingBall <- readVar gripper
      InGripper <- readVar b
  
      robotRoom <- readVar robotLocation
      writeVar b (InRoom robotRoom)
  
      writeVar gripper Empty
  
      return DropBall

  
  solve
    cfg
    ( [ pickUpBallWithGripper b g | b <- balls, g <- grippers ]
        ++ [ dropBall b g | b <- balls, g <- grippers ]
        ++ [ moveRobotToAdjacentRoom ]
    )
    [ b ?= InRoom RoomB | b <- balls ]

  
main :: IO ()
main = do
  plan <- runProblem problem
  case plan of
    Nothing ->
      putStrLn "Couldn't find a plan!"

    Just steps -> do
      putStrLn "Found a plan!"
      zipWithM_ (\i step -> putStrLn $ show i ++ ": " ++ show step) [1::Int ..] steps


cfg :: Exec.SearchEngine
cfg =
  Exec.AStar Exec.AStarConfiguration
    { evaluator =
        Exec.LMCount Exec.LMCountConfiguration
          { lmFactory =
              Exec.LMExhaust Exec.LMExhaustConfiguration
                { reasonableOrders = False
                , onlyCausalLandmarks = False
                , disjunctiveLandmarks = True
                , conjunctiveLandmarks = True
                , noOrders = False
                }
          , admissible = False
          , optimal = False
          , pref = True
          , alm = True
          , lpSolver = Exec.CPLEX
          , transform = Exec.NoTransform
          , cacheEstimates = True
          }
    , lazyEvaluator = Nothing
    , pruning = Exec.Null
    , costType = Exec.Normal
    , bound = Nothing
    , maxTime = Nothing
    }