RadSim Challenge Problem
|
| Screen dump of Radsim simulator with our changes. The red circles are the targets. The green circles are our guesses at the targets' locations. |
|
|
| Screen dump of Radsim simulator with our changes. The red circles are the targets. The green circles are our guesses at the targets' locations. |
RadSim is a simulator which implements the Challenge Problem. The simplest Challenge Problem consists of a a field with radars and moving targets. Each radar can be positioned in one of three orientations. The radars return an amplitude and frequency (Doppler shift) from each target on their field of view. From these values we can determine and arc---the target can be anywhere on this arc.
The challenge is to determine the exact location of all targets as they move in the field while using the least amount of resources (i.e. battery power) possible.
2. General Approach
We divide the problem into three subproblems:
Both of these problems are solved by our Dynamic
Constrained Service-Allocation with Teams protocol. While our protocol
solves the two problems, we still separate the static and
dynamic concerns because there are mathematical tools available for
the analysis of the static problem. The dynamic problem can only be
studied via simulation (which we will do).
2.1 Target Creation and Death
A target agent's sole purpose is to keep track of the location of
the mobile object it represents. It embodies our desire to know
the location of a target, as well as our know-how for determining
this location from all the available data.
2.2 Locating the Target
|
| Graphical representation of the radar data. Each line (path) represents one radar return. In this case, the target is located at the intersection of three paths (one from each sensor). |
After using our exchange protocol, each target will receive a number of returns (i.e. readings) from the sensor agents from which it must extract its location. For our initial implementation we assume that:
In the future, we plan to relax some of the assumptions above. The target will then use Bayes Networks to determine a probability distribution over the set of possible locations it could be in.
Assuming that we have one target associated with each mobile object, we can formalize this problem using some notation. Let S be the set of sensors, where s1, s2, ... ,s|N|, are each of the individual sensors. Similarly, let T be the set of target agents and t1, t2, ... t|T|, be the individual targets. The problem now is to find an allocation A = {{si, sj ...}, {sl, sm ...}, ......} where the first subset is the set of sensors looking at t1 and so one.
The set of possible allocation is constrained by the location of the mobile objects and the fact that sensor can only look in one sector at a time. This set of constraints is given by C. C(A) is true if and only if the allocation A does not violate any constraints. Notice that the global set of constraints can be satisfied if each sensor satisfies its own constraints. That is, if all sensors find that A does not make them violate a constraint (e.g. looking at two sectors at the same time) then the global constraint is satisfied.
The solution is given by a global utility function G(A) which reaches a peak when all the targets are viewed by at least two sensors (we need at least two sensors to determine the location of a target, see locating the target), and decreases as more targets are left without cover. This function also assigns more value to an even allocation, that is, it is better to assign 5 sensors to one target and 5 to another than to give 2 to the first and 8 to the second (the target agents can take advantage of this redundancy to update their position more frequently and reduce errors).
Our task, as multiagent systems engineers, is to develop a protocol the agents can use to reach the A which maximizes G(A). Since we made the initial decision of implementing actual target agents, this task has been made much simpler. We simply assign each target agent a utility function Ut(A) which equals:
Given these individual utilities, we now need to define a protocol which the agents can use to try and change the current allocation to increase their individual utility but without violating any constraints, we show that protocol in the Dynamic Service Allocation section.
A great deal of insight can be had if we use the "fitness
landscape" metaphor and picture each of the A's as one point in
this plane whose height is given by G(A). Furthermore, the fact
that our G(A) equals the sum of all Ut(A) means that
this fitness landscape is very similar to Kauffman's
NK
landscapes, where it has been shown that a global optima can
be found faster if groups of agents act selfishly as a group. It
remains to be seen whether these results will hold in our
domain, which differs from the NK model because of the set of
constraints C that we must impose on the agents.
In order for the sensor agents to determine which target they
will look at, we have developed an extension to the basic
contract-net protocol which makes it more suitable to dynamic
service domains such as this one.
In our protocol, the target agents constantly send bids to the sensor
agents. The bids are simply the marginal utility the agent expects to
receive if the sensor agrees to take a reading in the target's
direction. The longer its been since a target agent refreshed its
location, the higher the utility will be. The sensors pick the bid
with the highest utility (if any) and take that measurement. They then
send the results to all the target agents that could benefit
from it. Since this is a cooperative system, we want to allow the
agents to share as much information as would be useful.
The agents' current algorithms are:
2.4 Dynamic Constrained Service-Allocation with Teams
Algorithm: Sensor agent (Sensor.java)
Targets; //vector of known targets, includes location, bid,
// and initial observation (if known)
while (true) {
foreach amplitude returned by radar
If one of the known Targets is on/near the amplitude path
then continue
If the amplitude is similar to one of a target I just created
but who does not know its position yet
then continue
Create a new Target agent,
start it running,
tell it about the observation (sensor location, amplitude)
tell it about the locations of all sensors.
Foreach msg received from a Target agent
If target is unknown,
add it to the list of known targets
If its a request,
change the agent's current request to this one
If its a location,
change the agent's current location to this one
If its a dead message,
remove target from list of known targets.
If ready to send a new requestformeasurement
pick the request with the highest utility and scan that sector
If no utilities > -1, pick a sector randomly.
}
Algorithm: Target agent (Target.java)
Location; //where I think I am
Observations; //vector of observations received by sensors, timestamped
// expire when old, new observations from sensor override old.
Tell all the sensors not in Observations to send me data
While (true){
Foreach msg received from sensor
If msg is observation then add it to Observations
Expire old Observations;
If its time to refresh my location
Send a bid to all sensors to look my way. Bid is amount of time
since my location was updated.
Determine Location based on Observations;
Given that we know the speed of the target, we can determine its
location with amplitude and frequency readings from two sensors.
There will be many intersections. Pick the one with the highest
score = 2*(# times this point comes up as an intersection) -
(distance from this point to old location).
Tell all sensors where I am.
If I have not been able to figure out where I am for a while,
tell all the sensor agents that Im dead.
die.
}
One problem with this solution is that it might lead to "flip-flops". That is, in a situation where two targets each need one of two available sensors, the two sensors could decide to both handle the same target. In order to avoid this and other similar problems, we propose that targets change their utility function to be the sum of the utilities of the targets in their team. Where the team is defined by physical proximity or some other desirable heuristic.
The team extension has not been fully developed yet.