Hi, I am intrested in making my bot able to "learn" its enviroment as it goes, as opposed to having to start off with a pre-built map. At the momement I am primarily intrested in 2d enviroments only. Does anyone know any good websites/books/papers that discuss dynamically contructing a map of your surroundings? Alan

I am not sure what you mean by "pre-built" map and "unknown environment". On current standards you can use A* path-finding or a few other methods to find a way to a location although this involves having a start and an end, as if the bot knows where it''s going just needs to figure out how. I think that you want to eliminate the end... ? then wouldn''t the bot just move randomly? Or do you want the bot to wander untill it reaches a solution without knowing the map? (Note: This is basicly what happens with standard path-finding anyway)

-------
"Programming is like sex make one mistake, and you have to support it forever."
Homepage: http://students.washington.edu/andrey

Sorry if I wasn''t very clear.

Instead of having my bot load a perfect map of the game level, I want it to have to build the map up as it goes. In this case the bot is a physical robot armed with rangefinder sensors that I am going to use to map out an enviroment (which it has no knowledge of before I turn it on).

I am also intrested in waypoint placement within this generated map, but that wont be for a bit yet.

Alan

Excellent article on your topic:

Knowing the Path

Definetly some good thoughts here. Enjoy.

_________________________________________________________________

Drew Sikora
A.K.A. Gaiiden

ICQ #: 70449988
AOLIM: DarkPylat

Blade Edge Software
Staff Member, GDNet
Public Relations, Game Institute

3-time Contributing author, Game Design Methods , Charles River Media
Online column - Design Corner at Pixelate

Unnoficial IGDA chat! [polaris.starchat.net -> #igda]
NJ IGDA Chapter - NJ developers unite!! [Chapter Home | Chapter Forum]

"Real programmers don''t work from 9 to 5. If any real programmers are around at 9am it''s because they were up all night."
-Anon.

Alan,

There are two ways you can go about this problem. One is to permit your agent access to the state of the map within it''s local environment (everwhere it can see) so that it can add it to it''s internal model. The other is to force it to actually sense the local features and build an internal representation of the map. You probably don''t need to do any more than the former, although the latter is a lot of fun.

The general problem though is how to identify a set of local features in terms of the known map. Has this area been visited before or is it somewhere new? Markov Localisation is a technique for solving this problem.

As for the decision making portion of your agent, you need to decide whether you want the agent to seek a specific goal (even though it might not know where the goal is) or just wander about, perhaps prefering to explore new areas, until it stumbles on the goal. There are many ways to implement each of these approaches and both are about the same level of difficulty.

If you want more advice/ideas on any of this, just holler

Cheers,

Timkin

Thanks for the replies.

quote:
One is to permit your agent access to the state of the map within it''s local environment

I would love to allow my agent access to the state of the map, but my agent is a physical robot, and the enviroment is a random room/area that there is no digital map of :-)

I will look into Markov Localisation as one thing I want to be able to do is store the generated map, and then later locate my position within it.

quote:
you need to decide whether you want the agent to seek a specific goal (even though it might not know where the goal is) or just wander about, perhaps prefering to explore new areas, until it stumbles on the goal

I want the agent to explore new areas, but there is no real goal to achive, just to keep on mapping and to build a navigation mesh so that it can return to any point it has already visited as efficiently as possible.

Alan

Map building and localization happen to be a very active topics currently in robotics. In the most recent ICRA there where about 5 localization session and 4 SLAM (Simultanious Localization And Map building) sessions.
The main problem with building a map in an unknown environment is that in order to build the map you have to know where you are and in order to know where you are you need a map. This is usually solved by taking into account the motion of the robot. At short distances odometry is often accurate enough so you know at least the relative position of the poses of the robot. You can use the change in sensory information to also guess the displacement and use this to correct the odometry. You find many Kalman filter like approaches for this. Also Markov localization is popular among probabilistic robotics people...

It depends very much on what sensors you use on your robot to choose among the many different approaches. I use omni-vision for my map building trick, which i''ll present next week at IROS .

I suggest you look at citeseer and search for "robot localization", "map building" and "SLAM". This will give you enough to read for the next month an maybe longer.....

Once i was made counter-strike bot, very simple and primitive compared to others, but i tested it against other bots and it was evective against realbot and plbot(all bots had set perfect shooting skills, so nearly one shot=one kill).
navigating was very simple:

+++++
+++++
+++++
+++++
+++++

each + = navigation point with its own healht, ammo, weapon supply, and how often bot was killed or kill here.
(nearest nav point got +10 kill ratio, navpoints around gets +9, etc.) each navpoint got their connections with navpoints around (from 1253 you can get up to 1162, left 1254 etc.)
navpoint were 5 iches from each other.
Bot after 10 min usually got all accesable navpoint filled, and can win about 7/10 matches one on one against realbot, and 8/10 aginst plbot.

quote: Original post by AlanKemp
Thanks for the replies.

One is to permit your agent access to the state of the map within it''s local environment

I would love to allow my agent access to the state of the map, but my agent is a physical robot, and the enviroment is a random room/area that there is no digital map of :-)

Alan

You probably already know this from your line of work, but besides the excellent articles here on Gamasutra that have already been referred to there''s an awful lot of excellent robotics stuff out on the web to delve into. The subject has also been covered at a variety of presentations over the years at the GDC.




Ferretman

ferretman@gameai.com
www.gameai.com
From the High Mountains of Colorado

You can check out a little old project of mine. It''s a simulated robot that must find it''s way across a simulated map it doesn''t know about, using only two antennae like sensors that tell it the distance to a wall in two directions (both directions are at a 45 degrees angle to it''s movement path). I''m not sure how well would my robot perform in a real environment, I assumed there were no movement errors (the robot knows it''s exact location at all times, even when he bumps into walls).


P.S. Just use "File/LoadWorld" to start the simulation.