Hey, the point of this post is to get advice and suggestions (what to read, and so on) to develop a program that will contain AI to allow the following. The objective is having a map with several ways to go to a given location (from any location to any other location). Then we unleach some "agent" whose purpose is to do recognition of the map. We let it go around for some time and then set an objective ("go from your current position to position X") and it does so by taking the best path they know. So this envolves two things, path finding and then learning. Example : ........________ ....(2)/........\___ --X---.......F______\ ...(1)\_____/ The dots are just "spacers". If the agent "knows" the map it will "know" that from zone X to zone F the fastest way is following path (1). Advice is welcome. Thanks.

Here's the easier way I see from what you told us:

You have three component:

-The real map
-The known map
-The agent

The known map is blank at first. As the agent move, you update the known map with information from the real map.

When you tell the agent to go to a point, you can just apply any pathfinding algorithm like A* or D* on the known map, and the agent will effectively take the best way he knows.

Also,
If no path if found, you can make the pathfinding algorithm to return the path to the node that was estimated as closest to the objective. You can make the agent go there, then start exploring to find a path to the original algorithm.

The learning in this problem is easy because it doesnt involve any behavior learning, only data learning...

If you really want to do it by having an agent wander around, take a look at David Gordon's "Ant-Based Pathfinding" project ( http://david.gordon.name/projects/Ant-based%20Pathfinding.pdf ).

Or do you just mean "what's a good way of having an agent that wanders around to explore a map, but uses A* to pathfind if the terrain is known?"

Google SLAM, Simultaneous Localization And Mapping.

Hey,

thanks for your help.

Quote: Original post by me22
Or do you just mean "what's a good way of having an agent that wanders around to explore a map, but uses A* to pathfind if the terrain is known?"

Yes that's the point - altough other pathfinding algorithms are okay.

However, other suggestions are also welcome. this is kind of an open project and I'm mostly gathering ideas and studying techniques - it's a project i'm thinking of developing for a class that gives the freedom to choose what we want to do... just had this idea about cars going around in a city and chosing paths to a location - an dynamic map that the cars don't know at first seams more interesting.

Thanks.

Hello,

while working on a multi-agent version of the initial problem the following problem appeared.

The following is the map when the agents are exploring.

012345
0******
1*i*j**
2******

Now, agents have the possibility to look at the next square in any valid direction so they know if it's walkable/occupied/not valid.

Let's say agents 'i' and 'j' both try to look at 1,3. They see it's empty so they try to move there at the same time (next iteraction).

Some ways to solve this:

1) Agents can look at 2 squares and they can identify the direction of the agent in that square. This way both 'i' and 'j' would avoid moving to 1,3 because they know that the other agent is going there. From here they could calculate a new Path for their next checkpoint (agent i (a->d->e->whateevr), d is ocuppied, get a new path from 'a' to 'e'.) or maybe wait until the space is empty (with a max wait period).

2) Some agents have higher priority and can move before another agent. If an agent is moved into a given square then all other agents that want that square must way for theira turn.

Example: agents are moved in the order they were spawned

while(1){  for(i=0; i<numAgents; i++) {    newPosition = agents.nextMoveInPath()    if (newPosition is empty) {       agents.moveTo (newPosition)       agents.move++ /* so it knows where to fetch the next move in the next iteration */    }  }}

Other sorts of the agent array could lead to different situations (the agent could have a Priority property that would mean he gets first move).

3) Multi-agent squares

Squaresw would allow several agents at the same time.

Example: a square could work like a two way road and allow an agent in each direction. This way two agents could ocuppy the same space at a given time if they are moving in oposite directions.

Any other ideas? Or comments on the previous ones?

Thanks.

I listened to an awesome speach at the Canadian conference on computer and robotic vision (CRV05). The keynote speaker was working on this problem, only with *actual* mobile robots with range sensors. He had a team of autonomous robots that cooperated to map an army building. Can't remember the name of the speaker, I will post later if I find it.

I remember that when they didnt need to exchange information, robots tried to maximize thier distance with each others (i.e spread!). At some point, two robots would move to the same place in order to use each's others map to complete and correct their own.

The whole thing worked in continuous space using a graph of coulds of range data points.