Agent Searches in the Bay of Biscay

Raymond Hill, Wright State University

Download Presentation

Dr. Hill retired from the military in January, and he first became interested in search theory when he read a book on chaos, complexity, and agent-based modeling. He was a research analyst by trade and has now joined Wright State University where he is conducting research on search theory applications.

Click image for enlargement

The Depart of Defense had interest in agent models. It started with the Project Albert work. At that time they were doing Brawler modeling in Ray's work with the Air Force. They were using this model to help with decision making. There was other agent model work as well, including adaptive interface agents, intelligent software agents and internet agents. We wanted to bring these models up to a higher level. How do we make the models mimic a commander?

Why Higher Level Modeling?

We needed to better capture command and control efforts, command "intangibles", and model learning based on battlefield information. We wanted to focus on actual information use versus perfect use. Agents and agent models hold promise but bring along many issues.

Agent Modeling Challenges

One challenge is output analysis. This is a new type of output, how do you model human behavior in modeling? How do the agents represent human behavior modeling? If you have models and dots that represent troops, how are they going to work? We have to get beyond low level models and create more campaign level models. How do we interact agents into elements of the model?

Another challenge is human interaction with models and the visual impact of interaction among the agents. How do we use this information to gain insight that is defendable? The models need to have verification, validation and accreditation. How do we ensure that the model is embedded into the code?

The Project

We needed a case for agent models. Dr. McCue's book "U-boats in the Bay of Biscay" was a great example of operational analysis. Since there was lots of information available, the Bay of Biscay became a great scenario for agent modeling and a basis for subsequent research.

Efforts Completed

Below is a list of the efforts completed on this research.

• Capt Ron "Greg" Carl (masters thesis) Search theory focus - finished
• Capt Joe Price (masters thesis) Game theory focus - finished
• Subhashini Ganapathy Optimization study - finished Entering PhD candidacy
• Lance Champagne Dissertation defense in early Fall

Methodology

The Bay of Biscay is a great example of the use of technology. It was a two-person, zero-sum game with the players being the Allied search crafts and the German U-boats. The information was not perfect for this game. Neither side knew the exact strategy of the other side.

First of all, the objective of the Allies was to maximize the number of U-boats detected, while the German goal was to minimize the number of detected U-boats.

The German U-boats have surfacing strategies. They had to surface every three hours to charge their battery. So, should they surface at day or night? Should the Allies search during the day or at night?

Game Formulation

Next, we need to determine the game formulation. The Allies have two pure search strategies. They can search only during the day or only at night. The Germans also have two pure strategies of only day or only night. The next step is to include mixed strategies and simple adaptation algorithms that could adjust each month based on the strategy of the previous month.

There is a equilibrium point where neither side can improve. The allies search 70% of the day and Germans surface 50% during day and 50% during night.

Adaptation Experiment

We then added adaptations to the experiment:

• Both sides can adapt strategies (simple model)
• Three design points chosen:
• Adaptation occurs every month Investigate results 20 replications; 12-month warm-up;
• 12 months of statistics collection (April 1943-February 1944)

Adaptation Convergence

After a period of time there became a converged strategy over six months time. The results were 50% of the time for Aircraft strategy and 20% for the U-boat. We only varied the amount of time surfaced not the technology .

Methodology Search Portion

We then look at the theoretical search portions. Before any of these agent models were built we looked at certain resources.

Design data compiled according to hierarchy

• Historical fact
• Published studies
• Data derived from a raw number
• Good judgment

MOE is number of U-boat sightings

• U-boat density constant between replications
• Aircraft flight hours same between replications
• Therefore, sightings = search efficiency

Two cases; search regions don't overlap, do overlap

Search Regions

We had a certain phase in our research to look at the search regions that overlap and those that do not overlap. Most search theory shows that you should not overlap your search patterns.

We created a grid of the search area. There are U-boats underneath the grid. How many U-boats can we find if we search the grid with non-overlapping patterns? What if we overlap these search patterns so some areas are being double searched?

In a non-overlapping search, it is agreed that it is best to have square and creeping line patterns. In this search your mean sightings would be 105.9.

If you overlap the search, you have more opportunity to find the U-boats crossing the patterns. The best search patterns for overlapping search regions was the square and parallel. The average mean sighting was 122.1.

Future Applications

Some future applications are the Coast Guard water efforts or Air Force UAV search in rugged terrain. Other applications include situations where Human-in-the-loop issues permeate. Some of these could be search and rescue using UAVs, reconnaissance using UAVs, and combat missions using UCAVs.

Future Efforts

Those were two efforts. We have some future efforts for applying agent models:

• Champagne completing dissertation
• Ganapathy starting candidacy
  • Looked at simulation-based optimization
  • Examining human-mediated optimization techniques
  • Application to search and rescue or operational routing
• Extensions planned
  • Extend game theory aspects
  • Further refinement of search results and optimization use

   

Discussion

We may have to build a model within another model. People using agent based models are using them for the wrong purpose. We are at a place today that we should be exploring and not finding solutions. Using an agent based model to understand the aspects of speed. To get to the accreditation, you have to show that your model has reasonable behavior. They are saying that there is not perfect validation. If you want to sink a lot of money into a model, try to validate it.

What makes an agent based model "good enough". This has not been defined yet. We want to take agent based models output and compare it to actual data from real situations. What the model showed in relation to the actual historical data? Did the model capture historical data?

In essence, if you run the scenario over and over, you will see many different outcomes. The thread gets lost in the output. You have to grow the outcome.

It is difficult to model something that has happened. Are your agents doing what the real people did? Did the U-boats do anything stupid? We have to get to the point where we shift the burden of proof.

These agent models are not replicable, so there is a tradeoff between exploration of an idea (great variation between model runs) and exploitation for engineering.

What is the role of the human in the loop?What is the contribution of human mediated optimization techniques?