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