GPS in Erlang

Posted on by
Contents hide
1 The book PAIP
2 The Model and Potential Problems
2.1 Model
2.2 Recurrent subgoal issue
2.3 The Clobbered Sibling Goal Problem
2.4 The Leaping before You Look Problem
2.5 The Running Around the Block Problem
2.6 The Lack of Intermediate Information Problem
3 The full erlang code
4 Test the Erlang Program
4.1 Simple Test
4.2 Test for Clobbered Sibling Goal Problem
4.3 Test for Leaping before You Look Problem
4.4 Test for Recursive Subgoal Problem
4.5 Test for Monkey & Banana case
4.6 Test for maze problem
4.7 Test for block domain

The book PAIP

GPS is the acronym for General Problem Solver. The book Norvig, Peter. Paradigms of artificial intelligence programming: case studies in Common LISP. Morgan Kaufmann, 1992 spent the whole Chapter 4 to show how you can program a GPS using common lisp and pointed out several “bugs” that you should pay attention to. This is a great book that I highly recommend it.

Since EOPL, I am convinced that Erlang is a very good language to implement other language or write AI paradigm program. My several projects are:

More details on Common Lisp implementation can be found in the open-source repo: https://github.com/norvig/paip-lisp.

The Model and Potential Problems

Model

To solve a problem is to achieve a goal. It may take some actions to fulfil a specific goal with its pre-condition satisfied at the beginning. Thus, actions can bring you to the new state from the old state. And if the new state contains the goal, you win.

Sometimes it is not straightforward to achieve your final goal. The abstract progress shares the same essence of programming language or theorem proving. In fact, we are just writing an interpreter or writing proofs.

Recurrent subgoal issue

To achieve goal 1, we have to fulfil its precondition goal 2, and if goal 2 has goal 1 as its precondition, we might have a deadlock. This is recurrent subgoal issue and it is about the halting problem. The skill used here to void this kind of deadlock is to check at runtime we can never achieve the goal again if we have already in its stack. This leads to turing incomplete language model but keeps the problem simple. We need a runtime info to record the context of the goals.

The Clobbered Sibling Goal Problem

This issue is about side-effect of actions. Suppose an action has several preconditions and we achieve them one by one by taking several actions. Actions have side-effect, it is possible that the first achieved precondition is broken by the last action to achieve the last precondition. But the action’s precondition have to consider as an atom. The skill to solve this issue is to check again after last precondition is achieved.

The Leaping before You Look Problem

This issue is introduced by the first version of gps1 in PAIP that it prints out every action even for some wrong trials. The skill to avoid this is to record every trial’s action into data structure.

The Running Around the Block Problem

This is about some operations that may be redundant. I find it not very interesting so that I skip it now.

 The Lack of Intermediate Information Problem

The is about log. Erlang has logging tool: https://erlang.org/doc/man/logger.html

The full erlang code

The following is the erlang code to implement this. The type specifications and comments should be just like the blog here to show how to write AI paradigms problem in Erlang.

-module(gps).

-export([gps/3, create_op/4, create_school_ops/0]).

%% Goal is just an atom in Erlang

%% A state is a set of goals, we use
%% list to implement state.

%% Action name is also an atom.
%%
%% Operator is a record. The effect
%% of it is modeled as three lists:
%% pre_conds, adds and dels.
-type goal() :: atom().
-type state() :: [goal()].
-type action() :: atom().
-record(operator, {action::action(),
		   pre_conds::[goal()],
		   adds::[goal()],
		   dels::[goal()]}).
-type op() :: #operator{}.

%% Runtime context of subgoals is a stack
%% of goals, we implement stack via list
%% here.
-type stack() :: [goal()].
-type context () :: stack().

-spec create_op(Action::action(),
		PreConds::[goal()],
		Adds::[goal()],
		Dels::[goal()]) -> op().
create_op(Action, PreConds, Adds, Dels) ->
    #operator{action=Action, pre_conds=PreConds,
	      adds=Adds, dels=Dels}.
%%
-spec gps(InitState::state(),
	  Goals    ::[goal()],
	  OpsRepo  ::[op()]) -> {Result::boolean(),
				 State::state(),
				 ActionList::[op()]}.
gps(InitState, Goals, OpsRepo) ->
    Context = empty_context(), %% Context is to solve recurrent subgoal issue
    Actions = [], %% Record each operations is to solve THE LEAPING BEFORE YOU LOOK PROBLEM
    achieve_all(InitState, Goals, OpsRepo, Actions, Context).

-spec achieve_all(State::state(),
		  Goals::[goal()],
		  OpsRepo::[op()],
		  Actions::[op()],
		  Context::context()) -> {Result::boolean(),
					  NewState::state(),
					  NewActions::[op()]}.
achieve_all(State, Goals, OpsRepo, Actions, Context) ->
    case achieve_all_internal(State, Goals, OpsRepo, Actions, Context) of
	{true, NewState, NewActions} ->
	    %% We have to check when finish the last subgoal
	    %% This is to solve the THE CLOBBERED SIBLING GOAL PROBLEM
	    %% And this is why we wrap it arond xxx_internal
	    case is_subset(Goals, NewState) of
		true ->
		    {true, NewState, NewActions};
		false ->
		    {false, State, Actions}
	    end;
	{false, _, _} ->
	    {false, State, Actions}
    end.

-spec achieve_all_internal(State::state(),
			   Goals::[goal()],
			   OpsRepo::[op()],
			   Actions::[op()],
			   Context::context()) -> {Result::boolean(),
						   NewState::state(),
						   NewActions::[op()]}.
achieve_all_internal(State, [], _OpsRepo, Actions, _Context) -> {true, State, Actions};
achieve_all_internal(State, [Goal|Goals], OpsRepo, Actions, Context) ->
    case achieve_single_goal(State, Goal, OpsRepo, Actions, Context) of
	{true, NewState, NewActions} ->
	    achieve_all_internal(NewState, Goals, OpsRepo, NewActions, Context);
	{false, _, _} ->
	    {false, State, Actions}
    end.

-spec achieve_single_goal(State::state(),
			  Goal::goal(),
			  OpsRepo::[op()],
			  Actions::[op()],
			  Context::context()) -> {Result::boolean(),
						  NewState::state(),
						  NewActions::[op()]}.
achieve_single_goal(State, Goal, OpsRepo, Actions, Context) ->
    case lists:member(Goal, State) of
	true ->
	    {true, State, Actions};
	false ->
	    case context_contain(Goal, Context) of
		true ->
		    %% recurrent subgoal!
		    {false, State, Actions};
		false ->
		    NewContext = push_context(Goal, Context),
		    PotentialOps = [Op ||
				       Op <- OpsRepo,
				       lists:member(Goal,
						    Op#operator.adds)],
		    tryOps(PotentialOps, State, Goal, OpsRepo, Actions, NewContext)
	    end
    end.

-spec tryOps(POps::[op()],
	     State::state(),
	     Goal::goal(),
	     OpsRepo::[op()],
	     Actions::[op()],
	     Context::context()) -> {Result::boolean(),
				     NewState::state(),
				     NewActions::[op()]}.
tryOps([], State, _Goal, _OpsRepo, Actions, _Context) -> {false, State, Actions};
tryOps([Op|POps], State, Goal, OpsRepo, Actions, Context) ->
    Pre_conds = Op#operator.pre_conds,
    case achieve_all(State, Pre_conds, OpsRepo, Actions, Context) of
	{false, _, _} ->
	    tryOps(POps, State, Goal, OpsRepo, Actions, Context);
	{true, NewState, NewActions} ->
	    {true, update_state(NewState, Op), [Op|NewActions]}
    end.

%% Internal helper functions
-spec update_state(state(), op()) -> state().
update_state(State, Op) ->
    S1 = add_with_unique(State, Op#operator.adds),
    del_with_unique(S1, Op#operator.dels).

-spec add_with_unique(state(), [goal()]) -> state().
add_with_unique(State, []) -> State;
add_with_unique(State, [Add|Adds]) ->
    case lists:member(Add, State) of
	true ->
	    add_with_unique(State, Adds);
	false ->
	    add_with_unique([Add|State], Adds)
    end.

-spec del_with_unique(state(), [goal()]) -> state().
del_with_unique(State, []) -> State;
del_with_unique(State, [Del|Dels]) ->
    del_with_unique(lists:delete(Del, State), Dels).    

-spec is_subset([goal()], state()) -> boolean().
is_subset(Goals, State) -> lists:all(fun (Goal) ->
					     lists:member(Goal, State)
				     end,
				     Goals).

%% Internal Functions for Context
-spec empty_context() -> context().
empty_context() -> [].

-spec push_context(goal(), context()) -> context().
push_context(Goal, Context) -> [Goal|Context].

-spec context_contain(goal(), context()) -> boolean().
context_contain(Goal, Context) ->
    lists:member(Goal, Context).

%% (defparameter *school_ops*
%%   (list
%%     (make_op :action 'drive_son_to_school
%%       :preconds '(son_at_home car_works)
%%       :add_list '(son_at_school)
%%       :del_list '(son_at_home))
%%     (make_op :action 'shop_installs_battery
%%       :preconds '(car_needs_battery shop_knows_problem shop_has_money)
%%       :add_list '(car_works))
%%     (make_op :action 'tell_shop_problem
%%       :preconds '(in_communication_with_shop)
%%       :add_list '(shop_knows_problem))
%%     (make_op :action 'telephone_shop
%%       :preconds '(know_phone_number)
%%       :add_list '(in_communication_with_shop))
%%     (make_op :action 'look_up_number
%%       :preconds '(have_phone_book)
%%       :add_list '(know_phone_number))
%%     (make_op :action 'give_shop_money
%%       :preconds '(have_money)
%%       :add_list '(shop_has_money)
%%       :del_list '(have_money))))

create_school_ops() ->
    [
     create_op(drive_son_to_school,
	       [son_at_home, car_works],
	       [son_at_school],
	       [son_at_home]),
     create_op(shop_installs_battery,
	       [car_needs_battery, shop_knows_problem, shop_has_money],
	       [car_works],
	       []),
     create_op(tell_shop_problem,
	       [in_communication_with_shop],
	       [shop_knows_problem],
	       []),
     create_op(telephone_shop,
	       [know_phone_number],
	       [in_communication_with_shop],
	       []),
     create_op(look_up_number,
	       [have_phone_book],
	       [know_phone_number],
	       []),
     create_op(give_shop_money,
	       [have_money],
	       [shop_has_money],
	       [have_money])
    ].

Test the Erlang Program

We might add more logs or pre-print the result. But I skip it here.

Simple Test

gps:gps([son_at_home, car_needs_battery, have_money, have_phone_book],
        [son_at_school],
	gps:create_school_ops()).

{true,[son_at_school,car_works,shop_has_money,
       shop_knows_problem,in_communication_with_shop,
       know_phone_number,car_needs_battery,have_phone_book],
      [{operator,drive_son_to_school,
                 [son_at_home,car_works],
                 [son_at_school],
                 [son_at_home]},
       {operator,shop_installs_battery,
                 [car_needs_battery,shop_knows_problem,shop_has_money],
                 [car_works],
                 []},
       {operator,give_shop_money,
                 [have_money],
                 [shop_has_money],
                 [have_money]},
       {operator,tell_shop_problem,
                 [in_communication_with_shop],
                 [shop_knows_problem],
                 []},
       {operator,telephone_shop,
                 [know_phone_number],
                 [in_communication_with_shop],
                 []},
       {operator,look_up_number,
                 [have_phone_book],
                 [know_phone_number],
                 []}]}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

gps:gps([son_at_home, car_needs_battery, have_money],
        [son_at_school],
	gps:create_school_ops()).

{false,[son_at_home,car_needs_battery,have_money],[]}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

gps:gps([son_at_home, car_works],
        [son_at_school],
	gps:create_school_ops()).

{true,[son_at_school,car_works],
      [{operator,drive_son_to_school,
                 [son_at_home,car_works],
                 [son_at_school],
                 [son_at_home]}]}

Test for Clobbered Sibling Goal Problem

gps:gps([son_at_home, car_needs_battery, have_money, have_phone_book],
        [have_money, son_at_school],
	gps:create_school_ops()).

{false,[son_at_home,car_needs_battery,have_money,
        have_phone_book],
       []}

Test for Leaping before You Look Problem

gps:gps([son_at_home, car_needs_battery, have_money, have_phone_book],
        [son_at_school, have_money],
	gps:create_school_ops()).

{false,[son_at_home,car_needs_battery,have_money,
        have_phone_book],
       []}

Test for Recursive Subgoal Problem

gps:gps([son_at_home, car_needs_battery, have_money],
        [son_at_school],
	[gps:create_op(ask_phone_number,
		       [in_communication_with_shop],
		       [know_phone_number],
		       []) | gps:create_school_ops()]).

{false,[son_at_home,car_needs_battery,have_money],[]}

Test for Monkey & Banana case

gps:gps([at_door, on_floor, has_ball, hungry, chair_at_door],
	[not_hungry],
	gps:create_banana_ops())
{true,[not_hungry,empty_handed,on_chair,at_bananas,
       chair_at_middle_room],
      [{operator,eat_bananas,
                 [has_bananas],
                 [empty_handed,not_hungry],
                 [has_bananas,hungry]},
       {operator,grasp_bananas,
                 [at_bananas,empty_handed],
                 [has_bananas],
                 [empty_handed]},
       {operator,drop_ball,[has_ball],[empty_handed],[has_ball]},
       {operator,climb_on_chair,
                 [chair_at_middle_room,at_middle_room,on_floor],
                 [at_bananas,on_chair],
                 [at_middle_room,on_floor]},
       {operator,push_chair_from_door_to_middle_room,
                 [chair_at_door,at_door],
                 [chair_at_middle_room,at_middle_room],
                 [chair_at_door,at_door]}]}

Test for maze problem

-module(maze).

-export([create_maze_ops/0]).

create_maze_ops() ->
    Config = [{1,2},{2,3},{3,4},{4,9},{9,14},{9,8},{8,7},{7,12},{12,13},
	      {12,11},{11,6},{11,16},{16,17},{17,22},{21,22},{22,23},
	      {23,18},{23,24},{24,19},{19,20},{20,15},{15,10},{10,5},{20,25}],
    [create_maze_op(A, B)
     || {A, B} <- Config] ++
    [create_maze_op(B, A)
     || {A, B} <- Config].

create_maze_op(A, B) ->
    SA = integer_to_list(A),
    SB = integer_to_list(B),
    ActionName = gen_action_name(SA, SB),
    PreCondName = gen_at_name(SA),
    AddName = gen_at_name(SB),
    DelName = PreCondName,
    gps:create_op(ActionName,
		  [PreCondName],
		  [AddName],
		  [DelName]).

gen_action_name(A, B) ->
    list_to_atom(
      string:join(["move", "from", A, "to", B], "_")).

gen_at_name(A) ->
    list_to_atom(
      string:join(["at", A], "_")).

Demo result:

gps:gps(['at_1'], ['at_25'], maze:create_maze_ops()).
{true,[at_25],
      [{operator,move_from_20_to_25,[at_20],[at_25],[at_20]},
       {operator,move_from_19_to_20,[at_19],[at_20],[at_19]},
       {operator,move_from_24_to_19,[at_24],[at_19],[at_24]},
       {operator,move_from_23_to_24,[at_23],[at_24],[at_23]},
       {operator,move_from_22_to_23,[at_22],[at_23],[at_22]},
       {operator,move_from_17_to_22,[at_17],[at_22],[at_17]},
       {operator,move_from_16_to_17,[at_16],[at_17],[at_16]},
       {operator,move_from_11_to_16,[at_11],[at_16],[at_11]},
       {operator,move_from_12_to_11,[at_12],[at_11],[at_12]},
       {operator,move_from_7_to_12,[at_7],[at_12],[at_7]},
       {operator,move_from_8_to_7,[at_8],[at_7],[at_8]},
       {operator,move_from_9_to_8,[at_9],[at_8],[at_9]},
       {operator,move_from_4_to_9,[at_4],[at_9],[at_4]},
       {operator,move_from_3_to_4,[at_3],[at_4],[at_3]},
       {operator,move_from_2_to_3,[at_2],[at_3],[at_2]},
       {operator,move_from_1_to_2,[at_1],[at_2],[at_1]}]}

Test for block domain

-module(block).

-export([create_block_ops/1, test/0]).

create_block_ops(Blocks) ->
    Ops1 = [gen_move_from_to_op(A, table, B)
	    || A <- Blocks, B <- Blocks, A /= B
	   ],
    Ops2 = [gen_move_from_to_op(A, B, table)
	    || A <- Blocks, B <- Blocks, A /= B
	   ],
    Ops3 = [gen_move_from_to_op(A, B, C)
	    || A <- Blocks, B <- Blocks, C <- Blocks, A /= B, B /=C, A /= C],
    Ops1 ++ Ops2 ++ Ops3.

gen_move_from_to_op(A, B, C) ->
    Sa = atom_to_list(A),
    Sb = atom_to_list(B),
    Sc = atom_to_list(C),
    ActionName = list_to_atom(string:join(["move", Sa, "from", Sb, "to", Sc], "_")),
    PreConds = [list_to_atom(string:join(["space", "on", X], "_"))
		|| X <- [Sa, Sc]] ++ [list_to_atom(string:join([Sa, "on", Sb], "_"))],
    Adds = case B of
	       table ->
		   [list_to_atom(string:join([Sa, "on", Sc], "_"))];
	       _ ->
		   [list_to_atom(string:join([Sa, "on", Sc], "_")),
		    list_to_atom(string:join(["space", "on", Sb], "_"))]
	   end,
    Dels = case B of
	       table ->
		   [list_to_atom(string:join([Sa, "on", Sb], "_"))];
	       _ ->
		   [list_to_atom(string:join([Sa, "on", Sb], "_")),
		    list_to_atom(string:join(["space", "on", Sc], "_"))]
	   end,
    gps:create_op(ActionName, PreConds, Adds, Dels).

Demo runs:

gps:gps([a_on_b, b_on_table, space_on_a, space_on_table],
	    [b_on_a],
	    block:create_block_ops([a, b])).
{true,[b_on_a,space_on_b,a_on_table,space_on_a],
      [{operator,move_b_from_table_to_a,
                 [space_on_b,space_on_a,b_on_table],
                 [b_on_a],
                 [b_on_table]},
       {operator,move_a_from_b_to_table,
                 [space_on_a,space_on_table,a_on_b],
                 [a_on_table,space_on_b],
                 [a_on_b,space_on_table]}]}

gps:gps([a_on_b, b_on_c, c_on_table, space_on_a, space_on_table],
	[b_on_a, c_on_b],
	block:create_block_ops([a, b, c])).
{true,[c_on_b,space_on_c,b_on_a,space_on_b,a_on_table],
      [{operator,move_c_from_table_to_b,
                 [space_on_c,space_on_b,c_on_table],
                 [c_on_b],
                 [c_on_table]},
       {operator,move_b_from_c_to_a,
                 [space_on_b,space_on_a,b_on_c],
                 [b_on_a,space_on_c],
                 [b_on_c,space_on_a]},
       {operator,move_a_from_b_to_table,
                 [space_on_a,space_on_table,a_on_b],
                 [a_on_table,space_on_b],
                 [a_on_b,space_on_table]}]}

1 thought on “GPS in Erlang”

  1. Pingback: 🐶🐰谜题 | Thoughts on Computing

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.