TargetShare Plan and Accomplishments

Current Plan

• Fall 2000- Refine architecture to the point where it can pass the challenge problem. Determine what are the strong and weak points of our approach. Write a paper detailing our approach to dynamic resource allocation as exemplified by the challenge problem.
• Summer 2000- Eliminate PostOffice code and re-engineer our agents to use the "node" communications module provided with Radsim. Re-design agents to use the new communications system. Rip out our equations for determining a target's location based on observations and instead use the tracker module. By the end of the summer we should have a "tracer bullet" system that displays some of the desired functionality, i.e., it can track the target with some accuracy.
• Winter 2000 - Begin transition from our Ants simulator to the Radsim simulator provided by Darpa. Rewrite agent code so they communicate with Radsim enviroment using the given language. Reimplement Target agent as a "virtual" agent. Derive and implement radar target locating equations. Derive and implement radar data "fusion" using Bayes Networks.
• Fall 1999 - Hire graduate students. Begin implementation of example problem domain simulation. Begin design of problem solution, which includes the negotiation protocol, the Bayesian networks, and the integration between them.

Accomplishments

• June 2000
  • We have shown the equivalence between an ANTS resource allocation problem and a service allocation problem, and have then shown via simulation that this problem can be solved optimally by a distributed set of agents using our protocol. A service allocation simulator was built for this purpose.[more]
  • We have determined the precise amount of time and communications needed by the agents to converge to the optimal solution.
  • Rewrote and extended previous agent code to interface with Radsim 1.0 using the "node" and "tracker" modules provided with it. This involved a restructuring of the agent's communications infrastructure. [more]
  • We have formulated a Bayesian approach to target tracking and, by characterizing it in terms of a Hidden Markov Model, have found a dynamic programming algorithms that can solve the tracking problem in quadratic time (as opposed to exponential time). [more]
• March 2000 -Completed design and implementation of initial architecture for our radsim agents (including Target and Sensor agents). Completed initial implementation of dynamic task-allocation protocol. Completed implementation of simple sensor fusion algorithm which Targets can use to determine their location (usually). Formalized Challenge problem as a dynamic task allocation problem, which lead to insights into the problem structure and into new possible approaches. Follow the Radsim links on the left for more information.
• January 2000 - Abandoned (temporarily?) our Ants simulator in favor of Radsim simulator. Started building new agent architecture and algorithms for new problem domain.
• November 1999 - Applet now implements "Blacklist" algorithms and achieves dynamic resource allocation of Follower agents to moving Target agents.
• October 1999 - Demo applet with simple coordination protocol is developed, alpha state.
• August 1999 - Hired several graduate students to work on the project. Started educating them on project goals, programming setup, CVS setup, Java skills, Bayesian networks, and multiagent systems.
• July 1999 - Design example problem to be used for testing system.
• May 1999 - Start of Project. Attend project briefing. Begin design and planning.

Technology Transition