Optimising the passage through charted minefields by path planning and mine removal
Date
2006-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Shipping is the lifeline to maritime nations. Therefore it is essential that approaches to
harbours and other strategic areas are kept free of threats by sea mines. With the
technological possibility of remotely surveying threatening sea minefields, it has become
necessary to develop a method by which such a charted minefield can be transited with
least risk to shipping. To achieve this, two areas of interest have to be addressed and the
resulting questions solved. This thesis addresses that requirement by meeting the
following objectives:
- to propose a methodology by which the risk involved in transiting a minefield can
be managed so that paths of acceptable risks can be taken through a minefield;
- if acceptable paths do not exist, to develop a methodology by which the minimum
number of mines can be identified for removal so that a sufficiently safe path is
established.
These objectives were met by following the approach outlined below:
- defining the problem in the context of traditional and developing mine warfare
and mine countermeasures;
- clearly stating the problems that have to be solved;
- investigating the enablers available to solve the problems;
- selecting and motivating a suitable approach;
- describing the background knowledge to the proposed solutions;
- implementing the solutions in a useable computer application;
- investigating the parameters that pertain to the solution and presenting the
findings;
- drawing conclusions from the results and insights obtained from exposure to the
problem and the solution strategies.
The presented methodology uniquely combines two methods of combinatorial
optimisation to give an integrated solution to the two stated problems of quantifying a
risk methodology and removing required mines. The methods use the well known
shortest path algorithm, Dijkstra's Algorithm, and a Genetic Algorithm for the basis of
the proposed solution. Also, elements of the principle of the Efficient Frontier Graph are
integrated to illustrate the aspects of return versus risk.
The solution to finding a safe path through a charted minefield is approached from two
risk principles:
- Finding a path that is optimised for minimum risk over the entire length of the
path. Here risk is a function of the distance between the mine and the ship.
- Defining a maximum allowable risk and minimising the path length. Here risk
is translated into the closest distance that a ship is allowed to approach a mine
with the areas closer than that, being declared out of bounds.
The sea mine removal problem is solved primarily by using a Genetic Algorithm that
bases the quality of a solution on a parameter obtained by applying the methodology
developed for solving the problem of optimising a path. This is achieved by minimising
the number of sea mines to be removed to create a safe path.
AFRIKAANSE OPSOMMING: Skeepsvaart is noodsaaklik vir die ekonomiese voortbestaan van maritime nasies. Daarom is dit belangrik dat die bedreiging van seemyne by die toegang tot hawens en antler strategiese seegebiede teegestaan word. Met die tegnologiese moontlikheid van afstandbeheerde verkenning van bedreigende mynvelde is dit nodig om 'n metode te ontwikkel om so 'n mynveld oor te steek met die minste risiko vir skepe. Om dit moontlik te maak moet twee areas van belang gedek en die gepaardgaande probleme opgelos word. Hierdie tesis dek die vereistes deur die volgende doelstellings te bevredig: - om 'n metodologie voor te stel waardeur risiko's betrokke by die oorsteek van 'n mynveld bestuur kan word sodat roetes met 'n aanvaarbare risiko deur 'n mynveld gevind kan word; - indien sulke roetes nie bestaan nie, om 'n metodologie te ontwikkel waarmee die minimum myne vir verwydering ge1dentifiseer kan word sodat 'n voldoende veilige roete ontstaan. Hierdie doelstellings is met die volgende benadering aangespreek: o deur die probleem in die konteks van tradisionele en ontwikkelende mynoorlogvoering en mynteenmaatreels te definieer; o deur die probleme wat opgelos moet word duidelik te stel; o deur moontlike oplossings tot die probleme te ondersoek; o deur die keuse en motivering van 'n geskikte benadering; o deur die agtergrond tot die voorgestelde oplossings te beskryf; o deur die implementering van die oplossings met 'n rekenaargebaseerde toepassing; o deur parameters wat verband hou met die oplossing te ondersoek en resultate te toon; o deur gevolgtrekkings te maak uit die resultate en insigte wat deur blootstelling aan die probleme en oplossingsmetodes verkry is. Die metodologie wat aangebied word verbind twee metodes vir kombinatoriese optimering op 'n vindingryke manier sodat die twee gedefinieerde probleme van kwantifisering van risiko en verwydering van seemyne aangespreek word. Die metodes maak gebruik van die bekende kortste pad algoritme Dijkstra se Algoritme, en 'n Genetiese Algoritrne as basis vir die voorgestelde oplossing. Dan word daar ook van die beginsels van die "Efficient Frontier Graph" gebruik gernaak om elernente van opbrengs teen risiko te illustreer. Die oplossing om 'n veilige roete deur 'n rnynveld te vind word vanuit twee risikobeginsels benader: o Orn 'n roete te vind wat geoptirneer is rn.b.t. risiko oor die hele lengte van die roete, met risiko 'n funksie van afstand tussen die skip en 'n myn. o Deur 'n rnaksirnurn toelaatbare lokale risiko te defineer en die roete te optirneer rn.b.t. afstand. Hier word risiko vertaal na 'n minimum toelaatbare afstand tussen rnyn en skip, sodat enige afstand nader aan 'n rnyn as ontoelaatbaar te verklaar. Mynverwydering is hoofsaaklik opgelos deur 'n Genetiese Algoritrne wat die kwaliteit van 'n oplossing baseer op 'n parameter wat deur aanwending van die roeteoptirneringsrnetode bepaal word. Die algoritrne optimeer die verwydering van die minimum aantal rnyne sodat 'n veilige pad onstaan.
AFRIKAANSE OPSOMMING: Skeepsvaart is noodsaaklik vir die ekonomiese voortbestaan van maritime nasies. Daarom is dit belangrik dat die bedreiging van seemyne by die toegang tot hawens en antler strategiese seegebiede teegestaan word. Met die tegnologiese moontlikheid van afstandbeheerde verkenning van bedreigende mynvelde is dit nodig om 'n metode te ontwikkel om so 'n mynveld oor te steek met die minste risiko vir skepe. Om dit moontlik te maak moet twee areas van belang gedek en die gepaardgaande probleme opgelos word. Hierdie tesis dek die vereistes deur die volgende doelstellings te bevredig: - om 'n metodologie voor te stel waardeur risiko's betrokke by die oorsteek van 'n mynveld bestuur kan word sodat roetes met 'n aanvaarbare risiko deur 'n mynveld gevind kan word; - indien sulke roetes nie bestaan nie, om 'n metodologie te ontwikkel waarmee die minimum myne vir verwydering ge1dentifiseer kan word sodat 'n voldoende veilige roete ontstaan. Hierdie doelstellings is met die volgende benadering aangespreek: o deur die probleem in die konteks van tradisionele en ontwikkelende mynoorlogvoering en mynteenmaatreels te definieer; o deur die probleme wat opgelos moet word duidelik te stel; o deur moontlike oplossings tot die probleme te ondersoek; o deur die keuse en motivering van 'n geskikte benadering; o deur die agtergrond tot die voorgestelde oplossings te beskryf; o deur die implementering van die oplossings met 'n rekenaargebaseerde toepassing; o deur parameters wat verband hou met die oplossing te ondersoek en resultate te toon; o deur gevolgtrekkings te maak uit die resultate en insigte wat deur blootstelling aan die probleme en oplossingsmetodes verkry is. Die metodologie wat aangebied word verbind twee metodes vir kombinatoriese optimering op 'n vindingryke manier sodat die twee gedefinieerde probleme van kwantifisering van risiko en verwydering van seemyne aangespreek word. Die metodes maak gebruik van die bekende kortste pad algoritme Dijkstra se Algoritme, en 'n Genetiese Algoritrne as basis vir die voorgestelde oplossing. Dan word daar ook van die beginsels van die "Efficient Frontier Graph" gebruik gernaak om elernente van opbrengs teen risiko te illustreer. Die oplossing om 'n veilige roete deur 'n rnynveld te vind word vanuit twee risikobeginsels benader: o Orn 'n roete te vind wat geoptirneer is rn.b.t. risiko oor die hele lengte van die roete, met risiko 'n funksie van afstand tussen die skip en 'n myn. o Deur 'n rnaksirnurn toelaatbare lokale risiko te defineer en die roete te optirneer rn.b.t. afstand. Hier word risiko vertaal na 'n minimum toelaatbare afstand tussen rnyn en skip, sodat enige afstand nader aan 'n rnyn as ontoelaatbaar te verklaar. Mynverwydering is hoofsaaklik opgelos deur 'n Genetiese Algoritrne wat die kwaliteit van 'n oplossing baseer op 'n parameter wat deur aanwending van die roeteoptirneringsrnetode bepaal word. Die algoritrne optimeer die verwydering van die minimum aantal rnyne sodat 'n veilige pad onstaan.
Description
Thesis (MScIng) -- University of Stellenbosch, 2006.
Keywords
Submarine mines, Harbors -- Safety measures, Shipping -- Safety measures, Dissertations -- Industrial engineering, Mine clearing