Towards a knowledge-based system prototype forAeronautical Search and Rescue Operations
Irène Abi-Zeid
Opérations et systèmes de décisionFaculté des Sciences de l'AdministrationUniversité Laval, Québec (Québec), G1V 
Stéphane Schvartz
Département d’informatique et de génie logicielFaculté des sciences et de génieUniversité Laval, Québec (Québec), G1V 
Oscar Nilo
Opérations et systèmes de décisionFaculté des Sciences de l'AdministrationUniversité Laval, Québec (Québec), G1V 
Michael Morin
Département d’informatique et de génie logicielFaculté des sciences et de génieUniversité Laval, Québec (Québec), G1V 
 Abstract -
The long-term objective of our project is to develop a knowledge-based tool for Search and Rescue(SAR) operations to support a Canadian search mission coordinator in determining the likely location of a missing aircraft overland. In order to attain this objective, we used a knowledge engineering approach to acquire, structure and model SAR experts’ knowledge.This knowledge was modeled and implemented in a knowledge-based system prototype. The input to theinteractive prototype consists of the known information regarding a given SAR case. Its main output is a set of  scenarios describing the various hypotheses on what might have happened to the missing aircraft, why and where, the plausible routes followed, as well as the possibility area, defined as the region most likely to contain the missing aircraft. In this paper, we introduce the knowledge model, present an application example and briefly describe the prototype.
Search and Rescue, knowledge-based system.
Search and Rescue (SAR) is one of the greatesthumanitarian activities. Steve Fossett is one famous SARcase. John F. Kennedy Jr. is another famous SAR case.For every famous case, there are dozens of non-famousones. In Canada, there are thousands of SAR cases everyyear where tens and sometimes hundreds of lives are lost.
 Coordinating SAR operations is knowledge intensive.Case prosecution, the main function of a searchcoordinator, is conducted in response to the occurrence of an incident. Following the receipt of an alert, the
Statistical information can be obtained from the NationalSearch and Rescue Secretariat at:
coordinator must determine if an emergency situationexists and the degree of emergency. If the missing aircraftis not located within a given period of time, a major searchoperation is then initiated.An important step prior to initiating a major search isthe definition of the possibility area, the area most likely tocontain the search object. For marine searches in Canada,the computer tool CANSARP helps in defining thepossibility area by developing different scenarios andprobability maps related to the possible location of thesearch object(s) [2]. For aeronautical searches overland,the current approach in non-mountainous regions, CSAD
,is based on an empirical distribution of incidents, over sixyears, where the missing aircraft was located [9]. Formountainous regions, the MVFR
method is used. Thesemethods were developed for cases where there is littleinformation to use besides a last known point and adestination. In practice, a search coordinator modifies theinitial CSAD or MVFR possibility area as a function of the information available on the missing aircraft, the pilot,the weather at the time of the incident, the terraintopography, etc. [5]. In the absence of a standardisedreasoning method, coordinators employ heuristicapproaches based on their intuition and experiences.In recent years, the need for developing a decisionsupport system for overland aeronautical SAR missionplanning was identified in Canada. There were two mainrequirements: a planning module for optimal effortallocation, and a knowledge module for capturingknowledge and expertise. To address these requirements, adecision support system for the optimal resource allocation
Canadian Search Area Definition
Mountain Visual Flight Rules
of overland aeronautical SAR, SARPlan, was developed[1]. One of the main inputs to SARPlan is the possibilityarea, a region manually defined and drawn by the user(Figure 1). As a consequence, SARLoc, a project todevelop a tool that can assist the coordinator in definingthe possibility area, was initiated to capture the currentknow-how and knowledge of experienced coordinatorswhose number is dwindling in the Canadian Forces. Boththe SARPlan and SARLoc projects were funded by theNational Search and Rescue Secretariat
via the NationalSAR Initiative Fund.
Figure 1: A possibility area in SARPlan
The main objective of the SARLoc project was tocapture the expertise of search mission coordinators, tostructure this expertise and to develop a knowledge modelas a structured method that can guide a coordinator in thedefinition of the possibility area of a civilian aircraftmissing overland in peacetime.The research questions that we wished to answer werethe following: How do coordinators determine thepossibility area? How can we describe and model theirknowledge and their problem resolution process? How canwe acquire, formalize and represent this knowledge at aconceptual level that can eventually lead to a knowledge-based system (KBS) prototype?
Knowledge modeling
In order to find answers to these questions, we positionedour qualitative study in a knowledge engineering context.We used the CommonKADS methodology [10] to help usdevelop conceptual knowledge models. The role of knowledge models is to describe human tasks that arecomplex and require a lot of expertise. They allow one toacquire domain knowledge and clarify the structure of aknowledge-intensive task at a level independent of thecomputer implementation. Although some papers havebeen published on knowledge engineering in SAR, ([3];[8]), none have addressed the possibility area problem.Our knowledge acquisition phase was based onknowledge available in documents, on interviews withdomain experts and on participation in training and
simulations. These activities helped us identify the mainconcepts involved in the definition of a possibility area(Figure 2).
Figure 2: The main concepts for defining a possibility area
distress case
contains available
incident information
 such as a flight plan, last known position, departure point,destination point, aircraft type and configuration, aircraftautonomy, equipment on board, etc. The availableinformation can help classify the case in a
In our prototype, the availability of suchinformation is
captured by the interfaces on
Figures 3 and4. Figures 5 and 6 capture the information on thenavigation equipment available on board along with theaircraft type.
Figure 3: Incident information
Figure 4: Incident locationFigure 5: Navigation equipment informationFigure 6: Aircraft information
distress scenario
is built for a distress case. Itdescribes the chain of events and is composed of fourhypotheses levels:
 Event hypotheses
These hypotheses relate to apossible event(s) that occurred to the missing aircraft(in peacetime) preventing it from arriving to theplanned destination. Knowledge acquisition enabledus to formulate six possible hypotheses: an encounterwith a weather barrier, with a topographic barrier,insufficient fuel, a mechanical problem, navigationerror, or medical problem.
 Decision hypotheses
In the face of an unexpectedevent, the pilot normally reacts and makes a decisionon the next course of action. These hypotheses relateto the plausible reactions of the pilot. The occurrenceof a sufficiently serious event normally requiringmodifications to the flight plan, namely the routeinitially planned by the pilot. These hypotheses allowthe coordinator to presume the pilot's behaviour inreaction to the event in question. The choice of hypothesis relating to the most plausible pilot'sdecision is based on the information availableregarding the pilot's profile, the supposed event, theconditions in which the coordinator believes the flightwas carried out, and so forth.
Consequence hypotheses
Given an event and apilot's decision to act, the outcome might be a successor a failure, meaning that the pilot succeeded inexecuting his plan or not. These hypotheses reflect thepossible consequences of the pilot's decisionfollowing the occurrence of a problematic event andhis actions. The selection of the most plausibleconsequence, be it the success or failure of the actionundertaken by the pilot, is influenced by informationsuch as the pilot's experience and qualifications, thescale of the supposed event, the performance of theaircraft, and so forth.
 Datum hypotheses
These hypotheses are related tospecific geographical positions in the vicinity of theintended route (either initial or modified) towardswhich the pilot would have been able to head basedon the hypotheses previously assumed (
, an openarea to carry out an emergency landing).An event-decision-consequence hypothesis tripletdefines a path
. A
is composed of one ormany hypothesis triplets. A hypothesis triplet is what thecoordinator believes has happened (
event hypothesis
), howthe pilot reacted (
decision hypothesis
) and what the resultof the pilot’s reaction was (
consequence hypothesis
 Datum hypotheses
may be associated to a hypothesistriplet. A
is associated to a
and is composedof one or many
including possibly a datum (ormany). A resulting
possibility area
is centred on one or
that the coordinator believes the pilot mayhave followed.In the following phase of our project, we used theseconcepts to elaborate a reasoning model for determiningthe possibility area. This structured procedure is describedby Figure 7.First, a distress case must be
in a distresscategory based on the available information and on“distress category classification rules”. The
category 1- certainty
is a simple situation where thedistress position is known and no further investigation isnecessary. The
category 3- total uncertainty
 corresponds to a situation where crucial information ismissing such as the pilot’s destination. For these twoextreme categories, there exist, in SAR manuals such asthe NSM [5], precise procedures that can be followed todelimit a possibility area. The most interesting case is theone where partial information is available, such as distressposition is unknown, destination is known, intendedtrajectory either known or unknown, which leads to a
category 2- partial uncertainty
. This is the most frequentsituation where diagnosis, the most knowledge-intensivesub-task, is required. The application of the reasoningmodel associated with diagnosis leads to distress scenariosdefined by hypotheses and associated routes.Given a hypothesis triplet, the diagnosis process can beterminated or can continue if the coordinator believessome other event has occurred. In this case, anotherhypothesis triplet can be constructed by the coordinatorand a new segment added to the presumed route. Inaddition, it might be pertinent to determine specificpositions where the pilot might have crashed or landed inthe vicinity of the routes constructed. These positions arealso included in the possibility area. For example, if thecoordinator believes that during the flight the pilot hasfigured out that he will not be able to reach his destinationfor whatever reason (lack of fuel, mechanical problem,physiological problem, etc.), the coordinator may look forspots where the pilot might have landed. A possiblelanding spot is a
. Obviously, the type of aircraftwill determine the possible landing spots available forlanding in a given region. For an aircraft on wheels,secondary airfields, highways, long straight portions of roads are possible landing spots. For an aircraft on floats,lakes with sufficient length are possible landing spots.Taking into account possible landing spots is relevantwhen the coordinator tries to determine alternative coursesfor the aircraft. In such cases possible landing spots thatcould have been reached by the aircraft should beidentified because they correspond to alternativedestinations that the pilot might have tried to reach. Incases of mechanical, electrical failure of the aircraft or of pilot's physical problems, one can assume that the pilotwill try to land as soon as possible in order to avoid majordamages if possible. This datum hypothesis level allowsone to complete the diagnosis by finding possibleemergency landing or crash points along the segmentsassociated to each hypothesis triplet.
Figure 7: The reasoning model
Once the coordinator is satisfied with the scenario, thepossibility area can then be created. The possibility area(for
distress category 2
) is delimited using a rectangulararea of 10 Nautical Miles (NM) in width centered on theroutes presumably followed by the pilot including thesegments to the datum points. Note that the user mightwish to study another distress scenario consisting of different hypotheses and associated routes. In this case, thetwo possibility areas can be merged. For the othercategories, the possibility area is delimited asrecommended in the NSM [5].One of our objectives in the knowledge modeling phasewas to propose a structured method to assist thecoordinator in determining whether the pilot flew thedirect route from the last known point to the planneddestination or whether he followed an alternative route due
to various unexpected events. We wished to guide thecoordinator in generating various possible scenarios of what happened to the aircraft, where and why. Byfollowing this modeling approach, we were reproducing,albeit in a structured manner, the reasoning followed bythe coordinator who tries to get a mental picture of whatthe pilot saw during his flight, and to guess what mighthave been his reactions. A full description of theknowledge model can be found in [12] and in [11].
Application example
We present an application example for defining apossibility area based on the reasoning model that wedeveloped. The information available in this case indicates
good weather conditions at the departure airfield withnoticeable degradation 90 NM to the north along the planned flight route. Skies are cloudy with a ceilingvarying between 1500 ft (1000 ft at some places) and 9000 ft. Visibility is reduced to 1 NM in some places. The last radio contact occurred at 10:34, about 48 NM after takeoff, which establishes the last known point (LKP). Radar data, available until 10:29, estimate the aircraft’sspeed at 100 knots. It is known that the pilot had completed 350 hours of flight including about 40 hoursduring night and about 30 hours using instruments. According to his next of kin, he felt more and moreconfident in difficult weather conditions. He was known tohave a GPS (Global Positioning System) on-board that hehad programmed to get to his destination as well as to analternate airfield where he could refuel.
 Based on the model developed, the reasoning couldproceed as follows:1.
The coordinator confirms that he believes that theaircraft has met with a weather barrier 42 NM afterhis LKP (
event hypothesis
). A first segment is thendrawn from the departure point to the LKP.2.
The available information concerning the pilot’sprofile suggests that he has attempted to cross theweather barrier (
decision hypothesis
). Since thishypothesis is retained by the coordinator, onlysegments crossing the weather barrier are drawn. If the pilot has decided to cross the barrier, it is likelythat he has used his GPS and attempted to follow hisdirect route to destination.3.
Given that the pilot has little experience flying withinstruments, it is possible that he tried to fly belowthe clouds’ ceiling in order to be able to see theground and, that he has crashed in a mountain.Therefore, the coordinator retains the hypothesis thatthe pilot did not succeed in crossing the weatherbarrier, (
consequence hypothesis
). This hypothesistriplet indicates that the presumed route stops at theexit point of the weather barrier.4.
The closest mountain to the route, presumablyfollowed by the pilot, is considered a
Figure 8 shows the planned route, its whereabouts,the weather barrier (in grey), three mountains alongthe route (triangles) as well as the resultingpossibility area (rectangle).
Figure 8: An example of a possibility area (not to scale)
KBS prototype
The reasoning model described in the previous section ismeant to guide the coordinator in delimiting the possibilityarea by providing him with a structured procedure tofollow and by identifying the decision points where hemust intervene. Nonetheless, we wished to verify thefeasibility of implementing this method in an advisor tool.We therefore designed an interactive prototype meant toact as a wizard. The wizard guides the coordinator in theproblem resolution and structuring process. The approachwe followed is rule-based where knowledge and expertisecaptured from the coordinator are translated into rules inthe expert system component of the prototype. It wasdeveloped in the object oriented philosophy andimplemented in Visual C++; it uses Oracle andMapobjects. The knowledge bases are implemented inCLIPS [4]. The prototype contains a geographicinformation system module (GIS) for maps and geo-referenced data.The prototype allows the user to build various scenariosof what happened to the missing aircraft, where and why(hypotheses on events, pilot's decisions, and likelyoutcome). To each scenario is associated the likely routethat the pilot might have followed given the assumedhypotheses.
of 8