CSCE 782: Problem Set 2

Due: Wednesday, 18 September 2002 @2:30pm

Upload Problem Set

Target Tracking

Figure 1: Click on the image in order to see the applet and get the source code

This problem set is inspired by DARPA-sponsored project we, along with MAS researchers from other universities, worked on. The problem involves a set of radars laid out in a field and their need to coordinate in order to track some moving targets. For the purposes of this problem set I have simplified the problem (namely by not adding noise to the sensors) but kept the parts of it which make it hard to solve.

The field is filled with radars in a grid layout. Each radar is 5 units away from the other ones. A radar can point in any direction (this is different from the original problem) and has a viewing angle of radar-amplitude. The radars can only see targets that are less than 5 units away. In general, we need two or three radars looking at a target in order to track it. As such, I have implemented a utility function for each target which returns 0 if there are no radars tracking it, 1 if there is 1 radar, 5 if there are 2 radars, and 7 if there are 3 or more radars tracking it.

When a target appears it has a target-type of "unknown". Once three or more radars track it at the same time it will either die, if it was really a phantom, or it will change its target-type to "real". The utility that is shown in the graph and box is the sum of the utilities calculated for all real targets, excluding those that are phantoms.

Your task, should you choose to accept it, is to implement a coordination method for the radars so that they can maximize the utility. When grading the quality of your solution I will be considering:

Utility.
Amount of information that radars need to make decisions (less is better).
Amount of communications between radars (less is better).
Robustness as I increase the number of phantoms and kill of radars.

References

The following papers detail some of the methods used to solve the original radar challenge problem. These methods are more complicated than what you need to implement. They can, however, provide an inspiration for your efforts.

Charles L Ortiz and Timothy Rauenbusch. Dynamic negotiation. 2002.
Paul Scerri, Pragnesh Jay Modi, WeiMin Shen, and Milind Tambe. Applying Constraint Reasoning to Real-world Distributed Task Allocation. In Proceedings of Autonomous Agents and Multi-Agent Systems Workshop on Distributed Constraint Reasoning, p. 134--141, 2002.
José M. Vidal. A Method for Solving Distributed Service Allocation Problems. 2002.

Submission Instructions

This problem set is to be done individually. You cannot ask or receive help from anyone. As will all the problem sets, you will hand them in using our department's dropbox. For the netlogo problem sets you will hand in only one file, your .nlogo file. You will use the information tab of the program for writing your detailed explanation of the techniques you used, how the program works, how to set the controls to obtain the different behaviors you want to show, etc. The information tab needs to start with:

Name: email: ID: I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation. I certify that I have neither given nor received unauthorized aid on this problem set.

Questions

José M. Vidal

Last modified: Wed Sep 4 07:27:28 EDT 2002