Using an agent-based model to identify high probability search areas for search and rescue

Thousands of people become lost in the wilderness each year and search and rescue personnel are called in to search for and to locate people who are lost. Time is critical as the lost person's chance of survival decreases over time. One method of improving search outcomes is efficient and accurate planning of search areas. Search and rescue planning techniques have been developed over time through extensive training, experience and knowledge. To expedite the search area planning process, an agent-based model (ABM) was used to highlight probabilistic and evidence-based areas typically considered by search area planners. This model takes spatial data calculated to a time-cost raster and incorporates lost person characteristics to determine location-specific probability data that can be used in decision-making.

Introduction

Hiking in the wilderness is a popular pastime with benefits for personal fitness and wellbeing as well as creating positive relationships with the physical environment (Taczanowska et al. 2014). In Australia, hiking was the sixth most popular physical activity in 2019–20, with approximately 1.5 million adults participating (Sport Australia 2021). With hiking being so popular, it is unsurprising that thousands of people get lost every year (Alanis et al. 2019, Department for Transport 2022, Australian National Search and Rescue Council 2019). In 2019, search and rescue (SAR) organisations in Australia conducted 1,820 land operations to locate lost people (Australian National Search and Rescue Council 2019). With the probability of a lost person's survival decreasing over time, proper planning to make the search more efficient is essential (Syrotuck 1976). Practical tactics can be employed to reduce this time such as reducing the size of the search area using better geographic assessments of where the lost person is likely to be and to find the missing person in the shortest possible timeframe (Doherty et al. 2014, Ferguson 2008).

Spatial modelling has been incorporated in SAR using mobility models that estimate the distance a lost person may have travelled (Doherty et al. 2014, Alanis et al. 2019, Yoo & Lee 2019). When a person is lost in the Australian wilderness, SAR personnel use a spatial model referred to as the 'ring model' to assist searchers to locate the lost person (Australian National Search and Rescue Council 2020) (Figure 1). The ring model indicates to search planners how far a lost person may be located away from their last known position (LKP) based on statistics from previous search incidents. The ring model is a common way to assign probabilities to search regions. It is based on quartile distance statistics and uses buffer rings from the LKP as probability circles by subject categories (Sava et al. 2016).

Figure 1: The ring model with Euclidian distances from the LKP for the hiker category.
Source: Koester 2008

Spatial modelling has been developed to assist in narrowing the possible location of a lost person. Probability mapping conducted by Jacobs (2015) used the percentage of lost people found in locations with specific terrain characteristics to determine the probability of a likely location based on those characteristics. Drexel, Zimmermann-Janschitz and Koester (2018) used network analysis of linear features as well as elevation and statistical data to determine areas of probability for lost person locations. The watershed model was used in Yosemite National Park by Doke (2012) to determine the number of watersheds crossed by a lost person in order to create a probability map of watersheds most likely to contain the lost person. Lin and Goodrich (2010) used a Bayesian approach to generate a probability map for SAR. This method drops thousands of simulated subjects around the LKP and a Markov Chain Monte Carlo1 simulation is run where the probability of moving from one cell to a neighbouring one is dependent on the environment in both those cells (Sava et al. 2016). In a similar approach, Alanis et al. (2019) developed a mechanistic model using a Markov Decision Process, specifically a Decision Tree Algorithm that incorporates a heuristic pathfinding algorithm to predict the movements of a person lost in the wilderness. There is currently no evidence to suggest that any of the spatial models described, beyond the ring model, have been used in real-time SAR incidents.

When SAR commanders are planning search areas, they look for features in the area that, through their training and experience, stand out to them as areas a person might likely be, such as tracks, ridgelines, fences and rivers. Conversely, they also identify areas a lost person is unlikely to have travelled to due to terrain difficulty or behavioural reasons. These subjective assessments could be incorporated into spatial models, providing more consistent approaches and opening them to rigorous scrutiny.

ABMs are potent tools that can help to understand the behaviour in complex spatial systems (Ye & Mansury 2016). They have shown promise in SAR application, as they incorporate movement across landscapes. ABMs consist of 3 elements: an agent, the environment and interactions between ‘agents’ (autonomous decision-making entities) and the environment (Macal & North 2010). The environment is where phenomena occur, and agents inhabit that environment (Gammack 2015). Some studies have successfully used ABMs as a probabilistic approach to SAR (Hashimoto & Abaid 2019, Mohibullah & Julier 2013, Mohibullah 2017). However, these studies are based on developing total search areas for searching by unmanned aerial vehicles not by a ground search by search teams. Hashimoto et al. (2022) created an ABM using a combination of real-world terrain data and lost person incident behaviour data. Rather than determining search areas, they used the model output to determine behavioural profiles of hikers (Hashimoto et al. 2022).

This paper describes the application of an ABM developed to model the movement and probable location of people lost in the wilderness in Australia. The model is outlined and the output assessed to highlight areas that may be considered in search area planning.

Methodology

Study area

Tidbinbilla is a nature reserve in the Australian Capital Territory and was selected as the region for study and application of the model. The study area selected within Tidbinbilla Nature Reserve is formed by a rectangle of 19 km by 11 km (centred on -35.44959 148.86686) with an area of 209 km2 and elevation ranging between 594 metres and 1,649 metres (Figure 2). This study area was chosen because it contains varied terrain and attracts many visitors due to the popularity of walking tracks. Tidbinbilla is an area where SAR assistance has been needed due to lost person incidents (P. Ibbott, personal communication, 11 December 2020).

Figure 2: The study area for the model was Tidbinbilla Nature Reserve in the Australian Capital Territory.

Data

There is spatial data that influences how people traverse wilderness regions. The first is a terrain ruggedness index (TRI) layer, which captures the elevation difference across the terrain (Bosworth-Ahmet 2020). The second is a vegetation density layer. To create these layers for the study area, LiDAR2 data were obtained from the ACT Government. These data were resampled to create a 40-metre Digital Elevation Model (DEM). From the TRI and vegetation density rasters, a cost raster was created reflecting the amount of time it would take to traverse each 40-metre cell horizontally or vertically using an average human walking speed (Peper, de Dreu & Roerdink. 2015). The use of Naismith’s law, as used by SAR personnel was considered. However, the technique used in the model measures the cost of crossing a cell without considering the slope or direction of travel. Travel time increased from 0.49 minutes to traverse a cell with low vegetation density and less rugged terrain to 1.30 minutes (165% increase) for cells with dense vegetation and rugged terrain. The walking tracks within the study area were created as a vector layer using a combination of the ACT Road Centrelines dataset (ACT Government 2021) and manual digitisation of a Strava heatmap of the area (Strava 2021).

ABM specification

The ABM was developed using Netlogo software (Wilensky 1999). This software was chosen as it is open source, there is extensive support documentation online, and it has a Geographic Information System (GIS) extension that allows raster and vector data to be incorporated into the model.

An ABM requires an environment and agents who interact with the environment. Agents are placed within the model and provided with simple rules to govern their behaviour. At each time-step, an agent autonomously decides whether to move and, if so, in which direction. The decisions made by agents are determined using rules incorporating behavioural characteristics and the underlying environment as well as the inclusion of randomness. Decisions about whether an agent moves depend on the current cell, characteristics of surrounding cells and the characteristics of the agent itself. Even though an agent can only move one cell, they can take a much larger neighbourhood into account for decision-making.

In the model for this study, the agents represent multiple instances of a single lost person, initially placed randomly within a user-specified radius of the last known point of the lost person to account for uncertainty in location, the time lost and movement prior to the search commencing. The time elapsed is set as the total time lost and agents individually record the time taken to traverse a cell or the time spent resting. As the agent moves, it maintains an attribute list including the current goal (which determines the direction the agent will face), the time elapsed, distance covered and fatigue level.

The model parameters include the likelihood a person would stay on a track, the possibility of stopping on a track and the physical condition of the lost person. The physical condition is represented as the time before fatigue sets in and incorporates the amount of rest required before continuing. Stochasticity (randomness) was integrated into the model through the random starting point of each agent and the direction they are facing, the agent's autonomous choice of goals, randomness of the fatigue elements as well as the required rest time. It is important to incorporate a level of randomness into the model due to the complexity and high degree of variability in human behaviour and decision-making.

Running the model

While it is possible to run the model with numerous variations of parameters, 3 theoretical case studies were developed to demonstrate how different parameters based on lost person behaviour can affect the model's outcome. The case studies were determined using results from the study by Darcy (2021) into lost person behaviour in the Australian wilderness. The first 3 case studies use profile characteristics outlined in Table 1. All 3 case studies assumed the same LKP and time lost. The model was run for the same length of time (4 hours). These case study profiles translate to the parameter settings in Table 1.

Each of the lost person scenarios was run in the model and the output was exported to a GIS. Kernel density analysis was conducted to determine the probability quartiles and a 95% probability area.

Results

Table 1: Parameter settings for case studies.

Case study 1

Case study 1 modelled a 35-year-old female hiker with poor-to-moderate physical condition and little experience in the wilderness (Table 1). The resulting probability map (Figure 3) is consistent with the profile female staying on track and being more likely to stop once on a track, hence the high density on the tracks closest to the LKP.

Figure 3: Kernel density analysis results from case study 1 overlayed with the ring model.

Case study 2

Case study 2 was of a hiker with the profile of a 60-year-old male with moderate physical condition and high experience in the wilderness (Table 1). The model predicted a larger search area than in case study 1, with the highest probability areas located around a nearby track (Figure 4). This is consistent with a person who does not move a significant distance and tends to stay near tracks.

Figure 4: Kernel density analysis results from case study 2 overlayed with the ring model.

Case study 3

Case study 3 modelled a 19-year-old male hiker with good physical condition but little experience in the wilderness (Table 1). The results showed the high mobility of the lost person and a high probability of moving off tracks (Figure 5), which is consistent with the profile. The high probability areas away from the tracks include ridgelines and some valley areas.

Figure 5: Kernel density analysis results from case study 3 overlayed with the ring model.

Discussion

Time is a critical factor in the survivability of a lost person (Sava et al. 2016). This study demonstrated how an ABM can incorporate spatial and lost person behaviour to highlight areas of probable value to a search area planner to expedite the planning process. The results from the case studies show that the characteristics of a person and the terrain they are trying to traverse can significantly affect their likely location.

While SAR personnel are aware of the relationship between lost person behaviour and terrain, the model can emphasise areas using data to provide likely search locations for consideration in search area planning. This is visualised in the first case study, where the lost person is more likely to stay near a track and not travel far due to lower physical condition. Case study 2 showed a dispersed probability area, although the highest probability was to remain near a track. When people are more mobile and tend to travel further, as demonstrated in the case study 3, the higher probability areas derived from the model tend to be clustered about areas containing paths. However, the search area itself can be much larger. When off-track, areas of less challenging terrain are more probable locations, indicating that the agents in the model consider the cost of traversing a cell prior to moving and choosing the path of least resistance. Case study 3 showed higher probability areas circular from the starting point that demonstrated that the agent ignored the paths. This creates a ring indicating where agents reached after 4 hours, with a high probability of travelling further and being less likely to stop on paths.

The model considers that a person will likely move to a path if a path is visible, choosing the least challenging terrain to get there and changing direction depending on the difficulty of the terrain and what they can see. Using an ABM, search area planners can consider the results of the model when making decisions on where to start searches and where to focus effort and human resources.

Factors such as fatigue as well as the difficulty of the terrain a lost person may be traversing are generally taken into account by search planners. The Australian State Police Search and Rescue Coordinator's Course Training Booklet (Whitehead 2018) encourages SAR personnel to apply the subjective method to search area planning. This method uses maps and professional knowledge to assess the terrain, boundaries and potential barriers to identify search areas. This ABM builds on that knowledge and provides additional evidence-based advice for decision-making in search area planning.

Model limitations and potential improvements

Parameterisation of ABMs can be subjective and difficult to validate. However, the goal of the model is to highlight areas that may be considered for a search rather than attempting to predict the exact location of the lost person. By using the ABM and understanding how lost people behave and react within the environment, informed recommendations can be made of which areas are the highest priority in search area planning.

While the model is stochastic, some static numbers informed by research into human movement (Gast, Kram & Riemer 2019; Peper, de Dreu & Roerdink 2015) are still used that limit the randomness of the model. It is possible to change these numbers within the code to reflect a real-life situation better when the incident warrants it. Further development and refinement of the model is required for operational use, including incorporating additional lost person behaviour, decision-making and how lost people choose their goals. However, comparing the model outcomes with points of interest in search planning shows that these assumptions and parameters are plausible and realistic.

Currently, within the model, the main goal for the lost person is to find a track and either continue to travel on it or to find another track. The incorporation of additional goals for agents might prove beneficial to increase the model’s accuracy.

SAR personnel use decision points to pinpoint locations where a lost person may have veered off course or lost the track, such as at track junctions, water crossings, sharp bends, or elevation changes (Australian National Search and Rescue Council 2020). Koester (2008) recommended that the next step for computer-based planning tools would be to locate these decision points for use in algorithms that take advantage of that information. Further development of the model presented in the study could assist to determine such features through studying agent movement. The model could be expanded to determine the least-cost path for navigation and to highlight accessibility and predict human movement in the wilderness for emergency planning and protected area management.

Implications of applying the model to SAR

One complicating factor in all human movement modelling is that the behaviour of people can be difficult to predict when combining unknown goals, motivations and decision-making processes. This is especially the case with lost people, who can act irrationally and out of character due to emotions such as fear Dacey (2021). There is further uncertainty when a person is lost as to whether they are genuinely lost or if they are simply overdue, or if they are trapped or injured (Koester 2008). The model described in this paper can be developed to be an accurate predictor of human movement in the wilderness. With the inclusion of additional data such as updated agent goals, behavioural and movement information and appropriate validation data, the model could be used as a location predictor rather than an indicator of areas of interest.

The ABM described in this study has parameter settings that can be altered based on lost person characteristics. The spatial data requirements are terrain ruggedness, vegetation density and track data. With these datasets preloaded, there is no requirement for connectivity to the Internet and it is possible to run the model in the field during a SAR incident. However, current data availability and processing speeds means it is not feasible to develop and run models in real-time to be used in the field. The results of the model can be displayed on a map that can be considered in search planning.

Conclusion

The ABM used in this study showed that this type of model can be an additional tool for search area planning by highlighting areas of interest for search area planners. While no model produces exact results, ABMs are powerful spatial models that can produce complex patterns based on simple movement rules. However, they are under-used in SAR and similar applications. The model requires limited publicly available spatial data and can be adapted to most wilderness areas. Having an automated process for developing the underlying environment raster and creating a user-friendly application to run the model may encourage its use in SAR incidents. While there is a great deal of uncertainty in lost person behaviour, this model uses randomness combined with accurate spatial data and statistically significant lost person behaviour to highlight probable areas a lost person may have travelled. The results of this model are aimed at search planners to provide additional information to refine search areas by producing evidence-based information for planning. With development and validation, the model has strong prospects as a search area planning tool to provide individualised results based on the lost person situation.