# Artificial intelligence planning with Picat

Picat (http://picat-lang.org/) is a new logic-based programming language. In many ways, Picat is similar to Prolog, especially B-Prolog, but it has functions in addition to predicates, pattern-matching instead of unification, explicit non-determinism (`?=>` means a non-deterministic goal), and destructive assignment. In this article I'll use the currently latest version Picat 0.8.

Picat has a planning module for declarative solving planning problems.

To solve a planning problem in Picat a programmer needs to define a `final` predicate for the final state, and an `action` predicate for possible actions.

The `final` predicate in its simplest form has only one parameter – the current state – and succeeds if the state is final.

The `action` predicate usually has several clauses – one for each possible action. The predicate has 4 parameters: current state, new state, action name, and action cost.

Picat's predicate for finding an optimal plan – `best_plan` – has 2 input parameters: the initial state and the resource limit, and 2 output parameters: the best plan and its cost. To find an optimal plan the system uses iterative deepening depth-first search-like algorithm. If no plan was found and the maximum resource limit was reached, the predicate fails.

Under the hood, Picat's planning module uses tabling (a form of memoization) to convert a tree search through state space to a graph search.

Below are 3 simple examples of using Picat to declaratively solve planning problems.

## Short Deadfish Numbers (Code Golf StackExchange)

The first example is my solution for the Short Deadfish Numbers problem.

The problem is about an esoteric programming language Deadfish. The language has one accumulator (which starts at 0) and 4 commands: `i` to increment the accumulator, `s` to square the accumulator, `d` to decrement the accumulator, and `o` to output the accumulator's value and a new line character.

The problem asks to find the shortest possible sequence of Deadfish commands to output an integer from the range [0, 255] given as the program's parameter.

```final((N, N)) => true.

action((N, A), NewState, Action, Cost) ?=>
NewState = (N, A + 1),
Action = i,
Cost = 1.
action((N, A), NewState, Action, Cost) ?=>
A != 16,
A < N,
NewState = (N, A * A),
Action = s,
Cost = 1.
action((N, A), NewState, Action, Cost) ?=>
A > 0,
NewState = (N, A - 1),
Action = d,
Cost = 1.

main([X]) =>
N = X.to_integer(),
best_plan((N, 0), Plan),
printf("%w\n", Plan ++ [o]).
```

The state representation for this problem is a pair `(goal value, current value)`.

The state is final when the current value equals to the goal value.

The actions – `i`, `s`, and `d` – correspond to the Deadfish commands.

The `main` predicate gets the goal number from the command-line parameters, calls a two-parameter version of the `best_plan` (which assumes a very high resource limit – 268435455 – and doesn't return the best plan's cost), and prints the best plan plus the `o` command.

Also see much shorter code golf-style version of this program.

Adjusting passwords was the first problem from the Internet Problem Solving Contest 2014.

The problem asks to find a shortest sequence of keystrokes to convert an already typed string to a goal string. A keystroke can be just a letter a–z, a backspase (`<`), or "enter" (`*`), which effectively erases the whole string. See the problem statement for more details and examples.

```% Adjusting passwords
% http://ipsc.ksp.sk/2014/real/problems/a.html
% Picat 0.8 - http://picat-lang.org

import planner.

final((Str, Goal)) =>
Str = Goal.

action((Str, Goal), NewState, Action, Cost) ?=>
append(_, [Action | Str], Goal),
NewState = ([Action | Str], Goal),
Cost = 1.

action((_, Goal), NewState, Action, Cost) ?=>
NewState = ([], Goal),
Action = '*',
Cost = 1.

action(([_|Str], Goal), NewState, Action, Cost) ?=>
NewState = (Str, Goal),
Action = '<',
Cost = 1.

do_case(Goal, Was) =>
RGoal = reverse(Goal),
RWas = reverse(Was),
best_plan((RWas, RGoal), length(Goal) + 1, Plan, _Cost),
printf("%s*\n", Plan).

main =>
foreach(_Case_num in 1..T)
do_case(Goal, Was)
end.
```

In this program a state is represented as a pair `(reversed current string, reversed goal string)`. A state is final if both strings are equal.

Strings in Picat are represented as linked lists of characters, and for linked lists it's natural to add and delete items from the beginning (head). The problem asks to add and delete from the end, so both the initial string and the goal string are reversed before passing to `best_plan`.

The actions are adding a letter (`a``z`), `*`, and `<`. The `append` predicate and the `[ | ]` syntax for getting the head and the tail of a list work exactly the same way as in Prolog.

The limit for `best_plan` is the length of the goal string plus 1, because there is an obvious plan to use `*` to erase the current string and retype all character of the goal string. `printf` outputs the plan found by `best_plan` plus the final "enter".

Osmos was the easiest problem from Round 1B of the Google Code Jam 2013.

This problem is about "motes". There is a player's mote (`Armin`), and there are other motes (`Others`). `Armin` can absorb an other mote if `Armin` is bigger; after that `Armin`'s size increases by the size of the absorbed mote.

Also, there are two operations that can be performed any number of times: a mote with positive size can be added to the list of other motes, and a mote can be removed from the list.

The goal is to find the minimum number of these two operations in order to make it possible for `Armin` to absorb every other mote.

See the problem statement for more details and examples.

```% A. Osmos
% Picat 0.8 - http://picat-lang.org

import planner.
import util.

final([_, []]) => true.

action([Armin, Others], NewState, Action, Cost) ?=>
Others = [Min | Rest],
Armin > Min,
NewArmin is Armin + Min,
Action = absorb,
Cost = 0,
NewState = [NewArmin, Rest].

action([Armin, Others], NewState, Action, Cost) ?=>
Others = [Min | _Rest],
Armin =< Min,
append(NewOthers, [_], Others),
Action = remove,
Cost = 1,
NewState = [Armin, NewOthers].

action([Armin, Others], NewState, Action, Cost) ?=>
Others = [Min | _Rest],
Armin =< Min,
NewItem is Armin - 1,
NewOthers = [NewItem | Others],
Cost = 1,
NewState = [Armin, NewOthers].

do_case(Case_num, Armin, Others) =>
Limit = length(Others),
best_plan([Armin, sort(Others)], Limit, _Plan, Cost),
printf("Case #%w: %w\n", Case_num, Cost).

main =>
foreach(Case_num in 1..T)
Others = [to_integer(X) : X in split(read_line())],
do_case(Case_num, Armin, Others)
end.
```

A state for this problem represented as a 2-element list, where the first item is the `Armin` size, and the second item is a sorted list of the sizes of other motes. A state is final if the `Others` list is empty.

The actions are `absorb`, `remove`, and `add`.

The `absorb` action can be used if `Armin` is bigger than the first of the other motes (the first mote is either the smallest of the other motes, or – if it was adder by the `add` action – smaller than `Armin`). `Armin` increases by the size of the absorbed mote, and the mote is removed from the list of motes. The cost of this action is 0.

The `remove` action removes the last (the largest) mote from `Others`. Again, the `append` predicate and the `[ | ]` syntax for getting the head and the tail of a list work exactly the same way as in Prolog. The cost of this action is 1.

The `add` action adds a mote with the size `Armin - 1` to the beginning of the other motes list (so it can be absorbed by the next `absorb` action). The cost of this action is also 1.

The list of other motes is sorted in the ascending order before sending to `best_plan`. The resource limit for `best_plan` is the initial number of other motes, because there is an obvious plan of this cost to remove the motes one by one.

The `main` predicate uses an interesting Picat feature – list comprehension (`[to_integer(X) : X in split(read_line())]` corresponds to Python's `[int(x) for x in input().split()]`).

In this article I didn't cover an important feature of the Picat planning module – usage of heuristics, which makes the planning algorithm in Picat a variant of the IDA* algorithm. For more info about Picat's planning module see "Planning Problems" at http://picat-lang.org/projects.html and the paper Zhou, Neng-Fa, and Hakan Kjellerstrand. "Solving several planning problems with Picat." Control and Decision Conference (2014 CCDC), The 26th Chinese. IEEE, 2014.