Learning and remembering an environment
Author
An agent is placed inside of an unknown environment with boundaries. It begins to wander around the environment. It has no previous knowledge of its world. How can we build a memory map of the environment so that the agent can determine if it has already been some place and can, after some wandering, have a complete and accurate mental image of the world?
My first thoughts were to enter at a set location let's say (x=0,y=0). This first position is entered into a dynamic array (or some other data structure). A constant radius value will be assigned for every point in the list which represents the area around the point. At every step we could check to see if the agent's position is already in the map (within the nearest point's area). If not then add the new point to the list.
One of the problems with the above implementation is that we would need to iterate through the list O(n) and check the distance formula for every point in order to determine the nearest known point before checking to see if it is within the known area. This becomes very bad as the size of the environment increases.
I'm sure this has been done before but I'm unsure of an optimal implementation. Any ideas?
Neil
[edit]I forgot to mention that I'm using C++[/edit]
[Edited by - noaktree on July 29, 2005 11:12:53 AM]
Well, if your intention is to just store knowledge of the locations where the agent has been and then search through them, then you could easily implement a constant search with a hash table.
You could calculate the hash value for the index into the hash table using both the x and y coordinate of the location.
You could calculate the hash value for the index into the hash table using both the x and y coordinate of the location.
Anyway, what exactly are you going to have this agent ask? What kind of knowledge will it have to query?
If the agent has knowledge of it's environment, then I would suppose that it would ask questions like, "Where is the nearest tree?", "How far am I away from the player (assuming there is one)?", "Where did I last see the player". If everything is based on position and distance, then having some sort of multi index hash table would be acceptable. You could base it on some sort of location class/struct. You could associate a text string with a location so you could do something like this:
You could store and access just about anything's location doing this. You could even store and search a specific location like this:
All of that would be pretty easy to implement. Though, if you need your agent to ask more than just location based questions, then you might want to look into semantic networks since it would allow you to add in a broader range of infomation in the language you are using.
If the agent has knowledge of it's environment, then I would suppose that it would ask questions like, "Where is the nearest tree?", "How far am I away from the player (assuming there is one)?", "Where did I last see the player". If everything is based on position and distance, then having some sort of multi index hash table would be acceptable. You could base it on some sort of location class/struct. You could associate a text string with a location so you could do something like this:
if(knowledge.find("food", location_list)){ // iterate through returned locations for the closest one known}if(knowledge.find("tree", location_list)){ // iterate through trees known}You could store and access just about anything's location doing this. You could even store and search a specific location like this:
location loc(20,20); std::stringstream str_loc;str_loc << "location{" << x << ',' << y << ')';knowledge.store(str_loc.str(), loc);if(knowledge.find(str_loc.str(), location_list)){ // Do whatever}All of that would be pretty easy to implement. Though, if you need your agent to ask more than just location based questions, then you might want to look into semantic networks since it would allow you to add in a broader range of infomation in the language you are using.
Author
Quote:Well, if your intention is to just store knowledge of the locations where the agent has been and then search through them, then you could easily implement a constant search with a hash table.My intention is to build a mental image of the landscape itself. Nothing else (trees, rocks, etc). Just the shape of the world for now. In which case I'd need a fast search which would return the nearest point to a point given in the "whatever" structure of points. Would a hash table allow this search? I won't be storing every vertex where the agent has been, just points with an area of n radius around them.
You could calculate the hash value for the index into the hash table using both the x and y coordinate of the location.
Ok, I think I understand what you are trying to do. Tell me if I have this right:
1. I draw a point on a map and draw a circle around it.
2. If I move outside of the radius of that circle, then I check whether I am in another existing circle.
3. If I am in an existing circle, then I identify myself as being in that circle.
4. If I am not in an existing circle, then I create a new point with a circle around it.
5. Goto step 2.
You might not want to have an agent explore using such a process. You would probably have to check all of the circles when you leave one. Also, there are possibilities that some circles are never revisted, because they are overlapped by several other circles.
Instead of using circles (which would be radius measurements), why not build the agent's representation of the world as a grid? This way, you wouldn't run into spaces that overlap. Also, the nearest node would be one of 4 or 8 directions (not sure if you would have diagonal movements) regardless of the size of the map. This would make the search constant. Leaving one of the boxes would be just as easy to check as leaving the radius of a circle too.
1. I draw a point on a map and draw a circle around it.
2. If I move outside of the radius of that circle, then I check whether I am in another existing circle.
3. If I am in an existing circle, then I identify myself as being in that circle.
4. If I am not in an existing circle, then I create a new point with a circle around it.
5. Goto step 2.
You might not want to have an agent explore using such a process. You would probably have to check all of the circles when you leave one. Also, there are possibilities that some circles are never revisted, because they are overlapped by several other circles.
Instead of using circles (which would be radius measurements), why not build the agent's representation of the world as a grid? This way, you wouldn't run into spaces that overlap. Also, the nearest node would be one of 4 or 8 directions (not sure if you would have diagonal movements) regardless of the size of the map. This would make the search constant. Leaving one of the boxes would be just as easy to check as leaving the radius of a circle too.
Circle - man ?
I mean, circles are very useful. look at the wheel for example. the same wit`h ai
I mean, circles are very useful. look at the wheel for example. the same wit`h ai
ACCU what was the point of that post you have made lots of pointless posts lately in this forum.
The prevalent solution to this problem is called SLAM: Simultaneous Localisation And Mapping. There is a wealth of information on implementation methods for SLAM online. It should give you more than enough information for your needs in a simulated world.
Author
Thank you Zefrieg and Timkin. If you would like to follow my progress on this topic then check out my journal page. [smile]
SLAM is an open issue. Up to now there is no close solution to the SLAM problem, except with very little maps. I think SLAM-related techniques are not suitable to game programming yet. A better solution would be based on grid-based map, provided that ur agent is able to determine only by its movements where it is.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
