An Introduction to Tabled Logic Programming with Picat

The goal is to reach the exit using the minimum amount of energy. Moving to an open cell costs one energy unit, picking up a key costs one energy unit, and opening a door and moving to the cell previously occupied by that door costs two energy units.

Let's represent a state for this problem as a tuple (R, C, (ExitI, ExitJ), Walls, Doors, Keys, K, (HeroI, HeroJ)):

  • R and C are the number of rows and columns in the maze.

  • (ExitI, ExitJ) are the coordinates of the exit.

  • Walls is a list of the positions of all walls.

  • Doors is a list of the positions of all closed doors.

  • Keys is a list of the positions of not-yet-picked-up keys.

  • K is the number of keys the hero has.

  • (HeroI, HeroJ) are coordinates of the hero's position.

Let's first do some boring work of translating a textual representation of a maze to an initial state in the format defined before.

The main predicate is an imperative procedure in constructing an initial state from a textual representation of a maze: you read the input line by line, symbol by symbol, and then construct the lists of walls, doors and keys, as well as record the coordinates of the hero and the exit.

Listing 3. Read the Maze Description


main =>
  R = read_int(), C = read_int(),
  Walls = [], Doors = [], Keys = [],
  (ExitI, ExitJ) = (_, _),
  (HeroI, HeroJ) = (_, _),
  foreach (I in 1..R)
    Line = read_line(),
    foreach (J in 1..C)
      Char = Line[J],
      if Char == '@' then
        HeroI := I, HeroJ := J
      end,
      if Char == 'X' then
        ExitI := I, ExitJ := J
      end,
      if Char == '#' then
        Walls := [(I, J) | Walls]
      end,
      if Char == '|' then
        Doors := [(I, J) | Doors]
      end,
      if Char == '=' then
        Keys := [(I, J) | Keys]
      end
    end
  end,
  InitState = (R, C, (ExitI, ExitJ),
               Walls, Doors, Keys,
               0, (HeroI, HeroJ)),
  println(InitState).

Let's save this program to maze_read.pi, the maze description from above to maze.txt, and run the program (the output is split into several lines for clarity):


$ picat maze_read.pi < maze.txt
5,5,
(4,3),
[(4,2),(3,3),(3,2),(2,3),(1,3)],
[(5,2)],
[(2,1)],
0,1,1

So, you have the dimensions of the maze (5 by 5), the coordinates of the exit (4, 3), the list of the coordinates of all five walls, a one-element list of the closed doors and a one-element list of the keys available for picking up. The hero has 0 keys and starts in cell (1, 1).

Now that you have your state, you can define some predicates to solve the problem. First, the final predicate for the planner module:


final((_, _, (I, J), _, _, _, _, (I, J))) =>
  true.

The state is final when the hero is in the cell with the same coordinates as the exit cell. Variables with name _ are throw-away, "don't care" variables that are not required to have any specific value (Picat invents a different name for each _ behind the scenes, so they don't have to be equal either).

Next, describe the action to take a key if the hero is in a cell with one:


action(State, NewState, Action, Cost) ?=>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
    select((HeroI, HeroJ), Keys, NewKeys),
    Action = $take_key(HeroI, HeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, NewKeys,
                K + 1, (HeroI, HeroJ)).

First you decompose the state into components, and then you try to select a key with the current coordinates of the hero from the Keys list. If there is such a key, this will succeed, and the rest of the keys will be assigned to "NewKeys"; otherwise, select fails, and Picat will break the execution of this action clause.

The name of the action is take_key, with the coordinates of the event in the parentheses (the $ instructs Picat to treat it literally, like a string, and not to try to execute as a function), and the cost is one energy unit.

The new state is almost the same as the old state, except that the number of keys the hero has is increased by one, and the current key no longer is available to pick up.

Besides picking up keys, there are two more possible actions: moving to an empty cell and moving to a cell with a door after opening it. It's a good idea to combine both these actions into one clause, because they share a lot of code used to select a new hero position and check whether it's within the maze boundary:


action(State, NewState, Action, Cost) =>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
  (
    Di = 0, Dj = 1
  ;
    Di = 0, Dj = -1
  ;
    Di = 1, Dj = 0
  ;
    Di = -1, Dj = 0
  ),
  NewHeroI = HeroI + Di,
  NewHeroJ = HeroJ + Dj,
  NewHeroI >= 1, NewHeroI <= R,
  NewHeroJ >= 1, NewHeroJ <= C,
  (
    % move to open cell
    not membchk((NewHeroI, NewHeroJ), Walls),
    not membchk((NewHeroI, NewHeroJ), Doors),
    Action = $move(NewHeroI, NewHeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, Keys,
                K, (NewHeroI, NewHeroJ))
  ;
    % open a door and move to that cell
    K > 0,
    select((NewHeroI, NewHeroJ), Doors, NewDoors),
    Action = $open(NewHeroI, NewHeroJ),
    Cost = 2,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, NewDoors, Keys,
                K - 1, (NewHeroI, NewHeroJ))
  ).

Again, first you decompose the state into the components. Next, you try all possible new positions for the hero with non-deterministic disjunction: ;.

A position must be within the maze boundaries: I must be from 1 to R, and J must be from 1 to C. After that, there are two possibilities: move to an open cell, or open a door and move to that cell.

Moving to an open cell is possible only if there isn't a wall or a closed door at the desired position. Two not membchk lines verify this condition. If the condition is met, the action name is move, and the cost is one energy unit. The only change in the state is the hero's position.

Opening an door is possible if there is a door at the position and the hero has at least one key. The select line here is similar to the line for the take action, but now you select a door instead of a key. If the conditions are met, the action name is open, and the cost is two energy units. The new state is almost the same as the old state, but the door is removed from the list of doors, the number of keys the hero has is decreased by one, and the hero has moved to a new position.

To use the defined final and action predicates and find the plan, you need to change println(InitState) to best_plan_unbounded(InitState, Plan), println(Plan) in the main from the maze_read.pi program. (Note: best_plan_unbounded is one of the predicates of the planner module for finding best plans. This particular version uses memory to avoid re-exploring states, converting tree search in the space of all possible plans to graph search.)

Listing 4 shows the complete maze program.

Listing 4. Full Maze Program


import planner.

action(State, NewState, Action, Cost) ?=>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
    select((HeroI, HeroJ), Keys, NewKeys),
    Action = $take_key(HeroI, HeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, NewKeys,
                K + 1, (HeroI, HeroJ)).

action(State, NewState, Action, Cost) =>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
  (
    Di = 0, Dj = 1
  ;
    Di = 0, Dj = -1
  ;
    Di = 1, Dj = 0
  ;
    Di = -1, Dj = 0
  ),

  NewHeroI = HeroI + Di,
  NewHeroJ = HeroJ + Dj,
  NewHeroI >= 1, NewHeroI <= R,
  NewHeroJ >= 1, NewHeroJ <= C,

  (
    % move to open cell
    not membchk((NewHeroI, NewHeroJ), Walls),
    not membchk((NewHeroI, NewHeroJ), Doors),
    Action = $move(NewHeroI, NewHeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, Keys,
                K, (NewHeroI, NewHeroJ))
  ;
    % open a door and move to that cell
    K > 0,
    select((NewHeroI, NewHeroJ), Doors, NewDoors),
    Action = $open(NewHeroI, NewHeroJ),
    Cost = 2,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, NewDoors, Keys,
                K - 1, (NewHeroI, NewHeroJ))
  ).

final((_, _, (I, J), _, _, _, _, (I, J))) =>
  true.

main =>
  R = read_int(), C = read_int(),
  Walls = [], Doors = [], Keys = [],
  (ExitI, ExitJ) = (_, _),
  (HeroI, HeroJ) = (_, _),
  foreach (I in 1..R)
    Line = read_line(),
    foreach (J in 1..C)
      Char = Line[J],
      if Char == '@' then
        HeroI := I, HeroJ := J
      end,
      if Char == 'X' then
        ExitI := I, ExitJ := J
      end,
      if Char == '#' then
        Walls := [(I, J) | Walls]
      end,
      if Char == '|' then
        Doors := [(I, J) | Doors]
      end,
      if Char == '=' then
        Keys := [(I, J) | Keys]
      end
    end
  end,
  InitState = (R, C, (ExitI, ExitJ),
               Walls, Doors, Keys,
               0, (HeroI, HeroJ)),
  best_plan_unbounded(InitState, Plan),
  println(Plan).

After running it for the maze used above, you get an optimal plan (list of actions) to solve the maze (the output is split into several lines for clarity):


$ picat maze.pi < maze.txt
[
 move(2,1),
 take_key(2,1),
 move(3,1),
 move(4,1),
 move(5,1),
 open(5,2),
 move(5,3),move(4,3)
]

You can try to run this program with inputs of various sizes and with different features. For example, this input requires the hero to take a key to the right, then go left to get more keys, and then go right again to the exit:


1 10 ==|=|@=||X

Of course, you can improve the maze program in many different ways:

  • Better user interface: currently, the output is not very easy to read, and the program exits with an error if the maze is not solvable.

  • Sets or hash tables instead of lists: looking for a key or wall in a list requires linear time, while with a more appropriate data structure, it will be constant.

  • Adding a heuristic: the search could be improved with a heuristic to make it a variant of an IDA* algorithm.

  • New maze features: you could implement different kinds of keys, weapons, treasure and monsters.

Overall, Picat looks like a really good starting point for a journey into the realm of logic-based programming languages. It provides many of the goodies Prolog has, such as non-determinism and built-in depths-first search with backtracking, and at the same time, Picat allows you to fall back to convenient imperative concepts like destructive assignments and loops. Higher-level features, like tabling and the planner module, provide ways to write concise, declarative and efficient programs.

Resources

Picat: http://picat-lang.org

"Artificial intelligence planning with Picat" by Sergii Dymchenko: http://sdymchenko.com/blog/2015/01/31/ai-planning-picat

Hakan Kjellerstrand's Picat Page: http://www.hakank.org/picat

"Declaratively solving Google Code Jam problems with Picat" by Sergii Dymchenko and Mariia Mykhailova: http://arxiv.org/abs/1504.00977

"Combinatorial Search with Picat" by Neng-Fa Zhou: http://arxiv.org/abs/1405.2538

______________________

Sergii Dymchenko is a software developer, a programming languages enthusiast and a great believer in the importance of open-source and free software.