Sergii Dymchenko

Artificial intelligence planning with Picat

Currently I'm participating in the Coursera course Artificial Intelligence Planning, and this article is my submission to the course's "Creative Challenge" assignment.

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]).

GitHub: https://github.com/kit1980/sdymchenko-com/blob/master/ai-planning-picat/ShortDeadfishNumbers.pi

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 (IPSC)

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 =>
    T = read_int(),
    foreach(_Case_num in 1..T)
            _ = read_line(),
            Goal = read_line(),
            Was = read_line(),
            do_case(Goal, Was)
    end.

GitHub: https://github.com/kit1980/sdymchenko-com/blob/master/ai-planning-picat/AdjustingPasswords.pi

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 (az), *, 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 (Google Code Jam)

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
% https://code.google.com/codejam/contest/2434486/dashboard#s=p0
% 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],
    Action = add,
    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 =>
    T = read_int(),
    foreach(Case_num in 1..T)
            Armin = read_int(),
            _N = read_int(),
            Others = [to_integer(X) : X in split(read_line())],
            do_case(Case_num, Armin, Others)
    end.

GitHub: https://github.com/kit1980/google-code-jam/blob/master/2013/Round%201B/A.%20Osmos/Osmos.pi

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.

For more info about Picat in general see documents in the distribution and http://www.hakank.org/picat/.

Comments

comments powered by Disqus