
Post by Baldur on Feb 11, 2012 11:36:54 GMT 5
Yes, I created this class so I could override the hashCode() function. Then you can control what will effect the hash value. You can't just add the x and y value because then (1,2) is the same as (2,1) so I created a string out of the x and y values and hashed the string, i.e. ( x + ":" + y ).hashCode()
I also implemented the equals() function. Not sure if it's necessary, but I did just in case it was being used somewhere. Maybe the default behaviour is to check if the hashCodes are equal. Not sure.



Post by stephan on Feb 11, 2012 11:55:24 GMT 5
I managed to find a solution using Uniform Cost search. ... There is one problem though. I'm not really sure how I should keep track of the best path (I never implemented BFS in GGP last semester). It's easy when using DFS, because then you know that the most current path is the solution. But using BFS or Uniform Cost the path is broken during search. How should I do that? What I'm doing now is when I find a solution I just put the current node as the "best node" in the parent and work my way to the first node. You do not need to store the best successor node for every single node. You only need to know the goal node. Once you have the goal node, you can simply follow the parent references and collect the actions on the way. This will give you the solution path (sequence of actions to execute) in reversed order.



Post by stephan on Feb 11, 2012 12:01:10 GMT 5
I also found a solution using DFS: ... The search ends when it finds the first path to a goal state. The path is, however, too long to execute so the final score is zero. Should the search keep on going until it finds the shortest solution? No, just stop after you found the first solution. You should of course discuss why this solution is not optimal and what could be done to find an optimal solution (see task 3 of the assignment).



Post by Baldur on Feb 11, 2012 13:58:55 GMT 5
Alright A* completed! (I think ) OK I think I cheated a little bit before with the Uniform Search. I didn't figure it out until I implemented A*. My Uniform Search was basically what A* should be. I used the number of dirty cells to guide the search in Uniform Search instead of using the path cost only. So I made the Uniform search dumber and moved the heuristics to A*. Here are my results for Uniform Search and A*: ########### vacuumcleaner_obstacles_1.gdl ########### Uniform: State Expansions: 492 Maximum Frontier Size: 31 Path Cost to Solution: 48 Search Time: 54 ms Final Score: 57 Now Uniform search only uses the path cost.  AStar (dirt count + path cost) Old Uniform State Expansions: 201 Maximum Frontier Size: 57 Path Cost to Solution: 48 Search Time: 16 ms Final Score: 57 This is pretty much what Uniform Search was before. The search prefers less dirty cells, but if it has to choose between two equally dirty states it falls back to using the path cost.  AStar (dirt distance): State Expansions: 455 Maximum Frontier Size: 44 Path Cost to Solution: 48 Search Time: 33 ms Final Score: 57 Here I'm using the manhattan distance of all the dirty cells to the current location of the agent.  AStar (dirt distance + obstacle penalty) State Expansions: 214 Maximum Frontier Size: 51 Path Cost to Solution: 48 Search Time: 25 ms Final Score: 57 I tried implementing heuristics using penalty for when an obstacle is between the agent and a dirty cell. This found the same solution, but faster. ########### vacuumcleaner_obstacles_2.gdl ########### Uniform State Expansions: 512 Maximum Frontier Size: 27 Path Cost to Solution: 48 Search Time: 39 ms Final Score: 57  AStar (dirt distance + obstacle penalty) State Expansions: 150 Maximum Frontier Size: 52 Path Cost to Solution: 50 Search Time: 16 ms Final Score: 55 First I tried the heuristics which gave the fastest results. This did not find as good a solution as Uniform Search.  AStar (dirt distance) State Expansions: 438 Maximum Frontier Size: 38 Path Cost to Solution: 46 Search Time: 30 ms Final Score: 59 Then I tried only using the dirt distance without the penalty. This found a slightly better solution.  AStar (dirt count) State Expansions: 512 Maximum Frontier Size: 30 Path Cost to Solution: 48 Search Time: 28 ms Final Score: 57 Here I'm just using the dirt count. Similar to Uniform Search  These were all the heuristics I could think of. Well I thought about adding orientation somehow into the mix, but I think that will probably be too complicated and won't improve the results. I could be wrong though



Post by stephan on Feb 11, 2012 14:43:18 GMT 5
Here are my results for Uniform Search and A*: ... Very nice results, especially for the blind search algorithms. I guess removing repeated states helps a lot there. The fact that A* with dirt distance + obstacle penalty returns a worse solution than with just dirt distance as heuristics should tell you something about the heuristics though. Depending on how you implemented A* (discarding revisited states or not), what properties must the heuristics have such that A* is optimal (finds the optimal solution first)? Do these properties hold for your heuristics?



Post by Baldur on Feb 12, 2012 6:32:50 GMT 5
The fact that A* with dirt distance + obstacle penalty returns a worse solution than with just dirt distance as heuristics should tell you something about the heuristics though. Depending on how you implemented A* (discarding revisited states or not), what properties must the heuristics have such that A* is optimal (finds the optimal solution first)? Do these properties hold for your heuristics? I discard revisited states so the heuristic must be consistent. It's not though because the penalty leads to an estimate that is too high and moving the agent to a cell where there is no obstacle between the agent and the dirt gives a much less estimate. This is a triangle inequality, an example of consitency violation. I tried lowering the penalty, but the search never did better than using only the manhattan distance. The distance heuristic is definately admissable because it always estimates the path so that the following holds: 0 <= h(N) <= h*(N)Can I then be sure the A* Search is optimal? I forgot to mention the heuristic also add the manhattan distance between the agent and the home position because the goal state is always at that position. So when all the dirt has been removed the heuristics prefers states closer to the home position.



Post by stephan on Feb 12, 2012 7:04:10 GMT 5
I discard revisited states so the heuristic must be consistent. It's not though because the penalty leads to an estimate that is too high and moving the agent to a cell where there is no obstacle between the agent and the dirt gives a much less estimate. This is a triangle inequality, an example of consitency violation. I tried lowering the penalty, but the search never did better than using only the manhattan distance. The distance heuristic is definately admissable because it always estimates the path so that the following holds: 0 <= h(N) <= h*(N)Does your dirt distance heuristics use the sum of the Manhattan distances to all dirt cells or just the maximal manhattan distance? I believe the sum would not be admissible: Imagine the case of position = (1,1) and dirt at (5,4) and (5,5). The maximum of the manhattan distances should be admissible and consistent. Can I then be sure the A* Search is optimal? If you have an admissible heuristics which is not consistent you must not discard revisited states, otherwise A* is not optimal. If the heuristics is consistent, you can discard revisited states and A* is still optimal. I forgot to mention the heuristic also add the manhattan distance between the agent and the home position because the goal state is always at that position. So when all the dirt has been removed the heuristics prefers states closer to the home position. Again I believe that adding the distance might make the heuristics nonadmissible. Check out this case: home = (1,1), position = (5,5), dirt at (1,5), that is, the dirt is on your way home. Remember: The cost of the optimal solution of a relaxation of the problem is an admissible heuristics. What are the relaxations you are doing? Also, the maximum of two admissible (consistent) heuristics is again admissible (consistent). So, if you have two admissible heuristics you can simply take the maximum value of both and you will get an admissible heuristics that is at least as good.



Post by Baldur on Feb 12, 2012 7:10:42 GMT 5
I forgot to mention the heuristic also add the manhattan distance between the agent and the home position because the goal state is always at that position. So when all the dirt has been removed the heuristics prefers states closer to the home position. Again I believe that adding the distance might make the heuristics nonadmissible. Check out this case: home = (1,1), position = (5,5), dirt at (1,5), that is, the dirt is on your way home. OK, but what if I use the distance from home when there is no dirt left?



Post by stephan on Feb 12, 2012 8:15:22 GMT 5
OK, but what if I use the distance from home when there is no dirt left? Sure, that should work. Also sum of the distance to the dirt and the distance from the dirt to the home location is admissible.



Post by heidar on Feb 12, 2012 12:17:33 GMT 5
Our group has finished implementing the search using BFS, DFS, UCS and A* algorithms
vacuumcleaner_obstacles_1.gdl
BFS State expansions: 13.517 Max frontier size: 1.311 Steps taken: 43 Search time: 230ms Final score: 63
DFS State Expansions: 146 Max frontier size: 96 Steps taken: 99 Search time: 13ms Final score: 7
Uniform cost search State Expansions: 13.523 Max frontier size: 1.291 Steps taken: 43 Search time: 321ms Final score: 63
A* State Expansions: 991 Max frontier size: 219 Steps taken: 43 Search time: 107ms Final score: 63
vacuumcleaner_obstacles_2.gdl
BFS State Expansions: 8.354 Max frontier size: 689 Steps taken: 47 Search time: 206ms Final score: 59
DFS State Expansions: 218 Max frontier size: 94 Steps taken: 95 Search time: 19ms Final score: 11
Uniform cost search State Expansions: 8.604 Max frontier size: 703 Steps taken: 47 Search time: 276ms Final score: 59
A* State Expansions: 1.129 Max frontier size: 148 Steps taken: 47 Search time: 114 Final score: 59



Post by stephan on Feb 12, 2012 13:16:40 GMT 5
Our group has finished implementing the search using BFS, DFS, UCS and A* algorithms ... Very nice results. It looks like the optimal solutions for the two environments have a cost of 43 and 47, respectively. Whoever gets something different from A* should check, what is wrong. Either there is some problem in implementation of the search algorithm or the heuristic does not have the required properties.


ou
New Member
Posts: 7

Post by ou on Feb 12, 2012 14:39:19 GMT 5
I'm having trouble working out how to use DFS and BFS to search for a solutions. When I implemented DFS I did it by allowing states to be revisited instead of marking them as visited. I did this because if you think about it, the robot has to revisit some places in order to clean all the dirt. My version of DFS did not work, it ran for minutes without finding a solution.
Perhaps I am misunderstanding the problem. I am not exploiting the fact that I know where the dirt is, should I do this? Then finding a solution that just travels between each dirt sport should not be a problem.



Post by gudmundurs10 on Feb 12, 2012 17:27:36 GMT 5
But if DFS doesn't remember where it has won't you have a situation where you will go back and forth between a certain space infinitely since it can't tell whether it has already been there? Also it's true if you ONLY remember x and y you cannot revisit certain cells again, however if I go into a cell facing north is that the same as me entering the same cell facing south? Sorry if this is cryptic, trying not to give the answers away


ou
New Member
Posts: 7

Post by ou on Feb 12, 2012 17:32:52 GMT 5
Thanks Gudmundur, that helps. I see now where my thinking was wrong.



Post by stephan on Feb 13, 2012 13:47:53 GMT 5
Ok, I tried it myself and get the following optimal solutions (different solutions with the same number of steps might be possible): vacuumcleaner_obstacles_1: cost 42, score 63, path: [TURN_ON, TURN_RIGHT, GO, TURN_LEFT, GO, GO, TURN_LEFT, GO, SUCK, TURN_RIGHT, GO, TURN_RIGHT, GO, SUCK, TURN_RIGHT, GO, GO, TURN_LEFT, GO, SUCK, GO, TURN_LEFT, GO, GO, GO, TURN_RIGHT, GO, SUCK, TURN_RIGHT, GO, TURN_RIGHT, GO, TURN_LEFT, GO, GO, GO, SUCK, TURN_RIGHT, GO, GO, GO, TURN_OFF] vacuumcleaner_obstacles_2: cost 46, score 59, path: [TURN_ON, TURN_RIGHT, GO, SUCK, GO, TURN_LEFT, GO, GO, TURN_RIGHT, GO, GO, TURN_LEFT, GO, SUCK, GO, TURN_LEFT, GO, GO, GO, GO, SUCK, TURN_LEFT, TURN_LEFT, GO, TURN_RIGHT, GO, TURN_RIGHT, SUCK, TURN_RIGHT, GO, TURN_RIGHT, GO, GO, TURN_RIGHT, GO, SUCK, GO, TURN_RIGHT, GO, TURN_LEFT, GO, GO, TURN_RIGHT, GO, GO, TURN_OFF] heidar: I guess you counted the number of nodes on the path (including the root node) and not the number of actions executed as "steps taken", because you get the same scores.

