[rules-users] 8Puzzle problem with Drools Planner
Anderson Rocha
anderson.ufal at gmail.com
Mon Nov 15 15:05:36 EST 2010
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 at 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 at 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 at lists.jboss.org
> >>>> https://lists.jboss.org/mailman/listinfo/rules-users
> >>>
> >>> --
> >>> With kind regards,
> >>> Geoffrey De Smet
> >>>
> >>>
> >>> _______________________________________________
> >>> rules-users mailing list
> >>> rules-users at lists.jboss.org
> >>> https://lists.jboss.org/mailman/listinfo/rules-users
> >>>
> >> _______________________________________________
> >> rules-users mailing list
> >> rules-users at lists.jboss.org
> >> https://lists.jboss.org/mailman/listinfo/rules-users
> >>
> >
> > _______________________________________________
> > rules-users mailing list
> > rules-users at lists.jboss.org
> > https://lists.jboss.org/mailman/listinfo/rules-users
> >
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20101115/4edd46f1/attachment.html
More information about the rules-users
mailing list