DYNAMIC PATH-PLANNING FOR SEARCH AND DESTROY
更新时间:2023-04-11 10:57:01 阅读量: 实用文档 文档下载
- dynamic推荐度:
- 相关推荐
Proceedings of the 2003 Winter Simulation Conference
S. Chick, P. J. Sánchez, D. Ferrin, and D. J. Morrice, eds.
DYNAMIC PATH-PLANNING FOR SEARCH AND DESTROY
MISSIONS – THE BAY OF BISCAY SCENARIO
Subhashini Ganapathy
Raymond R. Hill
Department of Biomedical, Industrial and Human Factors Engineering
Wright State University
207, Russ Engineering Center
Dayton, OH 45324, U.S.A.
ABSTRACT
Among the many modeling methods used for military ap-plications, simulation modeling is one of the most popular as it offers flexibility and an ability to perform “what-if” analysis.In this paper, we discuss search and destroy mis-sions in the context of the World War II Bay of Biscay U-boat scenario. We present a simulation architecture that supports integration of human reasoning with simulation-based optimization methods.
1 INTRODUCTION
Simulation models are used extensively for studying mili-tary applications. The primary goal of a military simulation is to provide a high fidelity representation of the combat conditions. Among the many modeling methods used for military applications, simulation modeling is one of the most popular as it offers flexibility and an ability to per-form “what-if” analysis (Battilega and Grange 1978).In the Search and Destroy (SAD) missions, a troop would search for the enemy and when found would capture or destroy the enemy force. Typically, in such cases, there is a threat to the search team by the enemy targets, directly or indirectly. In a direct threat there are attacks without an intervening agency or resource acting on behalf of the threat.
In a SAD scenario the information about the objects of interest (targets) is very important and is dynamic in nature. There could be two situations, (a) searching for an elusive target, and (b) if a target is located and is subse-quently lost. In the latter case, it behooves us to start the search in the area the target was last located. The knowl-edge about the target location (search area) temporally decays and this knowledge may no longer be relevant with change in time.
The dynamics and uncertainty associated with this problem scenario makes it very difficult to apply purely analytic approaches. Human reasoning integrated with
heuristic optimization methods offer a potentially attrac-
tive alternative.
In this article, we present the simulation architecture in the context of Bay of Biscay scenario. We present the deci-
sion algorithm that the simulation architecture uses in plan-
ning the path over the search area. Our model implements
the computational infrastructure to support reusable soft-
ware components. The architecture represents a dynamic
path planning in the context of the Bay of Biscay scenario
involving interactions associated with search for targets with minimum resources and maximum efficiency. Simula-
tion models give the flexibility of expanding and compress-
ing time (real world time) and, thus, allow extensive inves-
tigation of the system during any period of time. It accounts
for the dynamics and uncertainty of the system.
2 PROBLEM DOMAIN
This study focuses on the U-boat hunting problem during
World War II in the Bay of Biscay area. The Bay of Bis-
cay is an inlet of the Atlantic Ocean in southeastern Europe, bounded by France and Spain. The German U-
boats operated from captured ports in occupied France,
crossing the Bay of Biscay to gain access to the North At-
lantic.In the Atlantic, the U-boat wolf packs would look
for and attack allied convoys.The Allied convoys pro-
vided critical logistical support to the war effort. The con-
voys would ship basic necessities and war material to Great Britain.As counter measures, the Allied force sent
out airplanes to search and destroy the U-boats. Accord-
ing to McCue (1990), one of the biggest challenges faced
by the Allies was the Axis U-boat threat.
U-boats most imperiled North Atlantic shipping in 1942 and 1943.The Allied forces sent aircraft to search
the Bay of Biscay area for U-boats that were in transit be-
tween their ports in occupied France and the areas in North Atlantic. This search effort was more of an “offen-999
Ganapathy and Hill
sive” campaign than the “defensive” task of protecting convoys (Waddington 1973).
The problem domain can be described by the entities present in the system, their states and events as shown in Figure 1. The U-boats can be present in one of the three states: surfaced, submerged or sunk. The aircraft remain either on the base to be deployed or on the bay searching for the U-boats. The three major functional components of the system are:
1. The place of origin of the U-boats (French Ports
& German Shipyard) and North Atlantic
2. The Bay of Biscay
3. The place of origin of the aircraft (airfields in
England)
Figure 1: List of Entities, Their
States and Events
There are two events that occur in the ports of occu-pied France. The U-boats returning to France undergo re-pair and service. The aircraft return to the base for refuel-ing and reloading of munitions. Sinking of U-boats in the Bay depends on the number of U-boats surfaced and sub-merged, and the Allied search effort.
The U-boat war presents an interesting study, particu-larly when examining the dynamic decision processes in either side. The technologies used by both sides kept changing and updating with new strategies and counter-measures. The British introduced Anti-Surface Vessel
Mark II airborne radars to facilitate night time search. The
Germans as countermeasure changed their strategies for
transit by lessening detectability and vulnerability. The
Allies tried to match their search effort balance with that
of the Germans strategy of day and night travel.
McCue (1990) developed a mathematical model to study the behavior of the system that is known as the U-
boat Circulation Model. The U-boat circulation model en-
ables evaluation of performance of different Bay meas-
ures and countermeasures, using merchant ships saved as
a measure of performance.
3 RESEARCH APPROACH
There has been a lot of research on developing algorithms
for finding shortest paths in a particular topology or map.
Many of the previous models have failed to include the
dynamics and uncertainty of the planning model. Stentz
(1994) presents planning trajectories for mobile robots but
the model assumption that the environment is predeter-
mined is inaccurate. Canny and Lin (1990) discuss a robot
path planning algorithm that constructs a global skeleton
of free-space.
A discrete search space consists of a network of arcs
interconnected with or without repetition of the nodes.
Some of the well-known search algorithms for state space
search include A*, Dijkstra and Ant-Search (Cormen, Le-
iserson, and Rivest 2000; Gallo and Pallotino 1988; Nils-
son 1982;).
Dijkstra’s algorithm has been the widely used algo-rithm because it is simple and has less computation time.
Some of the applications include vehicle routing, emer-
gency routing and response system.
These algorithms aid in finding a solution that takes the form of a sequence of actions leading in a path from
the start state to a goal state. One of the major disadvan-
tages of these methods is that they are deterministic in na-
ture. These algorithms fail to account for the temporal
change in the environment. One of the limiting factors
for destroying the U-boats was the amount of munitions
carried by the airplane. The aircraft could carry only one
bomb at a time and once they dropped their bomb they
needed to fly to the base and rearm. The problem be-
comes very interesting for the following scenario: If an
airplane sights a U-boat on its way back to the base, what
is the flight path of the airplane after rearming? This can
result in two alternatives:
1. The airplane can return back to the sighted loca-
tion and search for the U-boat
2. The airplane can go and follow its predefined
search pattern.
Given a particular region the aircraft can travel along any path. The choice between the alternatives depends on
the cost effectiveness of the alternatives. The cost func-
tion depends on the probability of finding the U-boat at 1000
Ganapathy and Hill
the sighted location. Good search heuristics can result in improving the quality of the solution in terms of the re-sources spent. Richardson (1980) discusses the United States Coast Guard Computer Assisted Search Planning System (CASP) development work that investigates the search plan over a rectangular region.
The process of planning involves six steps. The first step is to define the objective and second is the correct problem formulation. The third step involves generation of alternatives and then comes evaluation of the alterna-tives. The next step is the choice of alternatives. The final step could be a feedback loop to give input to the simula-tion (Hozaki and Iida 2001).
The decision process for selecting the path is as shown in Figure 2. The base for the decision process is a Dijkstra’s algorithm, that also checks for optimal resource allocation based on the aircraft location, the resources present for the aircraft and whether it is armed or not. Dijkstra’s algorithm can be used to find the shortest path on a weighted, directed graph with a single-source node. The Bay area is pided in to equal segments of 100NM and each intersection of the square is considered a node. Each node is associated with a weight based on the dis-tance between the nodes, the amount of fuel required to cover the distance, and how recently an aircraft has vis-ited the node. The route of the aircraft is determined by first checking to see if the aircraft has ammunition. If the aircraft needs to be rearmed then it is routed back to the base, otherwise the algorithm calculates the next node based on the weights. Once the next location is calculated this information is presented to the user, and they can change the allocation based on the heuristics.
The search area covered can be expressed as the opera-tional sweep width of the airplane. Operational sweep rate measures submarine sightings in square miles per hour. 4 COMPUTATIONAL ARCHITECTURE High-fidelity computer models and simulations are very useful in design as well as ongoing systems management of many complex, real-world, dynamic systems (Naraya-nan et. al. 1998). The system developed for this study is a discrete event simulation. Figure 2: Decision Process for Selection of Waypoints 4.1 Simulation Architecture
The simulation architecture is based on an object-oriented architecture and supports interactive simulations (Naraya-nan et. al. 1997). The different modules of the system are (a) Basic Simulation Module, (b) Allied Resources Module, (c) Interface Module, and (d) German U-boats Module.
Interactions between different components are repre-sented using UML as shown in Figure 3. UML is a language for specifying, constructing, visualizing, and documenting the artifacts of a software-intensive system (Muller 1997).
Figure 3: Dependency Diagram of Simulation Architecture
1001
Ganapathy and Hill
Within the simulation, the entities are connected in a multi-threaded architecture. Hence, each inpidual air-craft or U-boat can be controlled and can describe differ-ent behavior. The architecture is built using the Java 2 en-vironment and can operate across different platforms. The basic simulation module is responsible for the scheduling of the events and coordinating the multi-threaded archi-tecture. It runs a standard simulation clock that tracks the time of the simulated system. The interface is developed
using the Java swing package.
Choosing the distributions for the occurrence of events is very critical in a simulation. There are two types of distributions used for this architecture: uniform and ex-ponential. In uniform distribution, the minimum and maximum are provided and all values within the range are equally likely to occur. The set of random numbers can be replicated; hence, these distributions generate pseudoran-dom numbers. The simulation design data is based on his-torical data and military expert opinion. 4.2 Features of the Model
The simulation interface is shown in Figure 4 . The time period for modeling the simulation was chosen as April 1943 – September 1943. During this timeframe the tech-nologies used by both the sides were fairly steady. Figure 4: Simulation Interface
aircraft could carry only one bomb at a time and once they dropped their bomb, they needed to fly to the base and rearm.
4.2.1 Aircraft Module
4.2.2 U-boats Module
The aircraft leave from a single base at Great Britain and search the base area based on the modified Djikstra’s al-gorithm. They standoff 100 NM from the coast of France to avoid enemy air patrols and escorts (Champagne and Hill 2003). They can sight a U-boat only when the U-boat travels on surface. The nodes are assigned based on the dynamic path-planning algorithm. The U-boats travel from five different ports and then cross the Bay of Biscay at different points in the sea. At the beginning of the simulation the U-boats are assigned randomly to any port based on a uniform distribution.
The simulation introduces anomalies in the system in terms of false targets, whose detection characteristics are identical to that of the target. A false target could represent a tide or water turbulence. Such false targets are called false positive. These false targets have the same detection function as the real target. The changes in the simulation module can be viewed on the interface as animations. The aircraft search around the middle of the bay area as shown in Figure 4. They do not go too close to the French ports as the U-boats had support convoys. The air-craft are limited by the munitions they can carry. They are also constrained by the search space and the capacity of the aircraft. Some of the assumptions made in this model are (a) the aircraft return to the base once the resources get depleted to 30% of their total capacity, (b) U-boats and the airplane move at a constant speed and do not ac-celerate, and (c) U-boats are always sighted when they are directly below a search beam of the airplane. 5 DISCUSSION
We have presented here an initial attempt to integrate human reasoning and decision making into a complex model. The computational architecture is generic and can support various studies related to heuristics optimization. In evaluating the effectiveness of the search it is impor-tant to properly formulate the effort. One of the most common measures in a search and destroy scenarios is to note whether a target has been found or not. If the target is not found then this measure does not give any clue re-garding the thoroughness and efficiency of the search nor
Some of the major decisions based on heuristics are: if a aircraft finds a U-boat on its return to the base for refuel then it would mark that place and let the other air-craft know about the specific location; if there are air-craft closer to that region then they would go and bomb that U-boat. One of the limiting factors for destroying the U-boats was the amount of munitions carried by the aircraft. The
1002
Ganapathy and Hill
does it provide guidance on when to stop the search. Hence it is important to choose the right measure in as-sessing the system.
The different studies that are in progress are (a) devel-oping software patterns that model prototypical scenarios and implement them as a library of classes using an object-oriented programming language, (b) formulation and im-plementation of heuristic optimization methods, and (c) ex-ploring the effectiveness of human integrated decision-making system with respect to an automated system. ACKNOWLEDGMENTS
The research was sponsored by Defense Modeling and Simulation Office through the Air Force Institute of Technology.
REFERENCES
Battilega, J. A., and Grange, J. K. 1978. The Military Ap-plications of Modeling. Air Force Institute of Tech-
nology Press: Wright-Patterson Air Force Base, Ohio.
Canny, J., and Lin., M. C. 1990. An Opportunistic Global Path Planner. In: Proc. IEEE International Confer-
ence of Robotics Automation. 39-48. Champagne, L. E., and Hill. R. R. 2003. Multi-Agent Simulation Analysis: Bay of Biscay Case Study. In Proceedings of SimTecT2003 Conference. Adelaide, Australia.
Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 2000.
Introduction to Algorithms. MIT Press: Cambridge, MA.
Gallo, G. and Pallotino, S. 1988. Shortest Path Algo-rithms. Annals of Operations Research. (13): 3-79. Hohzaki, R., and Iida, K. 2001. The Process of Search Planning: Current Approaches and Continuing Prob-
lems. European journal of operational research, 133: 120 – 129.
McCue, B. 1990. U-boats in the Bay of Biscay: an Essay in Operations Research. National Defense University Press: Washington D.C.
Muller, P. 1997. Instant UML. England: Wrox Press. Narayanan, S., Scheider, N. L., Patel, C., Reddy, N., Carrcio, T. M., and DiPasquale, J. 1997. An Object-
Based Architecture for Developing Interactive Simu-
lations using Java. Simulation, 69 (3):153–171. Narayanan, S., Bodner, D. A., Sreekanth, U., Govindaraj, T., McGinnis, L. F., and Mitchell, C. M. 1998. Re-
search in Object-Oriented Manufacturing Simula-
tions: An Assessment of the State of the Art. IIE Transactions, 30 (9): 795–810.
Nilsson, N. J. 1982. Artificial Intelligence. Springer-Verlag, Berlin Heidelberg: New York Richardson, H.R., and Discenza, J.H. 1980. The United States Coast Guard Computer-Assisted Search Plan-
ning System (CASP). Naval Research Logistics Quarterly, Vol. 27, 659-680.
Stentz., A. 1994. Optimal and Efficient Path Planning for Partially-Known Environments. In IEEE Int. Conf.
Robot. & Autom., 3310-3317.
Waddington, C. H. 1973. O.R. in World War 2: Opera-tions Research against the U-Boat. Paul Elek (Scien-
tific Bools) Ltd.: London, England.
AUTHOR BIOGRAPHIES
SUBHASHINI GANAPATHY is a Research Assistant at Human Computer Interaction Lab, Wright State University. She is currently pursuing her Ph.D. in Humans in Complex Systems. Her research interests include predictive analysis in model-based information technology systems, design op-timization, and simulation and modeling. Her email and web addresses are
RAYMOND R. HILL is an Associate Professor of In-dustrial and Human Factors Engineering with Wright State University. He has a Ph.D. from the Ohio State Uni-versity and has research interests in heuristic analysis, ap-plied optimization and simulation modeling. His email and web addresses are
1003
正在阅读:
DYNAMIC PATH-PLANNING FOR SEARCH AND DESTROY04-11
动火作业操作规程03-05
内经讲义06-01
Linux系统的网络配置与管理 - 图文03-17
浙江省口腔义齿生产企业质量体系考核检查表04-10
奥鹏15春中国石油大学《安全行为学》第二阶段在线作业答案09-06
彩泥社团工作计划01-31
谦受益满招损作文600字06-22
- 1Urban landscape planning experience in Nigeria
- 2A Decomposition-Based Implementation of Search Strategies
- 3In Search of the Amber Room说课稿
- 4UNIVERSITY OF SOUTHAMPTON Dynamic Discovery, Creation and In
- 5Integrating Dynamic Deformations into Interactive Volume
- 6HND 大综合2 planning
- 7Urban landscape planning experience in Nigeria
- 8ABS_Dynamic_Positioning_System
- 9Dynamic Business English- Work Experience
- 10Further investigation on the dynamic compressive strength enhancement
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- PLANNING
- DYNAMIC
- DESTROY
- SEARCH
- PATH
- 华为认证HCDP-Enterprise实验指导书HCDP-Enterprise-IERN v1.5
- 加强水利基础设施建设 提高农村抗灾减灾能力2
- 乌鲁木齐市创建全国文明城市应知应会内容
- 食品安全问题调查报告(最新版)
- 四年级下册计算题题.doc
- 2022-2022年初中科学牛津上海版《六年级下册》《第7章 空气与生
- 高级茶艺师、茶艺技师论文撰写要求
- 新教材 高考物理一轮总复习达标训练习题:高考必考题突破讲座11
- 成都知识产权律师:知识产权的纠纷类型有哪些?解决这些纠纷的方
- 校园导游系统数据结构图
- 语文-高二-湖北省宜昌市第一中学2022至2022学年高二上10月阶段性
- web前端试用期工作总结.doc
- 2022年西北大学计算机网络考研复试核心题库之综合题精编
- 苹果手机通讯录不小心删除了怎么恢复
- 湖北松滋刘家场地区普通地质实习报告
- 公务员考试申论热点:贯彻新发展理念 建设现代化经济体系
- 团章考试试卷及答案
- 15年春节后复工检查及一季度安全生产与文明施工大检查情况
- 线性代数第五版答案(全)
- 2022年福建师范大学数学与计算机科学学院618教育学基础综合之教