astar-monad

[ bsd3, library, unclassified ] [ Propose Tags ]

Please see the README on GitHub at https://github.com/ChrisPenner/astar-monad#readme


[Skip to Readme]
Versions [faq] 0.1.0.0, 0.2.0.0, 0.2.1.0, 0.3.0.0
Change log ChangeLog.md
Dependencies base (>=4.7 && <5), logict, mtl [details]
License BSD-3-Clause
Copyright Chris Penner
Author Chris Penner
Maintainer christopher.penner@gmail.com
Home page https://github.com/ChrisPenner/astar-monad#readme
Bug tracker https://github.com/ChrisPenner/astar-monad/issues
Source repo head: git clone https://github.com/ChrisPenner/astar-monad
Uploaded by ChrisPenner at Wed Sep 11 23:51:59 UTC 2019
Distributions NixOS:0.3.0.0
Downloads 175 total (82 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs uploaded by user
Build status unknown [no reports yet]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for astar-monad-0.2.1.0

[back to package description]

A* Monad

Hackage

Caveat Emptor; this hasn't been battle-tested yet; it should work, but make sure to test it out if you're doing anything serious.

Easily do A* searches with use of arbitrary monadic effects!

Basics

  • Use <|> or asum (anything using Alternative) to branch into multiple possible choices.
  • Use updateCost myCost to set the value of your 'heuristic' function whenever you've done enough work to change your estimate. Remember that A* heuristics should always be pessimistic (e.g. can over-estimate cost, but shouldn't UNDER estimate).
  • Every call to updateCost creates a branch; Branches with LOWER costs will run before those with higher costs.
  • Call done mySolution to short circuit ALL running branches and immediately return your result.
  • AStarT has a built-in State monad which can store branch-local states for you. You can store your current branch's solution-space for instance, or the path you've followed to get to the current solution; or both!

Here's an example of using A* to find a path to a location in a 2 dimensional grid.

-- Track which moves we've made, up, down, left or right
data Move = U | D | L | R
    deriving (Show, Eq)

-- Track our current position, the goal we're moving towards, and the moves we've taken so far.
data Context =
    Context { _currentPos :: (Int, Int)
            , _goal    :: (Int, Int)
            , _moves   :: [Move]
            }
    deriving (Show, Eq)
makeLenses ''Context

-- The Manhattan distance between two points
-- This is our A* heuristic
distanceTo :: (Int, Int) -> (Int, Int) -> Int
distanceTo (x, y) (x', y') = abs (x - x') + abs (y - y')

-- Move around the space looking for the destination point.
findPoint :: AStar Context Int () ()
findPoint = do
    c <- use currentPos
    gl <- use goal
    -- I could return the moves we took, 
    -- but our State is automatically returned when we run AStar
    when (c == gl) $ done ()
    -- We have more work to do, we should update the cost estimate and continue
    updateCost $ distanceTo gl c
    if c == gl 
       then done ()
       else updateCost $ distanceTo gl c
    -- Non-deterministically choose a direction to move, 
    -- store that move in our state, and edit our current position.
    asum
        [ moves <>= [R] >> currentPos . _1 += 1 >> findPoint
        , moves <>= [L] >> currentPos . _1 -= 1 >> findPoint
        , moves <>= [D] >> currentPos . _2 += 1 >> findPoint
        , moves <>= [U] >> currentPos . _2 -= 1 >> findPoint
        ]

-- We only care about the ending state, so we use `execAStar`
-- `runAStarT` is the most powerful and runs a monad-transformer version
-- and returns both the state and result type.
run :: Maybe Context
run = execAStar findPoint
             Context { _current = (5, 5)
                     , _goal    = (7, 4)
                     , _moves   = []
                     }

-- run it to see if we found a solution; it returns the state of the the 'winning' branch.
>>> run 
Just (Context { _current = (7, 4)
              , _goal    = (7, 4)
              , _moves   = [U, R, R]
              })