Wrong solution

Help
2013-02-23
2013-05-30
  • Karel Durkota
    Karel Durkota
    2013-02-23

    Hello,
      I am a student of CTU in Prague and I am working on my Master Thesis, where I use CSP Solver for finding a solution of Graphplan Algorithm (instead of Backsearching).  I've tried Choco and Minion Solvers, but I feel they are quite slow, and want to implement  JaCoP for comparison and hopefully getting better results, but so far JaCoP returns wrong solution. Could I ask you to look at it? I could not figure out what goes wrong. I used basically the same constraint for the former solvers, and it worked.
    Here is the snippet of the constraints I am giving to the JaCoP:

    ....
    Or135 : Or( XneqC259 : XneqC(goal-(at package2 loc1)::{10..11, 41}, 10 ), And15 : And(XneqC257 : XneqC(level2(in package2 truck1)::{-1, 6}, -1 )XneqC258 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, -1 ),),
    Or136 : Or( XneqC262 : XneqC(goal-(at package2 loc1)::{10..11, 41}, 11 ), And16 : And(XneqC260 : XneqC(level2(at truck2 loc1)::{-1, 19, 23}, -1 )XneqC261 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, -1 ),),
    Or138 : Or( XneqC263 : XneqC(level2dp-(agent2-load-truck ag2 package1 truck2 loc2)::{-1, 55}, 55 ), Or137 : Or( ),
    Or139 : Or( XneqC264 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, 51 ), XneqC265 : XneqC(level1dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, -1 )),
    ....
    

    The main part is the first constraint, which says:
    either

    goal-(at package2 loc1)::{10..11, 41} =/= 10
    

    or

    And15 : And(XneqC257 : XneqC(level2(in package2 truck1)::{-1, 6}, -1 )XneqC258 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, -1 ),),
    

    (or both)
    which originally was an implication:

    goal-(at package2 loc1)::{10..11, 41}=10
    

    => 

    (level2(in package2 truck1)::{-1, 6} =/= -1)  & (level2(at truck1 loc1)::{-1, 18, 25} =/= -1),
    

    . But it's basically the same.
    But unfortunatelly the JaCoP returns me as a solution this:

    Solution : [level2(at package2 loc1)=-1, level2(in package1 truck2)=-1, level2(in package1 truck1)=-1, level1dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)=-1, level1dp-(agent2-load-truck ag2 package2 truck1 loc2)=-1, level2dp-(agent2-load-truck ag2 package2 truck2 loc2)=-1, level2(in package2 truck2)=-1, level2(at package1 loc1)=-1, level2dp-(agent2-load-truck ag2 package1 truck2 loc2)=-1, level1(at truck1 loc1)=-1, level2dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)=-1, level1dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)=-1, level1(in package1 truck1)=-1, level1dp-(agent2-load-truck ag2 package2 truck2 loc2)=-1, goal-(at package2 loc1)=10, level1(at truck2 loc1)=-1, level1(in package2 truck2)=-1, level2dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)=-1, level2(at truck1 loc1)=-1, level2(in package2 truck1)=-1, level2dp-(agent2-load-truck ag2 package2 truck1 loc2)=-1, level2(at truck2 loc1)=-1, level2dp-(agent2-load-truck ag2 package1 truck1 loc2)=-1, level1(at package1 loc1)=-1]
    

    where the most important is that:

     goal-(at package2 loc1)=10
    

    , and

    level2(at truck2 loc1)=-1
    

    and

    level2(at truck1 loc1)=-1
    

    , which was not allowed according to the constraint.
    The whole constraint with the solution follows:

    *** Store
    *** Constraints for evaluation:
    {SimpleHashSet[]
    SimpleHashSet[Or146 : Or( XneqC280 : XneqC(level2(at package2 loc1)::{-1, 11}, 11 ), Or145 : Or( XneqC276 : XneqC(level1(at truck2 loc1)::{-1, 19}, -1 ), XneqC278 : XneqC(level1(in package2 truck2)::{-1, 7}, -1 )),),Or114 : Or( XneqC215 : XneqC(level2(at package1 loc1)::{-1, 8, 40}, 40 ), XneqC216 : XneqC(level2(in package1 truck2)::{-1, 1}, 1 )),Or112 : Or( XneqC211 : XneqC(level2(at package1 loc1)::{-1, 8, 40}, 40 ), XneqC212 : XneqC(level2(in package1 truck1)::{-1..0, 34}, 0 )),Or110 : Or( XneqC207 : XneqC(level2(at package1 loc1)::{-1, 8, 40}, 8 ), XneqC208 : XneqC(level2(in package1 truck1)::{-1..0, 34}, 34 )),Or127 : Or( XneqC241 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 7 ), XneqC242 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, 51 )),, Or160 : Or( XneqC304 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, 18 ), XneqC305 : XneqC(level1dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)::{-1, 50}, -1 )),Or164 : Or( XneqC311 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 39 ), Or163 : Or( XneqC309 : XneqC(level1(in package2 truck2)::{-1, 7}, -1 )),),Or115 : Or( XneqC217 : XneqC(level2(at package2 loc1)::{-1, 11}, 11 ), XneqC218 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 39 )),Or136 : Or( XneqC262 : XneqC(goal-(at package2 loc1)::{10..11, 41}, 11 ), And16 : And(XneqC260 : XneqC(level2(at truck2 loc1)::{-1, 19, 23}, -1 )XneqC261 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, -1 ),),Or140 : Or( XneqC266 : XneqC(level2dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)::{-1, 50}, 50 ), XneqC267 : XneqC(level1dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)::{-1, 50}, -1 )),Or122 : Or( XneqC231 : XneqC(level2(in package2 truck1)::{-1, 6}, 6 ), XneqC232 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 7 )),Or120 : Or( XneqC227 : XneqC(level2(in package1 truck1)::{-1..0, 34}, 0 ), XneqC228 : XneqC(level2(in package1 truck2)::{-1, 1}, 1 )),Or142 : Or( XneqC272 : XneqC(level2(at package1 loc1)::{-1, 8, 40}, 8 ), Or141 : Or( XneqC270 : XneqC(level1(at truck1 loc1)::{-1, 25}, -1 ), XneqC268 : XneqC(level1(in package1 truck1)::{-1..0}, -1 )),),Or132 : Or( XneqC251 : XneqC(level1(at truck2 loc1)::{-1, 19}, 19 ), XneqC252 : XneqC(level1dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, 47 )),Or126 : Or( XneqC239 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, 18 ), XneqC240 : XneqC(level2(in package2 truck1)::{-1, 6}, 6 )),Or149 : Or( XneqC283 : XneqC(level2dp-(agent2-load-truck ag2 package1 truck1 loc2)::{-1, 54}, 54 ), Or148 : Or( ),Or166 : Or( XneqC314 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, 47 ), XneqC315 : XneqC(level1dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, -1 )),Or139 : Or( XneqC264 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, 51 ), XneqC265 : XneqC(level1dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, -1 )),Or119 : Or( XneqC225 : XneqC(level2(at truck2 loc1)::{-1, 19, 23}, 19 ), XneqC226 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, 47 )),Or133 : Or( XneqC253 : XneqC(level1(in package2 truck2)::{-1, 7}, 7 ), XneqC254 : XneqC(level1dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, 47 )),Or135 : Or( XneqC259 : XneqC(goal-(at package2 loc1)::{10..11, 41}, 10 ), And15 : And(XneqC257 : XneqC(level2(in package2 truck1)::{-1, 6}, -1 )XneqC258 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, -1 ),),Or123 : Or( XneqC233 : XneqC(level2(in package2 truck1)::{-1, 6}, 6 ), XneqC234 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, 47 )),Or116 : Or( XneqC219 : XneqC(level2(at package2 loc1)::{-1, 11}, 11 ), XneqC220 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 7 )),, Or147 : Or( XneqC281 : XneqC(level2dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)::{-1, 46}, 46 ), XneqC282 : XneqC(level1dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)::{-1, 46}, -1 )),Or125 : Or( XneqC237 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, 18 ), XneqC238 : XneqC(level2dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)::{-1, 50}, 50 )),, Or165 : Or( XneqC312 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 7 ), XneqC313 : XneqC(level1dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, -1 )),Or129 : Or( XneqC245 : XneqC(level1(at package1 loc1)::{-1, 40}, 40 ), XneqC246 : XneqC(level1(in package1 truck1)::{-1..0}, 0 )),Or144 : Or( XneqC275 : XneqC(level2(at package1 loc1)::{-1, 8, 40}, 40 ), Or143 : Or( XneqC273 : XneqC(level1(at package1 loc1)::{-1, 40}, -1 )),),Or162 : Or( XneqC308 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, 25 ), Or161 : Or( XneqC306 : XneqC(level1(at truck1 loc1)::{-1, 25}, -1 )),),Or158 : Or( XneqC301 : XneqC(level2(in package1 truck2)::{-1, 1}, 1 ), Or157 : Or( XneqC299 : XneqC(level1(at truck2 loc1)::{-1, 19}, -1 ), XneqC297 : XneqC(level1(at package1 loc1)::{-1, 40}, -1 )),),Or118 : Or( XneqC223 : XneqC(level2(at truck2 loc1)::{-1, 19, 23}, 19 ), XneqC224 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 7 )),, Or124 : Or( XneqC235 : XneqC(level2(at truck1 loc1)::{-1, 18, 25}, 18 ), XneqC236 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, 51 )),Or156 : Or( XneqC296 : XneqC(level2(in package1 truck1)::{-1..0, 34}, 0 ), Or155 : Or( XneqC292 : XneqC(level1(at package1 loc1)::{-1, 40}, -1 ), XneqC294 : XneqC(level1(at truck1 loc1)::{-1, 25}, -1 )),),Or128 : Or( XneqC243 : XneqC(level2(in package2 truck2)::{-1, 7, 39}, 7 ), XneqC244 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck2 loc2)::{-1, 47}, 47 )),, Or154 : Or( XneqC291 : XneqC(level2(in package1 truck1)::{-1..0, 34}, 34 ), Or153 : Or( XneqC289 : XneqC(level1(in package1 truck1)::{-1..0}, -1 )),),Or117 : Or( XneqC221 : XneqC(level2(at truck2 loc1)::{-1, 19, 23}, 19 ), XneqC222 : XneqC(level2dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)::{-1, 46}, 46 )),Or152 : Or( XneqC288 : XneqC(level2(at truck2 loc1)::{-1, 19, 23}, 23 ), Or151 : Or( XneqC286 : XneqC(level1(at truck2 loc1)::{-1, 19}, -1 )),),Or130 : Or( XneqC247 : XneqC(level1(at truck2 loc1)::{-1, 19}, 19 ), XneqC248 : XneqC(level1dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)::{-1, 46}, 46 )),, Or159 : Or( XneqC302 : XneqC(level2(in package2 truck1)::{-1, 6}, 6 ), XneqC303 : XneqC(level1dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, -1 )),Or131 : Or( XneqC249 : XneqC(level1(at truck2 loc1)::{-1, 19}, 19 ), XneqC250 : XneqC(level1(in package2 truck2)::{-1, 7}, 7 )),Or113 : Or( XneqC213 : XneqC(level2(at package1 loc1)::{-1, 8, 40}, 8 ), XneqC214 : XneqC(level2(in package1 truck2)::{-1, 1}, 1 )),Or121 : Or( XneqC229 : XneqC(level2(in package2 truck1)::{-1, 6}, 6 ), XneqC230 : XneqC(level2dp-(agent2-load-truck ag2 package2 truck1 loc2)::{-1, 51}, 51 )),Or150 : Or( XneqC284 : XneqC(level2(at truck2 loc1)::{-1, 19, 23}, 19 ), XneqC285 : XneqC(level1dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)::{-1, 46}, -1 )),Or111 : Or( XneqC209 : XneqC(level2(at package1 loc1)::{-1, 8, 40}, 8 ), XneqC210 : XneqC(level2(in package1 truck1)::{-1..0, 34}, 0 )),Or134 : Or( XneqC256 : XneqC(goal-(at package2 loc1)::{10..11, 41}, 41 ), And14 : And(XneqC255 : XneqC(level2(at package2 loc1)::{-1, 11}, -1 ),),Or138 : Or( XneqC263 : XneqC(level2dp-(agent2-load-truck ag2 package1 truck2 loc2)::{-1, 55}, 55 ), Or137 : Or( ),]
    SimpleHashSet[]
    SimpleHashSet[]
    SimpleHashSet[]
     }
    Depth First Search DFS7
    JaCoP.search.InputOrderSelect@105dd2c
    Solution : [level2(at package2 loc1)=-1, level2(in package1 truck2)=-1, level2(in package1 truck1)=-1, level1dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)=-1, level1dp-(agent2-load-truck ag2 package2 truck1 loc2)=-1, level2dp-(agent2-load-truck ag2 package2 truck2 loc2)=-1, level2(in package2 truck2)=-1, level2(at package1 loc1)=-1, level2dp-(agent2-load-truck ag2 package1 truck2 loc2)=-1, level1(at truck1 loc1)=-1, level2dp-(agent3-drive-truck2 ag3 truck1 loc2 loc1)=-1, level1dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)=-1, level1(in package1 truck1)=-1, level1dp-(agent2-load-truck ag2 package2 truck2 loc2)=-1, goal-(at package2 loc1)=10, level1(at truck2 loc1)=-1, level1(in package2 truck2)=-1, level2dp-(agent3-drive-truck2 ag3 truck2 loc2 loc1)=-1, level2(at truck1 loc1)=-1, level2(in package2 truck1)=-1, level2dp-(agent2-load-truck ag2 package2 truck1 loc2)=-1, level2(at truck2 loc1)=-1, level2dp-(agent2-load-truck ag2 package1 truck1 loc2)=-1, level1(at package1 loc1)=-1]
    Nodes : 22
    Decisions : 22
    Wrong Decisions : 0
    Backtracks : 0
    Max Depth : 22
    

    Thank you very much for taking look at it, really appreciate it.
    Karel

     
  • Dear Karel,

    Before I try to figure out the problem, can I ask you for one thing?

    Can you implement your And, Or, XneqC constraints (e.g. Or138) in your first printout as ExtensionalSupport or ExtensionalConflict (whatever has smaller number of tuples or is easier to use for you).

    This approach of using Extensional* constraints may help you immensely in solving your problem efficiently. Or constraint should be used as rarely as possible.

    Each time you implement one type of constraint as Extensional one try to see if the problem persists. As soon as the problem disappears please send the code of your solution to me by email (radoslaw dot szymanek at gmail . com ). I will run few tests to check if there is a bug in JaCoP. It will help to locate the bug/wrong usage pattern, etc.

    Please make sure you are using good quality JVM, with newest bug fixes. I had few times weird behavior because of bugs in JVM.

    best,
    Radek

     
  • kris
    kris
    2013-02-23

    Hi!

    Do you check if your search succeeded? Do you check whether labeling method of DepthFirstSearch returns true?Your printout-out of the store suggests that there are still constraints for evaluation, that means that your search has finished with unconsistent store and your problem has **no solution**.

    To make it short. Check what is returned by labeling method and continue only if the result is true!

    Best regards,
    /Kris

    PS. To implement implication you can use IfThen constraint, for example.