Transcript Route Algorithm

Virtual Computing Environment
for Future Combat Systems
Maps are as important to soldiers as guns
Shooters Network
Sensor Network
HPGIS
National Assets, e.g. Maps
Commanders Network e.g.
Situation Assessment
Example Usage of Geographic Info. Systems (GIS) in Battlefield :
•Rescue of pilots after their planes went down (recently in Kosovo)
•Precision targeting e.g. avoid civilian casualities (e.g. friendly embassies)
•Logistics of Troop movements, avoid friendly fires
Motivating Example – Urban Warfare
“Black Hawk Down”
Mogadishu, Somalia, 10/3/1993

Soldiers trapped by roadblocks

No alternate evacuation routes
Rescue team got lost in alleys having
no planned route to crash site

18 Army Rangers and elite Delta
Force soldiers killed, 73 wounded.

( Mark Bowden, Black Hawk Down: A Story of Modern
War )
Motivating Example – Chem-Bio Portfolio
• Examples
•
•
Weather, Terrain, Base map
Chem-Bio portfolio project (Dr. Alibadi)
Scenario – managing a (say chem-bio) attack
• Components of the system
•
•
•
•
•
Gathering initial conditions
• Weather data from NWS or JSU
• Terrain maps (State of federal Govt.)
• Building geometry (City Govt.)
Plume simulation using supercomputers
Visualizing results – map, 3D graphics
Response planning
Plume
Modeling
Q? What happens after plume simulation,
visualization?
Demographics, Transportation
( Images from www.fortune.com )
Homeland Defense: Chem-Bio Portfolio
"We packed up Morgan City residents to evacuate in the a.m. on
the day that Andrew hit coastal Louisiana, but in early afternoon
the majority came back home. The traffic was so bad that
they couldn't get through Lafayette."
- Morgan City, Louisiana Mayor Tim Mott
( http://i49south.com/hurricane.htm )
( National Weather Services)
Hurrican Andrew, 1992
 Traffic congestions on all highways
 Great confusions and chaos
( www.washingtonpost.com)
Problem Statement
Given
• Transportation network (e.g. building floor map, city roadmap) with
capacity constraints
• Initial number of people to be evacuated and their initial location
• Evacuation destinations
Output
• Scheduling of people to be evacuated and the routes to be taken
Objective
• Minimize total time needed for evacuation
• Minimize computational overhead
Constraints
• Capacity constraints: evacuation plan meets capacity of the network
Route Algorithm - Related Works
•
Dynamic network flow (Ford and Fulkerson, 1960’s)
–
•
Simple algorithms for multiple source and destination (1970’s-1980’s)
–
•
Quickest Flow Problem: Only apply to single source and single destination node
Algorithms have exponential running time, e.g. EVACNET(University of Florida)
Improved algorithms (1990’s)
– Klinz:
• Polynomial time algorithm
• Can only find required time, not the evacuation plan
– Tardos(1994):
•
•
•
•
Polynomial time algorithm to find optimal plan for fixed number of sources
Cannot apply to variable number of sources
Cannot apply to variable arc capacity, e.g. arc capacity changed over time
May produce fractional solution, e.g. “5.2 people go to …”,
feasible evacuation plan requires integer solution
Route Algorithm - Our Approach
•
Algorithm Design
– Extend shortest path algorithms (e.g. A*) To honor capacity contraints
– Attach a time-series with each node and edge
• Edge capacity
• Node occupancy
– Start single-source routing between all (source, dst) pairs
• First route found is used to reduce edge and node attributes
• Process repeats till node capacities are reduced to zero
•
Evaluation
– Much faster than the current approaches
– Solution quality is comparable on hand tested examples
• Problems with little interference across routes, ;arge edge capacities
– Detailed evaluation in progress
Example Map
Node
N1, 50
(10)
Node ID, Max Capacity
(Initial Occupancy)
(7,1)
N4, 8
(3,3)
First Floor
EXIT #1
N13
(14,4)
N9, 25
N5, 6
(3,4)
N7, 8
(6,4)
(2,5)
(6,4)
(8,1)
N10, 30
(6,3)
N8, 65
(15)
(3,3)
N11, 8
(3,1)
(6,4)
N12, 18
Edge
(Max Capacity, Travel time)
Exit
N2, 50
(5)
N6, 10
(5,5)
(3,3)
(7,1)
(5,4)
Second Floor
N3, 30
(3,3)
N14
EXIT #2
Node ID
Result: Routes, Schedules
Group of People
Start time
Route
Exit time
ID
Origin
No. of people
A
N8
6
0
N8-N10-N13
4
B
N8
6
1
N8-N10-N13
5
C
N8
3
0
N8-N11-N14
4
D
N1
3
0
N1-N3-N4-N6-N10-N13
14
E
N1
3
1
N1-N3-N4-N6-N10-N13
15
F
N1
3
2
N1-N3-N4-N6-N10-N13
16
G
N1
1
0
N1-N3-N5-N7-N11-N14
14
H
N2
1
0
N2-N3-N5-N7-N11-N14
14
I
N2
2
1
N2-N3-N5-N7-N11-N14
15
J
N2
2
2
N2-N3-N5-N7-N11-N14
16
Result – Checking edge capacity constraints
Number of people move though each edge starting from each time interval
N8N10
N1-N3
N2-N3
6
7
5
6
3
N4-N6
N5-N7
N6N10
N7N11
3
2
5
3
2
6
3
2
8
3
2
9
3
2
10
3
2
0
1
N8N11
3
N11N14
N10N13
2
3
3
4
6
6
N3-N4
N3-N5
3
2
3
2
3
2
7
11
12
13
2
3
14
2
3
15
2
3
Routing – Next Phase (S. Shekhar)
•
AHPCRC Relevance – Projectile Target Interaction Portfolio
– Increase lethality of weapons such as guided missiles
– Pre-lauch routing – stealth route avoiding enemy sensor network
– In-route routing
• to correct drifts from planned trajectory
• To route route unanticipated obstacles
•
Possible Extensions in 2002-2003
– Focus on relevance to AHPCRC Portfolios
– Complete design and implementation of routing algorithm with capacity constraints
– Performance evaluation with real datasets
SPIRAL NATURE OF THE PRECISION ENGAGEMENT PROCESS
Locate
Assess ISR
Locate
Assess
TST
Locate
Defer
Assess
Attack
ID
ID
ID
Assess
Re-attack
Detect
Decide
Attack
Decide
Employ
wpns
Decide
TST
Status
Detect
Detect
Detect
• Process timeline
compresses for TSTs
ID
Locate
Target
• Iterative process driven
by effort to refine data
about target ID,
location, and status
• Process necessarily
balances timeliness,
lethality, and accuracy
Decide
Guidance and
Objectives
Location Prediction and Spatial Data Mining (S. Shekhar)
•
Specific Project in 2001-2002
– Evaluation of location prediction techniques
– Towards high performance parallel implementation
•
AHPCRC Relevance – Projectile Target Interaction Portfolio
– Increase lethality of weapons such as guided missiles
– Location prediction for map matching
• to check correctness of missile trajectory
• To identify unanticipated obstacle
– Towards possible rerouting
•
Army Relevance in general
–
–
–
–
–
–
–
Predicting global hot spots (FORMID)
Army land management endangered species vs. training and war games
Search for local trends in massive simulation data
Critical infra-structure defense (threat assessment)
Inferring enemy tactics (e.g. flank attack) from blobology
Locating enemy (e.g. sniper in a haystack, sensor networks)
Locating friends to avoid friendly fire
Accomplishments
•
Formal Results
•
•
•
SAR - parametric statistics, provides confidence measures in model
MRF from non-parametric statistics
SAR : MRF-BC :: linear regression : Bayesian Classifier
•
Rewrite SAR as y = (QX)  + Q, where Q = (I- W)-1
•
SAR has linear class boundaries in transformed space (QX, y)
•
MRF-BC can represent non-linear class boundaries
•
Experimental results
•
•
MRF-BC can provide better classification accuracies than SAR
•
But solution procedure is very slow
Details in Recent paper in IEEE Transactions on Multimedia
Location Prediction
• Problem Definition:
Nest locations
Given: 1. Spatial Framework S  {s1 ,...sn }
2. Explanatory functions: f X : S  R
3. A dependent function: fY : S  {0,1}
4. A family  of function mappings:
Find: A function fˆy   R  ...  R  {0,1}
Objective: maximize classification accuracy ( fˆy , f y )
Constraints: Spatial Autocorrelation in dependent function
Distance to open water
k
• Past Approaches:
Non-spatial: logistic regression, decision trees, Bayesian
– Assume independent distribution for learning samples
– Auto-correlation => poor prediction performance
Spatial: Spatial auto-regression (SAR), Markov random
field Bayesian classifier (MRF)
– No literature comparing the two!
– Learning algorithms for SAR are slow (took 3 hours
for 5000 data points)!
Vegetation
durability
Water depth
Accomplishments
•
Formal Results
•
•
•
SAR - parametric statistics, provides confidence measures in model
MRF from non-parametric statistics
SAR : MRF-BC :: linear regression : Bayesian Classifier
•
Rewrite SAR as y = (QX)  + Q, where Q = (I- W)-1
•
SAR has linear class boundaries in transformed space (QX, y)
•
MRF-BC can represent non-linear class boundaries
•
Experimental results
•
•
MRF-BC can provide better classification accuracies than SAR
•
But solution procedure is very slow
Details in Recent paper in IEEE Transactions on Multimedia
Past Accomplishments
• Scaleable parallel methods for GIS Querying for Battlefield Visualization
• A spatial data model for directions for querying battlefield information
• Spatial data mining: Predicting Locations Using Maps Similarity (PLUMS)
•An efficient indexing method, CCAM, for spatial graphs, e.g. Road Maps
GIS Research at AHPCRC
•
•
•
High Performance Geographic Information Systems (HPGIS)
–
Parallel formulations for terrain visualization
–
Efficient storage (e.g. CCAM), join-index
More expressive GIS - Query languages, Data models
–
Mobile objects, Direction and Orientation
–
Processing direction based queries
Smarter GIS - Spatial Data Mining
–
Spatial prediction, classification
–
Association among spatial features
–
Spatial outlier detection