Praktikum Autonome Agenten

Project1: Evidence Grids for efficient exploration and target selection

Part I - Evidence grids

Function:
An evidence grid is a grid representation of the state space that assigns to each cell a probability. Implement an evidence grid that represents the agent’s current belief about the location of objects of interest in the RoboCupRescue domain, such as “burning buildings”, “buried civilian” and “blocked road”. The module has to provide methods for updating the grid by evidence given from the senses of the agent, such as: “heard civilian”, “broken building” and “free path”. An evidence has to be given by a probability distribution over the objects of interest (houses or street nodes) or a single probability assigned to one object only. For each kind of evidence there has to be a particular sensor model in order to update the grid.

Approach:
Bayesian update by Occupancy grids, kd-trees, r-trees. See:

M. Martin and H. Moravec. Robot Evidence Grids. Technical Report CMU-RI-TR-96-
06, The Robotics Institute, Carnegie Mellon University, March 1996.

W. Burgard, D. Fox, M. Moors, R. Simmons, and S. Thrun. Collaborative multi-robot exploration. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, 2000. IEEE

J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509--517, September 1975.

Implementation:
The data structure has to be efficient in performing updates from senses and region queries. Therefore data has to be stored in a kd-tree or a r-tree like data structure. This is particularly valuable if agents want to communicate areas they have explored or areas they plan to explore. Suppose the agents did an equal clustering of the state space, then it would suffice to communicate the cluster number and the assigned utility/probability rather than the whole set of objects contained in the cluster. Furthermore it will be more efficient to store only visited objects during early stages of the exploration and to represent complete areas by a single value (e.g. 0 if there is no civilian) at later stages of the exploration.

It is important to examine carefully the range an agent is able to sense if visiting a place before implementing the according sensor model.

The module has to be realized by java interfaces for an easy adaptation of the code to other agent types.

Part II - Exploration

Function:
The problem of exploration can only be poorly solved by a simple random strategy. Particularly in a multi agent scenario it turns out to be important to guarantee that areas in the state space are only explored once. In the case of evidence grids, where there is evidence for partitions of the state space, it makes sense to make use of this evidence to explore the environment more efficiently. This can be achieved by assigning a utility to each cell. However, there exists a trade-off between the cell utility and the cost of reaching the particular cell.

Another trade-off inherent in the problem is to decide whether to reduce the entropy of unexplored regions or to focus the search on areas with high utility. Clearly, to decide between the exploitation of given knowledge and the exploration of an unknown terrain. The optimal setting probably depends on the time of the simulation and the number of agents assigned to the exploration task.

Approach:
W. Burgard, D. Fox, M. Moors, R. Simmons, and S. Thrun. Collaborative multi-robot exploration. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, 2000. IEEE

W. Burgard, D. Fox, and S. Thrun. Active mobile robot localization by entropy minimization. Proc. of the Second Euromicro Workshop on Advanced Mobile Robots (Eurobot). IEEE Computer Society Press, 1997

Implementation:
Implement a function that calculates an utility U for each cell of the evidence grid. The function should be dependent to the number of assigned agents and simulation cycles at time t.

Implement a function that chooses the area with the highest payoff e.g. the area which is safely and fast reachable but leads to high utility.

Implementation:
Implement a simple communication interface that allows to send messages from the agents to the station and to broadcast from the station to the agents.
Implement an additional method for integrating information communicated by other agents (e.g. explored cluster regions) to the belief.
Modify the utility function from part II so that it assigns low utilities to areas explored by other agents (which have also to be communicated).

Deliverables:
Diagrams that shows the averaged number of targets found per cycle with each method on different map sizes.