Hi Geoffrey.

Thank you very much for your replies. I was just testing the Drools Planner, and the way it was implemented (with a search approach), I thought it would work with the 8Puzzle problem. I already worked with this problem executing an A* search (http://en.wikipedia.org/wiki/A*_search_algorithm). This search is also usefull to calculate the shortest distance between 2 locations (there is an example in the wikipedia page). So, for now on, I will be carefull with the problems I work with, to be sure they can be solved with Drools Planner =)

Regards,
Anderson

2010/11/15 Geoffrey De Smet <ge0ffrey.spam@gmail.com>
I 've been thinking about this: 8puzzle isn't really a planning problem
as you model it, here's the main problem:
 a planner move != an 8puzzle move
I 'll call a 8puzzle move "a sliding of a number" from now on, to avoid
confusion.

A perfectly valid planner move would basically move 1 to place and 2 to
place 2 and 3 to place 3.
But the whole point of 8puzzle is to find the sequence of valid 8puzzle
"slidings of a number" to come for a certain problem instance to the
final state.

So if you really want to make 8puzzle work in planner, model it differently:
 a possible solution = a sequence of "slidings of a number"
 a move = add or remove "slidings", change a "sliding"s direction or
change the order of "slidings"
 hard score: if after all the slidings, it's not the perfect endstate:
sum of distance each number still have to slide
 soft score: count number of slidings

With kind regards / Met vriendelijke groeten,
Geoffrey De Smet

Op 14-11-10 21:01, Geoffrey De Smet schreef:
> See below.
>
> With kind regards / Met vriendelijke groeten,
> Geoffrey De Smet
>
> Op 13-11-10 19:33, Anderson Rocha schreef:
>> Hi Geoffrey, thanks for your reply.
>
> Overall, 8 puzzle isn't a natural planning problem fit, like bin
> packing, employee rostering, freight routing or even n queens.
> But it should be possible to solve this with planner.
>>
>> When I try the tabu search like you suggested, if I use 7 or 5 in the
>> move tabu, it ends up with a wrong solution, and if I use 3 or 1, it
>> gets into loop. Here is my Drools Planner configuration:
>>
>> <?xml version="1.0" encoding="UTF-8"?>
>>
>> <localSearchSolver>
>>      <environmentMode>DEBUG</environmentMode>
>>      <scoreDrl>/rules/eightPuzzleScoreRules.drl</scoreDrl>
>>              <scoreDefinition>
>>           <scoreDefinitionType>SIMPLE</scoreDefinitionType>
>>       </scoreDefinition>
>>       <selector>
>>           <moveFactoryClass>solver.move.factory.EightPuzzleMoveFactory</moveFactoryClass>
>>       </selector>
>>       <acceptor>
>>           <completeSolutionTabuSize>1000</completeSolutionTabuSize>
>>           <completeMoveTabuSize>7</completeMoveTabuSize>
>>       </acceptor>
>>       <forager>
>>           <pickEarlyType>NEVER</pickEarlyType>
>>       </forager>
>>       <termination>
>>           <scoreAttained>0</scoreAttained>
>>       </termination>
>> </localSearchSolver>
>>
>> I tried out 2 score calculations:
>>
>> 1- The number of 8Puzzle pieces that are out of place.
> that's bad, the score should favouritize solutions closers to the final
> solution
>> 2- The sum of the number of moves that each 8Puzzle piece that is out
>> of place need to do to go to its place. This is calculated with the
>> Manhattan Distance (http://en.wikipedia.org/wiki/Taxicab_geometry).
> that's better. But maybe it's even better to double or exponentialize
> that distance.
> So distance 1 = 1*1 = 1
> distance 2 = 2*2 = 4
> distance 3 = 3*3 = 9
> distance 4 = 4*4 = 16
>>
>> To simplify the Email, I will tell you how I defined the first score
>> calculation. I defined a state as a String, like "6751#2430", where
>> the character '#' is the empty space, that I called white space. So,
>> the final state should be "01234567#". The moves are:
>>
>> 1- WhiteUpMove ->   from "6751#2430" to "6#5172430"
>> 2- WhiteDownMove ->   from "6751#2430" to "6751324#0"
>> 3- WhiteLeftMove ->   from "6751#2430" to "675#12430"
>> 4- WhiteRightMove ->   from "6751#2430" to "67512#430"
>>
>> And here are the rules that calculate the score:
>>
>> rule "0 out of place"
>>      when
>>              $p : Puzzle(gameState not matches "0........")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("0 out of place", $p));
>> end
>
> matches uses regex, that's very unoptimal
> Don't use a String to represent the gameState of the problem, use new
> int[3][3] or even better new NumberEnum[3][3]
>
>>
>> rule "1 out of place"
>>      when
>>              $p : Puzzle(gameState not matches ".1.......")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("1 out of place", $p));
>> end
>>
>> rule "2 out of place"
>>      when
>>              $p : Puzzle(gameState not matches "..2......")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("2 out of place", $p));
>> end
>>
>> rule "3 out of place"
>>      when
>>              $p : Puzzle(gameState not matches "...3.....")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("3 out of place", $p));
>> end
>>
>> rule "4 out of place"
>>      when
>>              $p : Puzzle(gameState not matches "....4....")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("4 out of place", $p));
>> end
>>
>> rule "5 out of place"
>>      when
>>              $p : Puzzle(gameState not matches ".....5...")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("5 out of place", $p));
>> end
>>
>> rule "6 out of place"
>>      when
>>              $p : Puzzle(gameState not matches "......6..")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("6 out of place", $p));
>> end
>>
>> rule "7 out of place"
>>      when
>>              $p : Puzzle(gameState not matches ".......7.")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("7 out of place", $p));
>> end
>>
>> rule "# out of place"
>>      when
>>              $p : Puzzle(gameState not matches "........#")
>>      then
>>              insertLogical(new UnweightedConstraintOccurrence("# out of place", $p));
>> end
>>
>> rule "hardConstraintsBroken"
>>       when
>>           $occurrenceCount : Number() from accumulate(
>>               $unweightedConstraintOccurrence : UnweightedConstraintOccurrence(),
>>               count($unweightedConstraintOccurrence)
>>           );
>>       then
>>           scoreCalculator.setScore(- $occurrenceCount.intValue());
>> end
>>
>>
>> Thanks again,
>> Anderson
>>
>> 2010/11/13, Geoffrey De Smet<ge0ffrey.spam@gmail.com>:
>>> Hi Anderson,
>>>
>>> Try a solution tabu of 1000 and combine it a move tabu of 7 (or even a
>>> smaller prime number), tweak from there with the benchmarker.
>>> How did you define your score function?
>>>
>>> Op 13-11-10 01:27, Anderson Rocha schreef:
>>>> Hi all,
>>>>
>>>> I am wondering if Drools Planner can handle the 8Puzzle problem. I
>>>> once resolved it with the A* search. But I do not know these simulated
>>>> annealing and tabu search that Drools Planner implements. So I am
>>>> having a "Getting stuck in local optima" problem, and depending on the
>>>> start sollution it gets into loop. But if you enter a really simple
>>>> start solution it resolves, because it choose the best scores until
>>>> finish with few steps. If some one can help, let me know what I can
>>>> send (source code, configuration files) to get some help.
>>>>
>>>> Thanks,
>>>> Anderson
>>>>
>>>>
>>>> _______________________________________________
>>>> rules-users mailing list
>>>> rules-users@lists.jboss.org
>>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>> --
>>> With kind regards,
>>> Geoffrey De Smet
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users@lists.jboss.org
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users@lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>
> _______________________________________________
> rules-users mailing list
> rules-users@lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>

_______________________________________________
rules-users mailing list
rules-users@lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users