Planning automation

[Nartoo Meon]

How to automate planning program?

The predicate final() takes a term, but uses it as a pattern, so, if I put him an instantiated variable before calling plan predicate,  then it didnt work, evaluates empty plan or error, even nothing.

I want to search a plan for various inputs, it painful to manualy write them every time.

 

If I rewrite it for constraint solver(standart modules), this probably, may work...

The question is general, but I'll focus on my program:

import planner.

main =>  solve_puzzle(Start_state).

solve_puzzle => best_plan_unbounded([b,b,b,c,w,w,w],Plan), writeln(Plan), writef("%i+%i\n",Plan.len(),1).

final([w,w,w,c,b,b,b])=>true.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[Y,c|Z],LastS),

  NextS=X++[c,Y]++Z,

  Action=move_R,

  ActionCost=1.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[c,Y|Z],LastS),

  NextS=X++[Y,c]++Z,

  Action=move_L,

  ActionCost=1.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[Y,Z,c|D],LastS),

  NextS=X++[c,Z,Y]++D,

  Action=jump_R,

  ActionCost=1.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[c,Z,Y|D],LastS),

  NextS=X++[Y,Z,c]++D,

  Action=jump_L,

  ActionCost=1.

It solves one simple puzzle
   move black balls "b" and white balls "w" to the opposite side of a list, using one empty space "c" and 4 possible moves: to the near empty space left/right, jump over one ball on empty space left/right. 

These puzzle expands easily, so, I wanted to search solutions for bigger versions. Probably, we can put any amount of white or black balls.. and solution is still exist. Even more empty spaces is possible.

But here is the problem - how to put various data(puzzle version) and call search predicate. Ive tried several solutions, but without succes unfortunately.
Next code is what I want(not working):

import planner.

main =>

  print("Write amount of black balls:"),

  N_black=read_int(),

  print("Write amount of white balls:"),

  N_white=read_int(),

  Start_state=new_list(N_black, b)++[c]++new_list(N_white, w),

  End_state=Start_state.reverse(),

  solve_puzzle(Start_state).

solve_puzzle(Start_state) =>

  best_plan_unbounded(Start_state,Plan), writeln(Plan), writef("%i+%i\n",Plan.len(),1).

final(End_state)=>true.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[Y,c|Z],LastS),

  NextS=X++[c,Y]++Z,

  Action=move_R,

  ActionCost=1.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[c,Y|Z],LastS),

  NextS=X++[Y,c]++Z,

  Action=move_L,

  ActionCost=1.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[Y,Z,c|D],LastS),

  NextS=X++[c,Z,Y]++D,

  Action=jump_R,

  ActionCost=1.

action(LastS,NextS,Action,ActionCost)?=>

  append(X,[c,Z,Y|D],LastS),

  NextS=X++[Y,Z,c]++D,

  Action=jump_L,

  ActionCost=1.

[Hakan Kjellerstrand]

Hi Nartoo.

Here's a way of doing this,. I hope that I've covered all your questions.

In main/0:

"""

main =>

  print("Write amount of black balls:"),
  N_black=read_int(),
  print("Write amount of white balls:"),
  N_white=read_int(),

  Start_state=[b : _ in 1..N_black] ++ [c] ++  [w : _ in 1..N_white], % <-- Using list comprehension
  End_state=Start_state.reverse(),
  cl_facts($[final(End_state)]), % <-- adding the final predicate
  solve_puzzle(Start_state).

solve_puzzle(Start_state) =>
  best_plan_unbounded(Start_state,Plan), writeln(Plan), writef("%i+%i\n",Plan.len(),1).

%  This is replaced with the cl_facts/1 in main/0
% final(End_state)=>true. % <---

"""

It's basically two changes (marked with "<--" above)

* use list comprehension to generate the appropriate number of 'b' , 'c'', and 'w'

* use cl_facts/1 to dynamically set the final/1 clause. Note that the existing final/1 clause must be commented.

Here's a session:

"""

Write amount of white balls:3
[move_L,jump_R,move_R,jump_L,jump_L,move_L,jump_R,jump_R,jump_R,move_L,jump_L,jump_L,move_R,jump_R,move_L]
15+1
"""

And a littler larger instance:

"""

Write amount of black balls:6
Write amount of white balls:5
[move_L,jump_R,move_R,jump_L,jump_L,move_L,jump_R,jump_R,jump_R,move_R,jump_L,jump_L,jump_L,jump_L,move_L,jump_R,jump_R,jump_R,jump_R,jump_R,move_R,jump_L,jump_L,jump_L,jump_L,jump_L,move_R,jump_R,jump_R,jump_R,jump_R,move_L,jump_L,jump_L,jump_L,move_R,jump_R,jump_R,move_L,jump_L,move_R]
41+1

CPU time 0.476 seconds. Backtracks: 0

"""

Hope this helps.

Best,

Hakan

[Nartoo Meon]

Emm, "Note that the existing final/1 clause must be commented. "  but, Why?  cl_facts() predicate rewrites the code itself(program change program), and it needs a "place" to rewrite? 
I even dont know about cl_facts() predicate... it seems, it provides a way to add clauses to predicates and possibly functions ...at a runtime, like a kind of exec() function in python, yes? Sound logical.

Hmm, my best ideas were confirmed, it should have entered data as a pattern, but an instantiated variable can't be used as a pattern, it should enter the data inline, using direct literals.
But this more like rewriting the code every time data changes. And I see, probably, exactly this solution.

bonus
If we have same amount of white & black balls, number of all puzzle states (with start state) equal to perfect square. N_black=N_white=N , then Plan.len()+1=(N+1)² .
Even more - the plan(+start state) seems like some recursion, so here is exact algorythm to solve it, and it must be recursive. I put visual representation if anyone want.

субота, 17 серпня 2024 р. о 20:38:20 UTC+3 Hakan Kjellerstrand пише:

[Hakan Kjellerstrand]

On Sunday, August 18, 2024 at 1:43:10 AM UTC+2 Nartoo Meon wrote:

Emm, "Note that the existing final/1 clause must be commented. "  but, Why?  cl_facts() predicate rewrites the code itself(program change program), and it needs a "place" to rewrite? 

The reason you have to comment the final/1 that was in your code is that it conflicts with the final/1 that is loaded with cl_facts/1. 

Using  the existing

   final(End_state)=>true.

does not do anything, since there's nothing to check that End_state is the reverse of the start state. Thus, the End_state in the final/1 clause - as it stands - does not have anything to do with the End_state in main/0; it must be matched with something is the body of final/1. See below for some alternatives to using cl_facts/1.

The reason I used cl_facts/1 was that it was the - at least for me - the simplest way of adding the End_state dynamically. Perhaps I should have used some of the alternative approaches below.

 

I even dont know about cl_facts() predicate... it seems, it provides a way to add clauses to predicates and possibly functions ...at a runtime, like a kind of exec() function in python, yes? Sound logical.

cl_facts/1 (and cl_facts/2) add facts dynamically to the program, but  - unfortunately - it does not support adding predicates or functions dynamically.

The are some variants to using cl_facts/1.

Add the End_state in a global map and use that in the final/1 clause.  For example:

"""

main =>
  print("Write amount of black balls:"),
  N_black=read_int(),
  print("Write amount of white balls:"),
  N_white=read_int(),
  Start_state=[b : _ in 1..N_black] ++ [c] ++  [w : _ in 1..N_white],

  End_state=Start_state.reverse(),
  get_global_map().put(end_state,End_state), % <--
  solve_puzzle(Start_state).

final(State) => State == get_global_map().get(end_state). % <---

% the rest is as before

"""

 

This is - as using cl_facts/1 - a quick fix.

One other way is to add the end state in the init of the best_plan*/2 predicate and then handle that in both final/1 and also in all action/4 clauses. This is a more general approach than using cl_facts/1 or the global map, since one can then add whatever needed data in init predicate.

Here's an example. All changes are commented with "<--".

"""

main =>

  print("Write amount of black balls:"),
  N_black=read_int(),
  print("Write amount of white balls:"),
  N_white=read_int(),
  Start_state=[b : _ in 1..N_black] ++ [c] ++  [w : _ in 1..N_white],

  End_state=Start_state.reverse(),
  solve_puzzle(Start_state, End_state). % <--  

solve_puzzle(Start_state,End_state) =>  % <--
  best_plan_unbounded([Start_state,End_state],Plan), writeln(Plan), writef("%i+%i\n",Plan.len(),1). % <--

final([State,End]) =>  End == State. % <--

action([LastS,EndS],NextS,Action,ActionCost)?=>   % <--
  append(X,[Y,c|Z],LastS),
  NextS=[X++[c,Y]++Z,EndS], % <--
  Action=move_R,
  ActionCost=1.

action([LastS,EndS],NextS,Action,ActionCost)?=>  % <--
  append(X,[c,Y|Z],LastS),
  NextS=[X++[Y,c]++Z,EndS], % <--
  Action=move_L,
  ActionCost=1.

action([LastS,EndS],NextS,Action,ActionCost)?=> % <--
  append(X,[Y,Z,c|D],LastS),
  NextS=[X++[c,Z,Y]++D,EndS], % <--
  Action=jump_R,
  ActionCost=1.

action([LastS,EndS],NextS,Action,ActionCost)?=> % <--
  append(X,[c,Z,Y|D],LastS),
  NextS=[X++[Y,Z,c]++D,EndS], % <--
  Action=jump_L,
  ActionCost=1.

"""

Hmm, my best ideas were confirmed, it should have entered data as a pattern, but an instantiated variable can't be used as a pattern, it should enter the data inline, using direct literals.
But this more like rewriting the code every time data changes. And I see, probably, exactly this solution.

I'm not sure what you mean by "an instantiated variable can't be used as a pattern" here.  But as the final/1 was in your original program, that doesn't work since there was not anything to match End_state in the body.

 

bonus
If we have same amount of white & black balls, number of all puzzle states (with start state) equal to perfect square. N_black=N_white=N , then Plan.len()+1=(N+1)² .
Even more - the plan(+start state) seems like some recursion, so here is exact algorythm to solve it, and it must be recursive. I put visual representation if anyone want.

Neat!

/Hakan

[Nartoo Meon]

Wooow, thank you it very helpful !!
"But as the final/1 was in your original program, that doesn't work since there was not anything to match End_state in the body." - I remember it.

I've tryed to run program with cl_facts() without commented final(), and... it works. (!)

"Neat!" - I don't know the algorhythm😅, it's just a hypothesis. But pictures gives a clear view, thats going on.

неділя, 18 серпня 2024 р. о 10:38:41 UTC+3 Hakan Kjellerstrand пише:

[Hakan Kjellerstrand]

Hi again.

I wondered about the closed form formula for the number of steps given the number of blacks (B) and number of whites (W).

The formula is simply (B*W)+B+W.

This was found by my symbolic regression program 

   http://hakank.org/picat/symbolic_regression.pi 

together with the data file

   http://hakank.org/picat/symbolic_regression_nartoo_meon_planning.pi

To run it

 $ picat symbolic_regression.pi  symbolic_regression_nartoo_meon_planning.pi

Here's an example output:

"""

  [program = A * 1 + (//(9,9) + A) * B,res = 15,count = 92]
  [program = A + (//(9,9) + A) * B,res = 15,count = 90]
  [program = A * B + (B + A),res = 15,count = 89]
  [program = (//(9,9) + A) * B + A,res = 15,count = 88]
  [program = B * A + (B + A),res = 15,count = 55]
  [program = (//(9,9) + A) * B + (B - A + (A - B + A)),res = 15,count = 44]
  [program = (//(9,9) + A) * B + (//(//(B,B),3 + (5 - 3)) * B + A),res = 15,count = 39]
  [program = B * A + (A + B),res = 15,count = 35]
  [program = A * B + (A + B),res = 15,count = 34]
  [program = B - A + (A - B + A) + (//(9,9) + A) * B,res = 15,count = 30]
  [program = B + A + A * B,res = 15,count = 26]
  [program = (//(9,9) + A) * B + A * 1,res = 15,count = 16]
  [program = //(//(B,B),3 + (5 - 3)) * B + A + (//(9,9) + A) * B,res = 15,count = 15]
  [program = (//(9,9) + A) * B + (A - //(1,10)),res = 15,count = 12]
  [program = A - //(1,10) + (//(9,9) + A) * B,res = 15,count = 9]
  [program = B + A + B * A,res = 15,count = 4]
  [program = (//(9,9) + A) * B - (//(5,//(4 * B,3) + 8) - A),res = 15,count = 1]
  [program = (//(9,9) + A) * B - (B - (B + A)),res = 15,count = 1]
  [program = B + A + B * 1 * A,res = 15,count = 1]
  [program = A + B + B * A,res = 15,count = 1]
  [program = A + B + A * B,res = 15,count = 1]
  [program = (//(9,9) + A) * B + //(A,1),res = 15,count = 1]

/Hakan

[Nartoo Meon]

This is very cool !🤩
So, this program can found exact formula to compute each value in the data file, yes? But we must to know, that our formula uses elementary functions..
May be, you notice, that for W=B, len(Plan)+1=(N+1)²=N²+2N+1, then len(Plan)=N²+2N and is not far away from solution.

Last day I start thinking about further extensions of "my" puzzle. Now in a table instead of a row. Tried some examples by hand and I feel a rise in difficulty.
Probably, becose bigger numbers of balls and much more configurations to play. We can forget jumps, becose it like 15-puzzle now. These strategy needs more moves, obvioustly.
Jumps make the path shorter.  I haven't written a program for it yet... But might do it soon. Just for fun. If anyone wants to give me some advice, it would be appreciated.

See pictures below, its my best manual solutions for first new version. The "no jump" strategy gives a "symmetric" path, but jumps — no. May be, I mistaken somwhere.

I think it might be boring to continue this conversation any further, don't you? We've discussed almost everything.
For now, thank you very much for the help.

bonus(like offtopic)
So, we have simple rules and a big variety of such puzzles. I need this on my smartphone! Looks simple but not so hard(like big 15-puzzle variations).
We even can add "obstacles", where balls cant be, and other colors, but not many of them for nicer look.

Cool idea for the mobile game!..
Picat needs a library(-s) to create windows and GUI for better visual experience! (to make this puzzle in fashion)

вівторок, 20 серпня 2024 р. о 19:45:43 UTC+3 Hakan Kjellerstrand пише: