OJ Board

Hello,

can you give some hints on what to learn (algorithms/techniques...) in order to do a program wich allows an artificial agent to

1) go around in a map it doesn't know, learning it

2) the agent is allowed some time to learn the map... then the agent would receive an order (go to position x) and then it would should one of the several ways he knows to go from his position to x - the fastest way for example.

Regarding the ways to represent a map, wich are recommended? Using graphs?



Thanks.

Sounds like a fun and interesting problem. An idea is to keep a list of known areas (or states, an area is either "known" or "unknown"). Known areas can be visited using a shortest path algorithm such as A* or Dijkstra. As for the exploration of / learning the map there are several ways, you can for example use a modified DFS[1] with some fancy human-like heuristics and randomness, so your agent will not traverse the map the same way every execution.

[1] or BFS if you play Dungeons & Dragons.

Thanks for your input.

One other question:

in simulations of this type, where multiple-agents may interact at the same time, how you suggest handling with the situation where two agents get to the same position at the same time?

The map zone could allow multiple agents (example 1 in each direction). However if there is something in the zone that the agents must pick up, one agent must be given priority. Any thoughs?

Thanks.