Introduction
and Welcome
Jeff
Cares, Alidade Incorporated
Welcome
to the third annual New Horizons in Search Theory Workshop. In the Navy,
there is a tradition of literally "welding" everything together.
What
we want to do is take these structured platforms that are welded together
and break them up, so that everything is broken up and interacting with
each other.
Click
image for enlargement
New
Horizons in Search Theory: From Abstraction to Application
1st
Annual Workshop
In
our first year, we explored Search Theory itself. Search Theory was developed
when operators and academics collaborated to apply mathematics to a very
tangible task (ASW). The early successes contributed to the foundations
of OR. This field now consists of two types of professionals, the analysts
who work directly with operators and the academics who develop new mathematical
results. These two groups have diverged. The OR Analysts continue to ply
their trade, mostly in ASW. And the Academics have gravitated to extraordinarily
abstract results in complex multivariate mathematics.
(Below
is an overview of the presentations from the first years.)
A
Conversation about Searches
Dr.
Brian McCue, Center for Naval Analyses gave a presentation on the overview
of Search Theory in ASW operations that discussed physical and nonphysical
searches and means of estimating the numbers of targets that were not
detected.
Hard
Search Problems: Recent Developments in Heuristic Optimization
Dr.
Jose Lobo, Cornell University focused on business applications of search
processes.
Multi-Paradigm Optimization
William
Macready, Bios Group discussed matching the biases inherent in an algorithm
with the nature of the problem being addressed.
The
Art, Science and Politics of Modeling Combat
Dr.
Martin Shubik, Yale University presented on art, science and politics
in getting things done in defense circles. He also discussed how the growth
of technology has created an "opaqueness in understanding what we
are doing".
Genetic
Range Dependent Algorithm for Search Planning (GRASP)
Don
Debalzo, NRL talked about ASW search planning Tactical Decision Aid (TDA)
which uses current environmental data to calculate sensor performance
and optimum search tracks for up to several heterogeneous sensors. The
GRASP algorithm adjusts waypoints in candiated paths to produce the optimum
search track over time.
Colloquium
During
the second day colloquium we probed some questions. The first question
was, "Is Search still relevant?" One participant suggested that
if we succeed in blanketing the battlespace with a very large number of
sensors, we might be able to apply the asset allocation model for search
planning. The second question was, "How is Search initiated?"
The thrust of this question was, who, in future combat organizations,
will determine that unfulfilled information requirements exist and direct
a search effort?
What
does it take to bring scientific rigor to the heuristic algorithms? The
group noted three broad issues surfaced repeatedly, and that these may
be good themes around which to organize. The issues were: network design,
use of heuristics and specific algorithms to solve real world problems.
We ended with a discussion around applications beyond the Navy.
Click
image for enlargement
New
Horizons in Search Theory: "Search Theory, Invented Now"
Second
Annual Workshop
During
the second year in 2002 ,
we talked about a third claimant to search solutions. Almost every advanced
warfare concept depends on high-performance collective robotics, most
notably for search and surveillance operations. This raises an intriguing
proposition. Might arranging the instruments of a search (collective autonomous
agents) require the same complex optimization solutions as the process
of the search (finding the target)?
If
so, we are on the verge of a new, ironic definition of Search Theory.
More importantly, it appears that the fundamental precepts of Koopman-style
Search Theory (KST) might warrant reconsideration.
If
this might be similar to KST, we could use Monte Carlo techniques, and
perhaps involve more statistics, or use functional forms that require
numerical solutions by modern computers. One might think of the search
as updating a Bayesian "prior" to where the target isn't. In
other words, it might look a lot like what people are doing today to modify
KST. It might look dramatically different in other ways as well.
Might searchers
and agents, applying a selection of local rules, sometimes change modes
or states, so as to switch to a new menu of rules? Might the robotic elements
of a future force act as such agents? Koopman’s later editions of
Search and Screening included an exploration of Information Theory, a
topic unknown before World War II. How might Information Theory contribute
to a modern Search Theory?
Below
is an overview of the presentations from the second year:
Jeff
Cares, Alidade Incorporated
- Recap
of last year
- Statements
of interest
Dr.
Brian McCue, CNA
- Midway
Game
- Very
“agent-looking”
- Dynamic
co-evolution
- Intent
very difficult to discern from knowledge of physical elements
Sessions
Dr.
Brian McCue, CNA
- “Search
Theory, Invented Now”
- Recognition
of KST as a product of its time
- Suggestion
that problem may be more complex
CDR
Mike Rimmer, RN, Naval Warfare Development Command
- “Future
Concepts of Military Search”Expeditionary Sensor Grid, FORCEnet,
FCS, etc.
- Formulation
of the operators’ estimates of the problem
Dr.
Doug Gage, DARPA-SDR
- “Distributed
Robotics and Problems of Search”
- Review
of existing DARPA efforts with robotic collective
- Discussion
of engineering problems
- Hard
for engineers to build ‘em cheap
Dr.
Fred Glover, OptTek, Inc., U of Colo.
- “TABU
Search”
- Discussion
of TABU search methods and effectiveness
Dr.
Ralph Klingbeil, Naval Undersea Warfare Center
- “Search
with Distributed Forces”
- Summary
of research into dimensions of the problem
- Rudimentary
exploration of the contributions of distributed forces
Cpt
Alistair Dickie, Royal Austrailian Army
- “Multi-Agent
Robot Swarm Simulation”
- Discussion
of his research at NPS
- Demonstration
of his simulation
LtCol
Ray Hill, AFIT
- “Agent-Based
Analysis of U-Boats in Bay of Biscay”
- ABM
treatment of (new) classic McCue work
- Raised
interesting questions about validation of ABM results
Dr
Josh Epstein, Brookings Institute
- “The
Spread of Disease in Populations”
- Recent
work for NSF
- Explored
the dynamics of contagion, death and recovery
Dr.
Rob Axtell, Brookings Institute
- “Operations
Research as a Subset of Multi-Agent Systems (MAS)”
- Intentionally
provocative suggestion
- Explored
the usefulness of MAS simulations when closed form equations fail
Dr.
Alfred Brandstein, MCCDC/Mary McDonald, SAIC
- “Search
Theory in Light of the El Farol Problem”
- “Co-evolving
Strategies between Red and Blue”
- Discussion
of the competitive dynamics of Search
Colloquium
During
the second day we discussed how can we Validation, Verification and Accredidation
(VV&A) be applied to agent-based models.
If
we can’t VV&A with Blue and Red dots, how will we gain confidence
in new C2 systems for distributed search? There was also discussion around
the engineering of Distributed Systems. As the Search Theory member of
an engineering team building robotic systems, what recommendations should
be made to the team? Consensus was that our knowledge of the problem is
too immature to make such recommendations on how can we VV&A Agent-Based
Models?
New
Horizons in Search Theory: “NETWORKED SEARCHES AND SEARCHES IN NETWORKS
Our
Third Annual Workshop
This
brings us to this year. We have two new problems. Networked Search (High-performance
collective robotics, swarms, sensor grids, etc) and Search in Networks
(data mining and distributed problem solving). We are going to hear presentations
on:
-
Distributed Networked Forces
-
Another
View of the Small World
-
Agent
Searches in the Bay of Biscay
-
Monte
Carlo Simulation
-
Social
and Organizational Search
|
