|
Post by Baldur on Feb 13, 2012 13:57:56 GMT -5
Ah thanks Stephan. I actually did this myself and found a different one. I deleted my post before I saw yours because I didn't need it anymore. Sorry about that. Anyway I think I've figured out the problem and I'm working on it
|
|
|
Post by heidar on Feb 13, 2012 15:02:24 GMT -5
stephan: I simply wrote the last 'step' number in the GameController application after running the algorithms.
|
|
|
Post by Baldur on Feb 13, 2012 17:51:51 GMT -5
vacuumcleaner_obstacles_1.gdl
DFS: State Expansions: 214 Maximum Frontier Size: 362 Path Cost to Solution: 137 Search Time: 13 ms Final Score: 0
BFS: State Expansions: 2554 Maximum Frontier Size: 118 Path Cost to Solution: 42 Search Time: 112 ms Final Score: 63
Uniform: State Expansions: 2559 Maximum Frontier Size: 121 Path Cost to Solution: 42 Search Time: 108 ms Final Score: 63
AStar State Expansions: 2509 Maximum Frontier Size: 121 Path Cost to Solution: 42 Search Time: 116 ms Final Score: 63
vacuumcleaner_obstacles_2.gdl
DFS: State Expansions: 181 Maximum Frontier Size: 300 Path Cost to Solution: 122 Search Time: 14 ms FInal Score: 0
BFS: State Expansions: 2538 Maximum Frontier Size: 135 Path Cost to Solution: 46 Search Time: 111 ms Final Score: 59
Uniform: State Expansions: 2540 Maximum Frontier Size: 134 Path Cost to Solution: 46 Search Time: 113 ms Final Score: 59
AStar: State Expansions: 2542 Maximum Frontier Size: 138 Path Cost to Solution: 46 Search Time: 120 ms Final Score: 59
I noticed that the state expansions are similar with BFS, Uniform and A*, isn't that something to worry about? Does that mean my heuristics are no good? I noticed Heiðar's team only needed 991 state expansions to a solution in world 1 using A*.
I'm going to try my search on one of the bigger worlds.
|
|
|
Post by stephan on Feb 14, 2012 6:10:36 GMT -5
If the number of state expansion with A* is the same as with BFS/UCS then your heuristics is not helping. Maybe h(s) is the same for most of the states. In that case A* will perform similar to UCS. Slight differences between the algorithms might arise from changes in the order in which you expand states with the same evaluation. This could explain the difference between BFS and UCS, which should be the same otherwise.
You'll probably run out of memory with the big problems unless you have a really good heuristics. I guess I made those environments a bit too hard. I uploaded some with increasing difficulty, so you can see how far you get.
|
|
|
Post by gudmundurs10 on Feb 14, 2012 7:12:40 GMT -5
This is what we have gotten from our algorithms:
Experiments for vacuumcleaner_obstacles_1.gdl:
#DFS: Elapsed time: 35 Cost: 74 Max frontier: 46 State expansions: 174
#BFS: Elapsed time: 97 Cost: 42 Max frontier: 118 State expansions: 2521
#UCS: Elapsed time: 671 Cost: 42 Max frontier: 140 State expansions: 3033
#A*: Elapsed time: 719 Cost: 42 Max frontier: 153 State expansions: 3018
Experiments for vacuumcleaner_obstacles_2.gdl:
#DFS: Elapsed time: 23 Cost: 70 Max frontier: 39 State expansions: 133
#BFS: Elapsed time: 104 Cost: 46 Max frontier: 127 State expansions: 2343
#UCS: Elapsed time: 578 Cost: 46 Max frontier: 147 State expansions: 2749
#A*: Elapsed time: 541 Cost: 46 Max frontier: 146 State expansions: 2731
|
|
|
Post by gudmundurs10 on Feb 14, 2012 12:45:24 GMT -5
Fixed both A* and USC and optimized them
#DFS: Elapsed time: 35 Cost: 74 Max frontier: 46 State expansions: 174
#BFS: Elapsed time: 97 Cost: 42 Max frontier: 118 State expansions: 2521
#UCS: Elapsed time: 149 Cost: 42 Max frontier: 113 State expansions: 2523
#A*: Elapsed time: 145 Cost: 42 Max frontier: 140 State expansions: 2470
Experiments for vacuumcleaner_obstacles_2.gdl:
#DFS: Elapsed time: 23 Cost: 70 Max frontier: 39 State expansions: 133
#BFS: Elapsed time: 104 Cost: 46 Max frontier: 127 State expansions: 2343
#UCS: Elapsed time: 143 Cost: 46 Max frontier: 123 State expansions: 2349
#A*: Elapsed time: 156 Cost: 46 Max frontier: 134 State expansions: 2267
|
|
|
Post by Baldur on Feb 14, 2012 17:53:55 GMT -5
For some reason the ant build produces a broken jar file. I added another jar file to the dist folder in the zip called vacuumagent.jar
|
|
ou
New Member
Posts: 7
|
Post by ou on Feb 14, 2012 17:59:09 GMT -5
vacuumcleaner_obstacles_1.gdl BFS steps:43 score: 63 Max frontier size: 117 State expansions: 7032 Search time: 183ms
DFS steps:85 score: 21 Max frontier size: 99 State expansions: 7032 Search time: 184ms
GoQueue(emphasis on going straight) steps:43 score: 63 Max frontier size: 253 State expansions: 7032 Search time: 184ms
DistanceQueue(Manhattan distance) steps:49 score: 57 Max frontier size: 228 State expansions: 7032 Search time: 190ms
A* steps:43 score: 63 The size of the map is 5 by 5 Max frontier size: 151 State expansions: 7032
vacuumcleaner_obstacles_2.gdl BFS steps:38 score: 36 Max frontier size: 41 State expansions: 1712 Search time: 106ms
DFS steps:64 score: 10 Max frontier size: 64 State expansions: 1712 Search time: 80ms
GoQueue(emphasis on going straight) steps:38 score: 36 Max frontier size: 71 State expansions: 1712 Search time: 77ms
DistanceQueue(Manhattan distance) steps:42 score: 32 Max frontier size: 55 State expansions: 1712 Search time: 76ms
A* steps:38 score: 36 Max frontier size: 42 State expansions: 1712 Search time: 86ms
|
|
ou
New Member
Posts: 7
|
Post by ou on Feb 16, 2012 18:07:38 GMT -5
I fixed my solution
vacuumclenaer_obstacles_1.gdl
DFS Score: 21 Steps: 84 Max frontier size: 78 State expansions: 134 Search time: 74ms
BFS
Score: 63 Steps: 43 Max frontier size: 93 State expansions: 1874 Search time: 980ms
GoQueue Score: 63 Steps: 43 Max frontier size: 170 State expansions: 1686 Search time: 454ms
DistanceQueue Score: 57 Steps: 49 Max frontier size: 136 State expansions: 1343 Search time: 494ms
A* Score: 63 Steps: 43 Max frontier size: 120 State expansions: 1280 Search time: 613ms
vacuumclenaer_obstacles_2.gdl
DFS Score: 39 Steps: 67 Max frontier size: 59 State expansions: 265 Search time: 116ms
BFS
Score: 59 Steps: 47 Max frontier size: 90 State expansions: 1842 Search time: 1067ms
GoQueue Score: 59 Steps: 47 Max frontier size: 169 State expansions: 1691 Search time: 593ms
DistanceQueue Score: 59 Steps: 47 Max frontier size: 112 State expansions: 1645 Search time: 321ms
A*
Score: 59 Steps: 47 Max frontier size: 119 State expansions: 1213 Search time: 468ms
|
|