**** Optimization Techniques ******** *** in the Search for a Lost Person *** Thu Mar 16 20:11:27 1995 Letter : 3812390 From: kevin sweere Address : kesweere@mtu.edu Subject : Re: CSAR Digest #50 Bytes : 26633 To: Computers_In_SAR Digest Optimization Techniques in the Search for a Lost Person Kevin Sweere Superior Search and Rescue Houghton, Michigan 20 March 1995 Introduction Henry was an adventurous eight year old. His family was vacationing in the Upper Peninsula of Michigan and stopped at a county park on the shores of Lake Superior after a long drive. It was a sunny but blustery fall day; a coming storm could be seen in the western sky. The family first walked one of the several nature trails and had begun to make lunch. Henry was last seen throwing rocks into the crashing waves at 2 P.M. The family searched the immediate area and then phoned the county sheriff who called the local SAR (search and rescue) group. Once on-scene, the Search Manager had to guess where Henry might be and decide where to place his meager search resources to quickly find Henry. Law enforcement and SAR groups commonly face similar situations to the above fictional scenario. In most cases, a leader predicts where the subject may be and assigns the resources according to his/her prior experience, abilities of the searchers, family interviews, and the history of the area. This one-man decision has many short-comings and accordingly, many advances in this process have made over the past few decades, including multi-person planning groups and portable computers with search resource allocation software. The improvements have increased the efficiency and effectiveness of SAR teams, and in turn helped save many lives. Several programs present today produce a recommended distribution of resources if given a great deal of specific information regarding the probabilities of where the subject (the lost person) may be and abilities of the resources. These programs are based upon computing all the possible permutations of placing teams into the areas and then selecting the best distribution. Their greatest weakness lies in the massive amounts of scenario specific information needed and the limited number of areas and resources that can be considered in a reasonable amount of time. This paper presents an improved resource allocation process based upon optimization methods that requires less user effort during a search, can handle a greater number of areas and resources, and have several other advantages over current methods. Overall, significant advancements in resource allocation software could be made using the process. Before describing the process, explanations of several common search theory terms are necessary. Search area A search area is a defined segment of space with similar terrain and vegetation characteristics within the likely perimeter of the maximum distance the subject could have traveled. It can be a field or forest with it's size defined by units squared, or it can be a linear section, like a trail, with it's size defined by its length multiplied by a constant width. The site is the sum of all the search areas. Resource A resource is the people, equipment, and the method of searching for a lost subject. It includes, but is not limited to, ground sweep teams, tracking dogs, horse-mounted searchers, aircraft, and watercraft. The resource`s abilities are characterized by their speed, available time, amount of experience, and capability to search in a particular environment. Stereotypes A stereotype is a set of pre-determined values for variables describing an area, a lost subject, command post, or a situation. For example, hunters generally share many characteristics which can be defined mathematically, such as normal walking speed, likely direction of travel, and likeliness to respond. On a search, stereotypes are selected and the values modified slightly to fit the specific situation. Stereotypes assist in rapid processing of probabilities, are based upon many prior searches, and can be tailored to the search group's specific area of operations. POA - Probability of Area The POA is the probability the subject is in that specific area. This can be determined by several means, but group consensus is the most commonly used means of determining the POA. It relies upon the combined educated guesses of several people. Many variations on POA computations have been proposed, including one that incorporates multiple scenarios (Hill, 1991). Defining the POA based upon stereotypes and algorithms is a future possibility. The POAs change as areas are searched and cleared and as clues are found (see Appendix A). The POAs are always given as a percentage and sum to 100%, including the ROW (Rest of the World). POD - Probability of Detection The POD is an estimate of the effectiveness of one search resource in one specific area. It defines the probability that a searcher will find the subject assuming the subject is in that area. It is always given as a percentage. It depends upon the weather, season, terrain, detectability of the subject, and the type of search resource being used. Current methods allow each resource to estimate it's own POD for each area. This requires the searchers to determine and communicate their PODs for each and every area instead of using the time to search for the subject. This individual guessing is quite imprecise and subject to any whim. Below is a new way of defining POD that is based upon prior field tests, statistics of previous searches, and limited on-scene modifications and is the basis of the new resource allocation process. Each POD value incorporates area, site, command, and resource effects. Many variables are needed to define the numerous POD equations to fit a specific scenario, but since many searches are basically combinations of several general categories, selecting pre-defined stereotypes greatly reduces on-scene effort. To consider the effects of terrain and vegetation, software routines could automatically analyze digitized topographic maps and choose the appropriate values for each area. Since each resource has a different method of finding the subject (a dog follows a scent trail, a siren attracts and orients, and a grid search team sweeps an area) each resource's ability requires a separate equation. One such equation follows. POD equation for sweep searching Sweep searching is defined as searchers moving in parallel or with repeated crossings over an area in parallel and includes the line search, the Sound Sweep (Colwell, 1994), and vehicle-mounted searching (horseback, all terrain motorized vehicles, bicycles, aircraft, etc.). The PODs are polynomial equations who's coefficients are determined with a great deal of field calibration. The basic equation is PODa,b = site * areaa * resourceb * teama,b * (c1*da,b3 *c2*da,b2 +c3*da,b+ c4) where the subscripts a and b define the area and resource, respectively. The site, areaa, resourceb, and teama,b are groups of variables; site affecting every area and all resources, areaa affecting one area for all resources, resourceb concerns one resource in all the areas, and teama,b affects one resource in one area. Appendix A provides additional information on these variables. da,b is the inverse of the distance between searchers (or sweeps) for that resource and area and is without units. It is defined as da,b = peoplea,b / width of search area where peoplea,b is the number of people and the variable being optimized. The width of the search area can be assumed to be the square root of the area's size, if generally square search areas are used. POS - Probability of Success The POS is an estimate of the searchers finding a clue or the subject in that defined area and has been defined simply as POS x POA. This report provides a new and advanced mathematical definition of POS using the new definition of POD. The Process The process for solving for the optimum designation of resources using this method has several critical steps. Ideally, each of these functions would be automated and require minimal amounts of on-scene modifications. 1. Define the search areas. 2. Determine the characteristics of each area. 3. Estimate the subject's characteristics. 4. Define each search resource's abilities. 5. Determine the POA of each area. 6. Determine the transit time between areas 7. Determine the optimum placement of resources First, the site is selected by defining it's boundaries (Appendix B), divided into separate areas. Second, each area's specific characteristics are obtained by software routines, stereotypes, or prior knowledge. Third, the subject's characteristics are obtained through interviews with friends and relatives and is fitted to a stereotype with specific modifications are made thereafter. Fourth, the POAs are determined from the opinions of the family and experienced SAR personnel based upon clues found and likely scenarios. Fifth, the resource's characteristics are defined by stereotype and modified slightly. Sixth, the transit time between different areas are found by a computer routine, and finally, using optimization techniques the optimum placement of resources can be determined. The goal of the process is to select the best distribution of resources as to give the greatest chance of finding the person. Since a search consists of multiple teams and multiple areas, the overall effectiveness of the search plan depends upon the effectiveness of searching each area, or the sum of the POSs equals the overall POS. Thus the challenge is to correctly place resources into areas that maximize the sum of the POSs. As stated earlier, the POS can be defined as POSa = POAa * PODa,b (equ. 1) This works well when all the areas are the same size, rarely the case in a real search. The size of the areas are important for if two different areas have same POA but one is large and would require days to search and the other small, needing but hours, it would be far wiser to search the small area first. The POS can then be redefined as POSa = POAa/sizea * PODa,b (equ. 2) If multiple teams can search an area at the same time, the equation changes to POSa = POAa / sizea * 100 * ( 1 - (1-PODa,1) * (1-PODa,2) * ...... * (1-PODa,b) ) (equ. 3) The above equations suffer from several problems. First, all of the PODs and POAs need to be pre-defined. This precludes optimization and requires far too much time. Also, this definition doesn't consider the effects of time in planning the distribution of resources or if a team can repeatedly search an area. A more accurate model considers the availability of each resource (i.e. a helicopter has fuel for two hours of flight), the time required to move to (access) a particular area, and allows multiple searches. A new definition of POS that includes these factors is below. POSa = POAa * 100 * ( 1 - (1-(PODa,1*(timea,1 - Taccessa, olda)))*(1-(PODa,1*timea,1)ya,1)* .................*(1-(PODa,b*(timea,b - Taccessa,olda)))*(1-(PODa,b*timea,b)ya,b) ) (equ. 4) where ya,b is the number of times that resource will re-search that area, timea,b is the time the resource requires to search that area, and Taccessa, old a,b is the time the resource requires to travel to the new area. For simplicity, the access time can be defined by the distance between areas divided by the resource's speed. An advanced definition (and algorithm) allows roads and vehicles to reduce access time andconsiders the effects of the terrain, weather conditions, and such. Notice that sizea is not included. The area's width is considered the POD equation and its length is covered in timea,b. The above equation is subject to a number of constraints. Constraints such as the minimum time a resource needs to search an area depends upon the distance the resource must cover and it's speed, limits on the maximum number of radio operators and searchers, the number of different resources, and restrictions on the minimum number of people on a team are common. Other constraints depend upon the situation and the Search Managers guiding principles. Solving the Equation One POS equation is created for each area with the various PODs defined by the resources being used. The sum of the POS equations produces the overall POS. This sum is combined with the constraint equations to form a Lagrangian equation. Solving for the local maximum values will produce a number of resource allocation recommendations and the global maximum will give the optimum distribution of resources. Since the values for the number of resources must be either positive integers or zero, the common solution algorithms using continuous variables must be altered slightly. Finding the three best distributions allows the Search Manager to consider other factors when selecting the distribution of resources. Many algorithms are available to solve this problem, such as ___________, the _________ method, and ______________ (Design Opt author, page#). Also, several computer programs are available, such as Optdesx by ______. Conclusion Although the process desrcibed above finds its home best in large scale searches where trained support personnell can provide the computer work necessary to run a simulation, the ideas presented can assist all SAR groups in preparing for a search by better understanding where a subject may be and their own capabilities. In the future it is hoped additional work will find a mathmatical way of defining the POAs for each area and the above process may become part of a computer program available to SAR groups worldwide. This process provides one more tool the Search Manager can use to quickly find lost persons such as Henry. Sample Problem and Solution This problem uses the advanced definition of POS (equ. 4) with four areas and two resources. In an actual search situation, one may have as many as 30 areas search areas and 10 different resource types. Large numbers of areas and resources dramatically increase the number of variables that must be optimized and accordingly, the processing time. It is suggested that a pre-program using heuristic rules select several starting points, thus decreasing the processing time. One such rule would place a descending percentage of searchers in the greatest to least POA/size areas. Problem Statement For a search consisting of four areas (plus the rest of the world), two resource types (line and sound search) and given the information below, determine where to place the radio operators and searchers by maximizing the sum of the POS's with the following constraints: each sound search sub-team consists of one radio operator and one searcher, each line search team must have at least two people, 10 radio operators are available for 8 hours, and 30 searchers are available for 10 hours. POA = [ .30, .20, .10, .35 ] size = [ 100, 70, 80, 20 ] TWspeed = [ .3, .6, .9, .8 ] Sdetect = [ .8, .9, .99, .98 ] searchers = 30, operators = 10: Rtime = [ 1, 1 ] Lquality = .9, Lcontrol = .9, Ltime = .333, CPcommo = .98, CPquality = .99 Lspeed = .7 Wspeed = .8 Sloud = .98 coefficients for the line search = [ 6.6862e5, -1.2651e5, 6.0695e3, 4.7684 ] coefficients for the sound search = [ 7.3862e7, -2.4324e6, 2.6188e4, -7.8975 ] Solution The first step to finding the optimal distribution is to define each POD equation for each resource. Since this problem uses line and sound sweep methods, the POD equations for sweep searches are used. Explanation of all of these variables can be found in Appendix C. Every effect that can alter the POD should have an associated variable. Several variables are given below using the line sweep POD as an example. POD1,line = site * area1 * resourceline * team1,line * (c1*d1,line3 *c2*d1=,line2 + c3*d1, line+ c4) site = Rtime * CPcommo * CPquality * Lspeed * Wspeed area1 = Sdetect1 resourceline = Rtimeline * Lquality * Ltime * Lcontrol team1, line = Twspeed1 da,b = people1, line / (size1).5 The sum of the POSs is defined using the new definition of POS (equ. 4). POSsum = POS1 + POS2 + POS3 + POS4 = 100*POA1*(1-(1-(POD1, line(time1, line-Taccess1, CP,line)))*(1-(POD1,line*time1, line)y1, line) *(1-(POD1, sound*(time1, sound - Taccess1,CP, sound)))*(1-(POD1,sound*time1, sound)y1, sound)) +100*POA2*(1-(1-(POD2, line(time2, line-Taccess2, CP,line)))*(1-(POD2,line*time2, line)y2, line) *(1-(POD2, sound*(time2, sound - Taccess2,CP, sound)))*(1-(POD2,sound*time2, sound)y2, sound)) +100*POA3*(1-(1-(POD3, line(time3, line-Taccess3, CP,line)))*(1-(POD3,line*time3, line)y3, line) *(1-(POD3, sound*(time3, sound - Taccess3,CP, sound)))*(1-(POD3,sound*time3, sound)y3, sound)) +100*POA4*(1-(1-(POD4, line(time4, line-Taccess4, CP,line)))*(1-(POD4,line*time4, line)y4, line) *(1-(POD4, sound*(time4, sound - Taccess4,CP, sound)))*(1-(POD4,sound*time4, sound)y4 sound)) Next, the given constraints are converted into Lagrangian equations and then into a form the computer can recognize, which are then subtracted from the above function. h1 = v1(=94=94peoplei - (searchers - operators)/2 ) for i = 1..4 h2 = v2(=94=94radioi - operators ) for i = 1..4 gi = ui( peoplei - si) = 0 for i = 1..4 gi = ui( radioi - si) = 0 for i = 5..8 g9 = u9(peoplei - (time in the field) - peoplei*(time available) -=s9) = 0 g10 = u10(radioi *(time in the field) - radioi*(time available)- s10)= 0 h1 = v[1] * (people[1] + people[2] + people[3] + people[4] - searchers/2) h2 = v[2] * (radio[1] + radio[2] + radio[3] + radio[4] - operators) g1 = u[1] * ( people[1] - s[1] ) g2 = u[2] * ( people[2] - s[2] ) g3 = u[3] * ( people[3] - s[3] ) g4 = u[4] * ( people[4] - s[4] ) g5 = u[5] * ( radio[1] - s[5] ) g6 = u[6] * ( radio[2] - s[6] ) g7 = u[7] * ( radio[3] - s[7] ) g8 = u[8] * ( radio[4] - s[8] ) g9 = u[9] * ( people[1] *(tim[1,1] + Taccess[1,old[it,1]]) + people[1]*(tim[1,1]^(y[1,1])) + people[2] *(tim[2,1] + Taccess[2,old[it,1]]) + people[2]*(tim[2,1]^(y[2,1])) + people[3] *(tim[3,1] + Taccess[3,old[it,1]]) + people[3]*(tim[3,1]^(y[3,1])) + people[4] *(tim[4,1] + Taccess[4,old[it,1]]) + people[4]*(tim[4,1]^(y[4,1])) - ( people[1] + people[2] + people[3] + people[4] ) * Ttotal[1] - s[9] =) g10 = u[10] * ( radio[1] *(tim[1,2] + Taccess[1,old[it,2]]) + radio[1]*(tim[1,2]^(y[1,2])) + radio[2] *(tim[2,2] + Taccess[2,old[it,2]]) + radio[2]*(tim[2,2]^(y[2,2]) + radio[3] *(tim[3,2] + Taccess[3,old[it,2]]) + radio[3]*(tim[3,2]^(y[3,2])) + radio[4] *(tim[4,2] + Taccess[4,old[it,2]]) + radio[4]*(tim[4,2]^(y[4,2])) - ( radio[1] + radio[2] + radio[3] + radio[4] ) * Ttotal[2] - s[10] ) where peoplea represents two searchers in one area, necessitating a even number of line searchers assigned to an area, radioa represents a searcher and a radio operator paired together, and tima, b the time needed to search that area (the e in timea,b has been dropped since many programs use that variable for other functions) The Lagrangian is formed by combining the POD, POSsum, and constraint equations. L(people, radio) = 94POS - h1 - h2 - g1 - g2 - g2 - g3 - g4 - g5 - g6 -g7 -g8 - g9 - g10 The complete equation in variable form and then with the sample values included is given on the following pages. These were computed by Maple (Mathworks,1985), a symbolic math program. The problem has a total of _______ dimensions and required ______ minutes to solve using _______ on a __________ computer. The computer suggested the following two distributions and their associated POSs (on the page following the program code). Suggested Resource Allocation .......... of starting point of.......... Area Suggested Distribution POS 1 # searchers in a line # sound sweep pairs 09 2 # searchers in a line # sound sweep pairs 09 3 # searchers ina line # sound sweep pairs 09 4 # searchers ina line # sound sweep pairs 09 POSsum = Suggested Resource Allocation .......... of starting point of.......... Area Suggested Distribution POS 1 # searchers in a line # sound sweep pairs 09 2 # searchers in a line # sound sweep pairs 09 3 # searchers in a line # sound sweep pairs 09 4 # searchers in a line # sound sweep pairs 09 POSsum = Appendix C: Definitions of Variables Line Search Ltime1 - difference between walking and searching Lquality - quality of searchers in regards to line searching (untrained or professionals) Lcontrol - the difficulty of controlling people, based upon the number of searchers Time Tmissing - time the subject has been lost (from the Last Known Point) Ttotal - the total time a resource has to search Taccessa, old a, b - access time; time required for a specific team to travel from their present location (old area) to another (new) area Command Post CPcommo - quality of communications (eg. experienced net controller with trained ham radios operators or CB units with novice operators) CPquality - overall quality of the command post (eg. a trained Search Manager in a comfortable RV with full support, or a novice sitting in a pickup truck) Resource Rtime - time the resource has been searching, considers searcher fatigue Area TWspeed - effect of terrain on walking speed TVspeed - effect of terrain on a vehicles speed Wspeed - effect of weather on movement Lspeed - effect of amount of light on movement (varies with day or night) Ssound - distance sound travels (based on audibility of a set decibel level) Subject Sdectect - detectability of the subject (blaze orange or camouflage clothing) Sspeed - speed and endurance (walks miles daily or can only move with assistance) Appendix B : Outer Boundary Determination The outer boundary is typically drawn as a circle about the Last Known Point (LKP) with the radius and Maximum Total Search Area (MTSA) defined by Radius = Tmissing * Sspeed * Tspeed * Wspeed * Lspeed MTSA = =93 * Radius2 The maximum area can quickly grow to immense sizes. For a typical adult missing for 4 hours in moderate terrain, the MTSA is 200 square miles. Statistically, most subjects are found within 3 miles of the LKP, regardless of the time they have been missing. This gives a MTSA of 29 square miles. This can usually be reduced further if one eliminates inaccessible areas (such as water surfaces and sheer cliffs). A good deal of educated guessing comes into play if the subject has been missing for more than an hour. Appendix A: Updating the POA using search results The optimization equations allow one to determine the best allocation of resources at the moment the analysis is run. Since a search is constantly changing, continual updates of the original plan must be made. The primary variable that changes is the POA. If after searching, the subject was not were found in the area, the chances of that person being in the area decrease. Likewise, if a clue was found in the area, the POA for that and adjoining areas increases. The POA after an area was searched decreases according to the equation (Lavalla, _) POAa, k+1 = POAa, k * 100( 1-(1-PODa,1)*...*(1-PODa,b) ) ------------------------------------------------------- 1 - POAa,k * 100( 1-(1-PODa,1)*...*(1-PODa,b) ) The POAs for all the other areas including the ROW (Rest of the World) increase according to following equation where arean are all areas that are not areaa (the area that has just been searched) and k is the iteration. POAn, k+1 = POAn, k ---------------------------------------------------------- 1 - POAa,k * 100( 1-(1-PODa,1)*...*(1-PODa,b) ) Since updates about different areas are constantly coming into the Command Post, it is suggested that a computer routine continuously update the POA as information is obtained and the next optimization calculation occurs after a significant number of areas have been searched and/or during a lull in the operation (such as during the night). References Colwell, Martin. Search Priority - an Integrated Approach to Search Planning. 1994 Conducting a Sound Sweep - Instructions to Search Teams, 1994 Lavalla, Stoffel, Wade. Search is an Emergency, Emergency Response Institute, Olymipia, Washington, 1981 Hill, Kenneth. Scenario Analysis in Land Search Planning, Wverly Ground Search and Rescue, Nova Scotia, Canada.1991 Bownds, Ebersole, and Lovelock. C.A.S.I.E. III (Computer Aided Search Information Exchange III), Tuscon, AZ: 1992. Design Optimization, 'bout it -------------------------------------------------- Kevin Sweere M.S. ME, Michigan Tech U. PO Box 372 2LT Army, Armor Dollar Bay, MI 49922 Prez Superior SAR (906) 482-2251 ARC Disaster Team kesweere@mtu.edu N0RRU http://www.hu.mtu.edu:80/~kesweere/ --------------------------------------------------