Urban search and rescue (USAR) simulation system: spatial strategies for agent task allocation under uncertain conditions

Task allocation under uncertain conditions is a key problem for agents attempting to achieve harmony in disaster environments. This paper presents an agent-based simulation to investigate task allocation considering appropriate spatial strategies to manage uncertainty in urban search and rescue (USAR) operations. The proposed method is based on the contract net protocol (CNP) and implemented over five phases: ordering existing tasks considering intrinsic interval uncertainty, finding a coordinating agent, holding an auction, applying allocation strategies (four strategies), and implementing and observing the real environment. Applying allocation strategies is the main innovation of the method. The methodology was evaluated in Tehran's District 1 for 6.6, 6.9, and 7.2 magnitude earthquakes. The simulation began by calculating the numbers of injured individuals, which were 28 856, 73 195, and 111 463 people for each earthquake, respectively. Simulations were performed for each scenario for a variety of rescuers (1000, 1500, and 2000 rescuers). In comparison with the CNP, the standard duration of rescue operations with the proposed approach exhibited at least 13 % improvement, with a maximal improvement of 21 %. Interval uncertainty analysis and comparison of the proposed strategies showed that increased uncertainty led to increased rescue time for the CNP and strategies 1 to 4. The time increase was less with the uniform distribution strategy (strategy 4) than with the other strategies. The consideration of strategies in the task allocation process, especially spatial strategies, facilitated both optimization and increased flexibility of the allocation. It also improved conditions for fault tolerance and agent-based cooperation stability in the USAR simulation system.

1 Introduction

Preparation to manage an earthquake crisis requires optimal and appropriate management. Agent-based modeling of search and rescue operations after an earthquake is a good model for decision-making compared with traditional computational approaches (Hooshangi and Alesheikh, 2018). Multi-agent systems consist of several automatic and autonomous agents that coordinate their activities to achieve a target (Crooks and Wise, 2013; Sabar et al., 2009). Multi-agent systems are suitable for the modeling and simulation of complex systems (Mustapha et al., 2013). They allow for the division of the system into subdivisions (agents) and the modeling of the relationships among these agents (Uno and Kashiyama, 2008). The use of multi-agent systems is necessary for disaster management (Hawe et al., 2015; Grinberger and Felsenstein, 2016). Importantly, multi-agent systems can be used to implement various scenarios of search and rescue operations, as well as distributions of facilities, in the crisis area (Crooks and Wise, 2013).

Task allocation is one of the main coordination challenges among sets of agents in a multi-agent system (Liu and Shell, 2012; Nourjou et al., 2011; Chen and Sun, 2012). Agents fail to reach their ultimate goal without proper assignment of tasks (Reis and Mamede, 2002). In disaster environments, urban search and rescue (USAR) and the assignment of tasks are dynamic processes occurring under uncertain conditions (Hooshangi and Alesheikh, 2017). Generally, task allocation on a large scale is influenced by uncertainties and various factors (Cai et al., 2014). Uncertain conditions have a major impact on the initial planning and results of rescue operations (Hooshangi and Alesheikh, 2018). Despite various investigations, an optimal task allocation solution has not been established (Olteanu et al., 2012).

In many instances, the initial allocation may result in problems or new tasks may be added to the worklist; therefore, reallocation is necessary. Reallocation is an effective reaction to environmental uncertainties and changes and has important roles in both reducing the wasted time during an operation and increasing operation profitability (Zhang et al., 2014). Reallocation after instantaneous disruption is very important, especially in large-scale distributed systems (e.g., USAR operations) (Olteanu et al., 2012). An effective task allocation approach in USAR operations should include strategies for replanning to manage future situations. Because tasks may not be performed well for various reasons, strategies such as minimum location displacement should be applied to initial responses to preserve additional time during reallocation or future task allocation. This approach to task allocation optimizes planning performance to achieve better performance time and provides conditions for fault tolerance.

The present article is the final part of a research project in Iran. This research project was carried out over three phases. In the first phase, uncertainty in task allocation among agents was considered, and task allocation was performed only by considering the proximity (spatial distance) to the tasks. The developed method was evaluated in a square-shaped random environment without a sensitivity analysis (Hooshangi and Alesheikh, 2017). In the second phase, the feasibility of the developed method was investigated in a simulated environment using real regional data. In this phase, the operational environment of a crisis was simulated, and the developed method was examined in a real environment. In the simulated system, damage for a 6.8 magnitude earthquake was calculated for District 3 of Tehran, and rescue operations were modeled (Hooshangi and Alesheikh, 2018). In the third phase using the concepts of previous articles (Hooshangi and Alesheikh, 2018, 2017), spatial strategies were included in task allocation among agents and simulated with real-environment data. The present paper is the output of the third phase of the research project. The main purpose of the research is to improve task allocation in crisis-ridden conditions for agent-based groups by considering proper strategies to manage uncertainties. This paper first develops an agent-based simulation system for USAR operations, then applies uncertainties in agent decision-making by improving an interval VIKOR method to perform task allocation, and defines strategies for conditions under which the initial assignment has encountered a problem and requires reallocation (i.e., managing availability uncertainty during implementation). The innovation of the study is the establishment of an approach to improve conditions during reallocations or future allocations when initial allocations encounter problems, due either to availability uncertainties or the addition of a new task. In general, strategies are selected in such a manner that the final cost of the system will not increase abnormally if the initial allocations encounter problems. By applying spatial strategies in the assignment of tasks, it is expected that the assignment of tasks in conditions of uncertainty will be done optimally and more quickly.

2 Literature review and background

2.1 Agent-based USAR simulation

An agent-based model is a class of computational models for simulating the actions and interactions of autonomous agents. Agent-based simulations have been used in various investigations including crisis/disaster management (Wang et al., 2012; Hooshangi and Alesheikh, 2018), emergency supply chains (Ben Othman et al., 2017), tsunamis (Erick et al., 2012), and collective behavior (Welch et al., 2014). These simulations can be effective in both planning and policymaking (Fecht et al., 2014). Simulation of the operating system involves a simplified real environment, which is used to model a wide range of agents in complex systems. Various researchers have modeled a portion of the behavior of agents in simulated environments (Erick et al., 2012; Wang et al., 2012; Matarić et al., 2003) and demonstrated collaboration among agents. However, agent cooperation in catastrophic environments has been less extensively studied, such that uncertainty in collaboration among agents has generally not been considered. In previous studies, a geospatial information system platform was used when preparing the environment and creating a simulation base map (Welch et al., 2014). Spatial analysis and related tools are used in most research endeavors in USAR operations after an earthquake.

2.2 Approaches to applying uncertainties in task allocation

Agents should include environmental uncertainties in their performance with respect to planning goals. There are four common approaches to considering uncertainty: probabilistic, fuzzy logic, rough set, and interval set (Hooshangi and Alesheikh, 2017). Uncertainty in task allocation has been investigated in various studies that can be categorized as sensor noise (Liu and Shell, 2011; Bertuccelli et al., 2009; Matarić et al., 2003), an accidental event during execution (Lee and Al-yafi, 2010; Li and Cruz, 2005), the occurrence of new tasks (Xiao et al., 2009; Kayır and Parlaktuna, 2014), the number of groups (Quiñonez et al., 2011; Dahl et al., 2009), the relationship among agents (Choi et al., 2009; Su et al., 2016), and decision parameters (Hooshangi and Alesheikh, 2017).

The above-mentioned methods have been used in various applications such as multiple unmanned aerial vehicles (Bertuccelli et al., 2009), supply chains (Dahl et al., 2009), moving plants (Tan and Barton, 2016), and disaster environments (Su et al., 2016). There is no dominant approach to model uncertainty for all phenomena. The appropriate method is determined based on the characteristics of the phenomenon and the purpose of the study. In crisis environments, there is uncertainty in all decision parameters. In the category of uncertainty in decision parameters, which is suitable for multi-agent systems, uncertainties are associated with the decision parameters for assigning tasks. Therefore, all information needed for task allocation is considered uncertain. Various methods such as the contract net protocol (CNP) (Hooshangi and Alesheikh, 2017), stochastic scheduling (Tan and Barton, 2016), and genetic algorithms (He et al., 2014) have been used in these contexts. Here, we present an approach that includes uncertainties in decision parameters and strategies in the CNP. The CNP produces local optimal solutions that are abundantly used in multi-agent systems (Choi et al., 2009). This method is simple and practical and is popularly used in agent-based modeling. In USAR operations, complete individual expertise is impossible due to a lack of environmental knowledge; therefore, determining membership function and the probability distribution is a complex and time-consuming step. We used interval analysis to manage these shortcomings and to consider the intervallic nature of available data within a rescue operation. In the interval set method, due to the uncertainty in a parameter's value, that parameter is specified as an interval regardless of the probabilistic distribution (unlike in probabilistic theory) or membership function (unlike in fuzzy logic) (Hooshangi and Alesheikh, 2017).

2.3 Reallocation and reassigning methods

Distinct algorithms have been proposed for scheduling and task reallocation in accordance with the tasks and available conditions within an environment (Gokilavani et al., 2013). Some reallocation methods (e.g., data envelopment analysis; Barnum and Gleason, 2010) and exact algorithms (e.g., a branch-and-bound algorithm with column generation) resolve problems on a smaller scale (e.g., 10 jobs and three vehicles). In such methods, the process is time-consuming and slow for resolving large-scale problems (Cai et al., 2014). Therefore, they are not suitable for the allocation of tasks that should be performed dynamically and instantaneously in large-scale problems.

In some research, such as the investigation of gate reassignment problems, initial assignment tables have been created using heuristic methods in such a manner that a succession delay is minimized (Cheng, 1997). The incidence of adverse events may disrupt the original table. Notably, this method is not suitable for a large number of tasks. Some other task allocation methods are interdependent with the plan's ongoing tasks, such as in construction operations (Olteanu et al., 2012). In those mathematical calculations, when a task fails, all other tasks that were based on its correct implementation must be replanned.

An appropriate reallocation method must be applied with respect to the nature and scale of the problem. In USAR, a rescue process generally occurs independently of any other rescue processes, and only a portion of the workflow is ready to be implemented and assigned. Moreover, because of the large number of rescue groups in USAR operations, as well as the available uncertainties and dynamic nature of multi-agent systems in disaster environments, the concept of general planning is uncommon, and appropriate plans should be produced both locally and cross-sectionally. Most available methods to resolve the problem of assigning tasks cannot be developed for uncertain conditions and restrictions such as in critical rescue environments (e.g., USAR after earthquakes).

With respect to USAR operations, task allocation methods must include different strategies for all conditions and be dynamically generated in a real-time environment. In contrast to previous studies, we define an approach based on spatial strategies, such that the results of the initial task allocation are used for future task allocations and are appropriate in the rescue environment. Time limitations constitute another issue in the reallocation and reassignment of rescue teams. Therefore, the present study aims to expand the CNP method for rapid problem resolution.

3 Case study and data

The proposed approach can be implemented in various study areas. This study used a part of Tehran (District 1 in the capital of Iran) to evaluate the feasibility of the proposed method on the basis of available data. District 1 is one of 22 central districts of Tehran Province, Iran. District 1 has an area of 210 km² and is located in the northernmost part of the city of Tehran (Fig. 1). Its population is 433 500.

Figure 1 Location of case study: (a) peak ground acceleration map of Iran for a return period of 2475 years and approximate location of Tehran and (b) location of District 1 and active faults in Tehran. (c) Map of District 1 (study area) and active faults, Tehran.

The recent Tehran earthquake (5.2 magnitude) in December 2017 attracted the attention of many urban planning organizations. Tehran is a highly seismic area because it is surrounded by the Rey, Masha-Fasham, and North Tehran faults (Fig. 1b). Tehran is located in the southern part of the Alborz Mountains, where a magnitude 7.3 earthquake occurred in 1990 (Berberian and Yeats, 2016; Hamzehloo et al., 2007). Seismologists have reported that a severe earthquake may occur in Tehran in the future (Hosseini et al., 2009). The North Tehran fault is the city's largest fault and is approximately 175 km long (Kamranzad et al., 2020). For this purpose, the North Tehran fault scenario, with the capacity to cause the most destructive potential earthquake in Tehran, was selected in the present study. Various scenarios have been simulated in seismic studies in Tehran, such as 6.8 and 6.9 magnitude earthquakes. The method developed in this research can be implemented for any scenario. In accordance with the previous earthquakes and suggestions of seismologist experts, we simulated 6.6, 6.9, and 7.2 magnitude earthquakes. The basic data used in environment simulation were block maps, population, distance from the fault, building material, agent location, year of building construction, and building height.

4 Materials and methods

In this section, the simulated scenario and proposed method are described.

4.1 Scenario of proposed agent-based USAR simulation

We assume the presence of a disaster environment in which events are uncertain. In this scenario, the crisis is assumed to be an earthquake. The injured individuals are trapped under rubble, and the number of such individuals in each building block is uncertain. Rescuing injured people is the main goal. Saving each person is a task that must be performed through the cooperation of rescue agents. After an earthquake, the numbers of injured and deceased people can be estimated using different formulas by determining the magnitude and location of the earthquake, as well as the urban context data of the buildings (Kang and Kim, 2016). Furthermore, the possible locations of injured individuals can be predicted using building damage assessment models. Therefore, the simulation inputs are the injured individuals' locations and their characteristics, which are available with some uncertainty. The rescue agents are attempting to save injured individuals by moving toward the task location. Given the results of previous studies (He et al., 2014; Hooshangi and Alesheikh, 2017; Sang, 2013; Chen et al., 2012) and in accordance with expert opinion on USAR operations, the uncertainties include the number of injuries, severity of the victims' injuries, duration of the operation, infrastructure priorities, agent energy, route status, task runtime by an agent, and risk level for each agent. These are important uncertainties in task allocation. All parameters are specified as intervals during the task allocation process. After task identification, an agent is assigned a task and pursues it. If an agent fails to complete an assigned task because of any existing disruptions, the task is updated with respect to uncertainties and reported to the central agent, resulting in the reinitiation of the task allocation process. In this process, task allocation strategies are applied to minimize the cost of the system.

In this scenario, there is a central agent, as well as several coordinators, rescuers, and injured agents in the environment. These independent agents are rational and can communicate with each other. The agents have the following roles and characteristics:

• Central agent. This agent is responsible for sorting the tasks, specifying the coordinators, determining the results, announcing rescuers, and applying allocation strategies.

• Coordinating agent. The coordinator is a rescue agent who is responsible for sending work details to rescuers, receiving their proposals (bids), holding auctions, and submitting the results and rescuer prioritization data to the central agent.

• Rescue agent. This agent identifies and moves to the task location, searches for injured individuals, sends the task uncertainty to the central agent, and rescues injured individuals from the debris.

• Injured agent. This agent exists in the environment and has a critical condition that changes continuously. This agent has no activity or communication with other agents.

4.2 USAR simulation

In preparation for the USAR operation simulation, there are three main parts: (1) calculating the damage rate of the area and people (simulating an earthquake-damaged environment), (2) defining agents and their characteristics, and (3) implementing the suggested method for task allocation between agents.

To simulate an earthquake-damaged environment, an earthquake risk assessment model was developed based upon the Japan International Cooperative Agency (JICA) model. The JICA model is the output of cooperation between the Center for Earthquake and Environmental Studies of Tehran and the JICA. The results of this project and its implementation have been presented previously (Mansouri et al., 2008) and used in various studies (Hooshangi and Alesheikh, 2018; Vafaeinezhad et al., 2009). This model can calculate the buildings' level of destruction and the number of injured people based on the earthquake intensity, earthquake location, building vulnerability, and the population in these buildings.

In our scenario, we included four types of agents: injured individual, rescuer, coordinator, and central agent. The tasks described in the previous section were implemented for each agent. The initial locations of injured agents were based on building damage, and the locations of rescue groups were randomly generated in the environment. The definitions of agents and their characteristics were described in detail in our previous article (Hooshangi and Alesheikh, 2018).

4.3 The proposed method

The proposed model for task allocation with uncertainties in earthquake USAR operation is shown in Fig. 2.

Figure 2 Task allocation flowchart in the proposed approach, separated into five steps within an environmental simulation.

The five steps of the proposed approach are the ordering of existing work, specifying the coordinators, holding an auction, applying reassignment strategies (the innovation of this paper), and implementing and observing environmental uncertainties (performed by an agent). The proposed method is presented below.

4.3.1 Ordering existing tasks

In crisis-ridden areas, there are varying degrees of urgency (Chen et al., 2012). Tasks with a higher priority must be performed first. Four parameters are used to prioritize tasks: the number of victims, severity of injuries, time required for a rescue operation, and infrastructure priorities. The initial tasks with their uncertainties in the environment (four priority parameters) are available to the central agent. Therefore, for each task feature, an interval such as that expressed in Table 1 is specified.

Table 1 Task characteristics based on intervals.

To manage interval data in the CNP, various multi-criteria decision-making methods are proposed. The interval-based VIKOR method is used extensively to coordinate agents in the assignment of tasks with interval data (Hooshangi and Alesheikh, 2017). The interval-based VIKOR method has been previously described (Sayadi et al., 2009). Ordering is performed by the central agent.

4.3.2 Finding the coordinating agent

For each task defined by the central agent, the most appropriate agent is identified as the coordinating agent. The coordinating agent is an agent who is located near that task and is not currently working. The selection of a coordinating agent and creating groups to execute any task can be achieved through different methods and is based on various criteria (Chen and Sun, 2012; Su et al., 2018). In this study, to simplify the calculations, only the criterion of proximity (spatial distance) is used to identify the coordinating agent. Therefore, the nearest agent to the task is selected as the coordinator and is responsible for the auction. Selection of a coordinating agent leads to the performance of calculations at a distributed point. By selecting coordinating agents, the computational overhead of the central agent is reduced.

4.3.3 Holding an auction

Coordinating agents hold auctions after receiving the task characteristics and the list of agents in the subgroup. In the CNP, agents bid for tasks, and the agent who offers the highest value for the task is the winner. During the auction, rescue agents offer intervals (rather than values) for the route conditions, the time required for the agent to execute the task, the agent's possible risk level, and their energy. Accordingly, the agent calculates numbers for each of the four decision-making criteria, such as variable X, based on Eq. (1). In Eq. (1), the distance (in meters), severity of the victims' injuries, and task priority are based on values declared by the central agent. Based on the rate of uncertainty presumed for a given environment (for example, 30 %), an interval for this number is estimated. The first number of this interval is in the range between [X, X+30 %X] and the second number is in the range [X−30 %X, X].

$$\begin{array}{rl}& \text{Agent energy (energy level, distance, number of people)}\\ & =\text{energy level}-\text{distance}/\mathrm{500}\\ & -\text{number of people rescued}\cdot \mathrm{0.3}\\ & \text{Task runtime by an agent (distance, number of people, severity)}\\ & =\text{distance}/\mathrm{150}+\text{number of people rescued}\cdot \mathrm{15}\\ & +\text{severity}\cdot \mathrm{2}\end{array}$$

$$\begin{array}{}\text{(1)}& \begin{array}{rl}& \text{Risk level for an agent (energy level, priority)}\\ & =\text{priority}-\text{energy level}\\ & \text{Route status (distance)}=\text{distance}\end{array}\end{array}$$

In the real world, each person can introduce intervals according to their experience and their knowledge of the environment. In this study, we used the above equations based on expert opinion to simulate the real environment. The coordinating agent applies the interval-based VIKOR method to order the agents' bids. The coordinating agent sends the results to the central agent after ordering the agents. The use of a central agent in this phase provides the opportunity to make the best decision considering the task priorities and capacities of other agents.

4.4 Applying allocation strategies

In operations where there is uncertainty, the issue of task allocation cannot be definitively resolved. In this phase, the initial allocation should be done in such a manner that a potential reallocation would waste the smallest amount of time. Based on different strategies at this stage, the central agent begins to assign tasks after obtaining all lists from coordinating agents. In each strategy, a priority is assigned to specific tasks. In this section, four different strategy-based approaches are described, as follows:

• Task allocation according to priority (strategy 1). In this strategy, task allocation begins with the assignment of higher priority tasks, following establishment of the task order and priorities of the rescue team in the previous stage (prioritization and auction). Therefore, the agent with the best performance is selected for high-priority tasks and is subsequently excluded from the lists of agents with no tasks. Subsequently, the tasks of lower priority are assigned in the same order. The limitation of this strategy is that it may cause some agents to not receive tasks.

• Assigning tasks to all agents, preferably to specific agents with optimal outcomes (strategy 2). This strategy is based on the optimal use of all rescue teams. In this strategy, all agents are assigned a task. For this purpose, a task is first assigned to an agent who has applied for the minimum number of tasks. The agent and task are then eliminated from the agent and task lists, and the allocation continues with the next agent who has made few requests. Using this strategy, a task will be assigned to all agents.

• Task allocation on a strategic spatial basis (strategy 3). Using this strategy, agents who play important and strategic roles in the task allocation process are excluded to ensure their availability for the implementation of tasks if problems are encountered during the task allocation process. Agents with strategic roles may be defined differently. Agents who participate in the auctions of more tasks are those with strategic locations. In such instances, these agents are close to many tasks (have strategic spatial locations) and can be used when these tasks are not implemented. Figure 3 shows the difference between the task allocation results for strategies 2 and 3. In Fig. 3, a rescue agent located centrally has a strategic position and will try to maintain this position. Although the total movement may increase, if there are problems in performing other tasks, this agent can help all other groups.

• Assigning tasks by creating the best density in the environment (strategy 4). This strategy is based on the optimal density of rescue agents. Using this strategy, task assignments are made in a manner that ensures the uniform distribution of agents in the environment. Generally, no exact information is available concerning the conditions of the tasks; therefore, this strategy aims to ensure a uniform distribution of rescue teams within the environment if the uncertainty is high. In disaster environments such as earthquakes, the incident occurs over a wide area, such that the damage and injured population are uniformly distributed due to the texture of the area. Therefore, the highest number of injured people is not accumulated in any one spot. Furthermore, applying this strategy prevents the convergence of rescue teams. To apply this strategy, the tasks of the highest priority in the task lists should be given to the available agents where the environmental density is the highest. The concept of optimal density can be solved through innovative algorithms. In our study, the simulated annealing method was used to determine uniform density. The implementation stages of simulated annealing have been described previously (Sabar et al., 2009). Figure 4 shows the difference between task allocation outcomes for strategy 2 and strategy 4.

Figure 3 Strategic agent illustration. Blue arrows show the final results for strategy 2, and red arrows show the successful rescuers in strategy 3.

Figure 4 Best density strategy illustration. Blue arrows indicate the successful rescuers in strategy 2, and red arrows indicate the final results for strategy 4.

4.4.1 Implementation and observation of real values in the environment

During the implementation phase, tasks are implemented by agents in a dynamic environment where there are always uncertainties during task execution. The rescuer observes the difference between predicted values and the actual environment after the work begins. In this study, a random number in the [X−30 %X, X+30 %X] interval was chosen to model the real environment. In the real world, the difference between the predicted environment (through building vulnerability estimation models) and the real environment will determine the agent's performance.

If the agent observes a large difference between the auction information and the real environment, the agent abandons that task. In this instance, the agent updates the task's values and uncertainties and returns the work to the central agent. The new uncertainty interval will be 80 % smaller than the original interval. There are various conditions under which agents will reallocate a task if the environment differs from the expected scenario. For example, the agent can abandon the task if three of eight decision-making parameters are out of range by 5%. Otherwise, the agent finishes the rescue work by accepting the new conditions. The central agent assigns newly added tasks within the reallocation framework. When a new task is assigned, the task allocation is combined with that of both new and incomplete tasks.

4.5 Evaluation method

Assessment of a task allocation algorithm is typically performed in the first phase through modeling and simulation due to the dynamic and heterogeneous nature of different environments (Olteanu et al., 2012). Simulation is a suitable approach for the implementation and validation of a proposed method (Nourjou et al., 2011). In a real test situation, the situations and conditions of the implementation scenario are difficult to reproduce. In the present study, we simulated three scenarios for earthquakes in Tehran's District 1 with magnitudes of 6.6, 6.9, and 7.2. We also estimated the numbers of deceased and injured individuals who are distributed in the centers of relevant building blocks and need to be rescued by 1000, 1500, or 2000 rescue agents. In the uncertainty analysis of the suggested method, the lower and upper bounds of uncertain values were also calculated. The proposed method was compared with the traditional CNP. The intended task allocation was considered efficient if profitability parameters were maximized. In accordance with several recent studies (Liu and Shell, 2012; Sang, 2013; Hooshangi and Alesheikh, 2017), three criteria were used to evaluate the performance of the proposed method: the number of deceased victims, number of incorrect allocations, and rescue time.

Some of the major problems in reallocation and in the task allocation environment include scalability, reliability, performance, and dynamic resource reallocation (Gokilavani et al., 2013). In this study, the results of two analyses (scalability of the proposed method and interval uncertainty analysis) are presented.

The first analysis focused on the evaluation of the proposed approach at different scales and for different criteria. Comparison and assessment were carried out at different scales to measure the effectiveness of the proposed approaches in USAR operations. Nine scenarios were applied in this study and compared with the traditional CNP.

The second analysis focused on interval uncertainty analysis and studied the rescue operation duration in the 6.9 magnitude earthquake at different levels of uncertainty. In this analysis, time changes in rescue operations were investigated according to different levels of uncertainties. The duration of a rescue operation in the simulation model depended on two main components: prioritization of tasks and outputs of each operation in each phase (Hooshangi and Alesheikh, 2018). Equation (2) defines the final model for calculating the operation duration based on these two components.

$$\begin{array}{}\text{(2)}& \begin{array}{rl}& T\left(x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},x_{\mathrm{4}},x_{\mathrm{5}},x_{\mathrm{6}},x_{\mathrm{7}},x_{\mathrm{8}}\right)=\\ & \sum _{n=\mathrm{1}}^{n+\mathrm{1}}{\mathit{\alpha }}_n\left(x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},x_{\mathrm{4}}\right)+\sum _{w=t}^{n+t}{\mathit{\beta }}_w\left(x_{\mathrm{5}},x_{\mathrm{6}},x_{\mathrm{7}},x_{\mathrm{8}}\right)\end{array}\end{array}$$

Variables x₁ to x₈ constitute the number of injuries, severity of injuries, duration of the operation, infrastructure priorities, energy, route status, task runtime by agents, and risk level for agents, respectively. α_n is the function of task prioritization, and β_w is the function of bidding.

To the best of our knowledge, interval uncertainty analysis has rarely been employed. The method used in this research was adapted from previous literature (Lan and Peng, 2016). In our analysis, Chebyshev points are used. Equation (3) depicts a Chebyshev formula for generating m collocation points in the interval [0, 1] (Lan and Peng, 2016):

$$\begin{array}{}\text{(3)}& {\mathrm{number}}_i=\left\{\begin{array}{ll}\mathrm{0.5}\times \left[\mathrm{1}-\cos \left(\frac{\mathit{\pi }(i-\mathrm{1})}{m-\mathrm{1}}\right)\right]& \mathrm{for}j=\mathrm{1},\\ & \mathrm{if}m=\mathrm{1}\\ \mathrm{0.5}& \mathrm{for}j=\mathrm{1},\\ & \mathrm{if}m=\mathrm{1}\end{array}\right\}.\end{array}$$

Equation (3) was used to create different numbers for the decision-making parameters. The output of the model was then calculated for various numbers within the intervals. This technique created different values for the output of the model.

5 Results and discussion

Multiple scenarios and experiments were designed to evaluate the proposed methods and strategies. The results are presented in this section. In accordance with expert opinion, three probable earthquakes were simulated with magnitudes of 6.6, 6.9, and 7.2. Figure 5 shows the vulnerabilities of buildings in these scenarios in the ArcGIS environment.

Figure 5 Vulnerability maps for District 1, based on earthquakes with magnitudes of (a) 6.6, (b) 6.9, and (c) 7.2 on the Richter scale.

Based on the level of building destruction, the numbers of injured and deceased people can be calculated using the JICA model. The numbers of injured and deceased people in scenarios with 6.6, 6.9, and 7.2 magnitude earthquakes are listed in Table 2.

Table 2 Results of earthquake simulations.

The computational scale of the JICA model uses urban blocks. Therefore, the numbers of deceased and injured individuals in each urban block were calculated. The locations of injured individuals were presumed to be in the centers of the respective blocks.

The environmental simulation and proposed method were implemented in AnyLogic software. This software can process geospatial information system data. To simplify the environment and reduce the calculation volume, each agent was regarded as a group in the real world. Figure 6 shows the simulated environment.

Figure 6 Overview of the USAR simulator.

There are many injuries in the environment. The central agent first sorts the tasks according to their priorities. After the coordinating agent has been determined, the central agent sends the task properties to the coordinating agent. The coordinator holds an auction. Rescue agents bid in accordance with their environmental and working conditions. Rescuers are in a ready state at the start of the operation. Each successful rescue agent moves to the task's location. After reaching the task position, the rescue agent begins rescuing the injured agents. During the execution of their assigned work, the agents may find considerable differences between the real-world information and the information expressed in the auction. In such instances, the agents may stop performing their tasks and report the discrepancies to the central agent.

Table 3 shows the durations of USAR operations as estimated using scalability analysis with the proposed method. In creating this table, an uncertainty of 30 % was considered. For this purpose, the range of task characteristics used the intervals [X, X+30 %X] and [X−30 %X, X]. At each stage, a given agent participated in the auction. For that agent's decision-making parameters, the numbers were randomly converted into an interval. The average range of agent tasks and decision-making was used for implementation of the CNP, rather than interval values.

Table 3 Comparison of operation duration in hours between the proposed method and the CNP (based on 30 % uncertainty).

The operational time decreased when the number of agents in rescue operations increased, with the number of tasks remaining fixed. The reduction rate ranged from 54 % to 60 % when the number of agents was doubled. The duration of a USAR operation increased when the number of tasks increased for a given number of agents. Therefore, the duration of the rescue operation was related to the number of rescue agents and the number of available tasks in a scenario. There was an inverse relationship between the duration of the USAR operation and the number of rescue agents and a direct relationship between the duration of the operation and the number of tasks.

The inclusion of uncertainty in any allocation strategy provided better results compared with the CNP method. Using the proposed strategies, the smallest improvement in results with uncertainty was 2.9 h (13 %) for a scenario with 2000 agents and 28 856 tasks (6.6 magnitude earthquake). The maximum improvement was 60.6 h (21 %) for 1000 agents and 111 463 tasks.

Figure 7 Numbers of deceased people with (a) 1000, (b) 1500, and (c) 2000 rescue agents.

Figure 8 Numbers of incorrect allocations with (a) 1000, (b) 1500, and (c) 2000 rescue agents.

Among the task allocation strategies in this study, strategy 1 produced the worst response. At each scale for the discussed scenarios, strategy 1 resulted in USAR operations with the longest durations compared with other strategies. Strategies 1 and 2 provided similar results at different scales, although strategy 2 achieved better results. Strategy 4, which involved spatial information in task allocation, produced better results at all scales, including improvements of 21 %, 24 %, and 23 % with 1000 agents for a 6.6 magnitude earthquake, 1500 agents for a 6.9 magnitude earthquake, and 2000 agents for a 7.2 magnitude earthquake, respectively, compared with the CNP. The average improvement for strategy 4 was 26.6 h in rescue operations. The use of strategies 3 and 4 is more suitable in a larger environment with high numbers of both injured people and rescue agents because controlling agent distribution with respect to expansion of the environment and the uncertain environmental conditions can be effective in future task allocations. In a real-world crisis-ridden environment, the overall environment is damaged, and the injured people are well distributed. Therefore, the spatial distribution of agents is an important parameter to control in USAR operations.

The simulation results in terms of deceased people for 1000, 1500, and 2000 agents with different numbers of tasks are shown in Fig. 7. In these figures, for each of the four priority parameters and decision parameters associated with agents, a 30 % uncertainty level was considered.

Figure 7 illustrates the numbers of deceased people in the rescue process with different numbers of agents and tasks. Based on Fig. 7, an increased number of tasks led to an increased number of deceased people, but an increased number of rescue agents led to a decreased number of deceased people. Regarding the numbers of deceased people at all three scales, the CNP method produced the worst response. An average of 7253 people were deceased in the CNP model with 1000 agents. Conversely, 5853 people were deceased in the model employing strategy 1 with 1000 agents. Overall, when all strategies were considered, strategies 4 and 1 resulted in the best and worst responses, respectively. As illustrated in Fig. 7, the numbers of deceased people were approximately equivalent in strategies 1 and 2.

Figure 8 illustrates the simulation results for the incorrect allocation of 1000, 1500, and 2000 agents with several different tasks.

The overall trend in each chart was approximately similar if all charts were considered simultaneously. Any incorrect allocation was unrelated to the number of rescue agents because there were no changes when the number of agents was increased. The number of incorrect allocations changed with the number of tasks, such that it increased with an increasing number of tasks. This increase is evident in all panels in Fig. 8. Incorrect allocations usually occurred at a nearly fixed rate.

Based on the results, the traditional CNP model produced the worst response. The total incorrect allocations in the CNP model with 1000 agents and 28 856 tasks, 1500 agents and 73 195 tasks, and 2000 agents and 111 463 tasks were 3780, 10 027, and 14 604 tasks, respectively. The numbers of incorrect allocations assigned by strategy 1 were 3174, 8014, and 12 455 tasks, respectively. Furthermore, the evaluation criteria showed the advantages of including uncertainty in task allocation. Therefore, the proposed approaches for all three evaluation parameters resulted in better performance compared with the traditional CNP method. The results indicate that the reallocation of tasks through the proposed approaches and strategies offered a better response, based on the scale of the event, because their differences from the CNP model increased at a larger scale.

The results of interval uncertainty analysis were achieved with 1000 randomized runs of each scenario (Fig. 9).

Figure 9 Uncertainty analysis of the proposed method for USAR operations, for nine simulated scenarios.

As shown in Fig. 9, there is a direct relationship between interval length and operational time. According to Eq. (2), assigning fewer tasks leads to less operating time and causes less uncertainty in the simulated environment.

As mentioned in Sect. 4.3.3, the rescuers use [X, X+30 %X] and [X−30 %X, X] to determine the intervals. Another analysis was performed for values other than 30 % in the estimations. The results are shown in Fig. 10. An average event scale (1500 agents and 73 195 tasks) was used, and different levels of uncertainty (uncertainty between 5 % and 55 % at five-unit intervals) were randomly generated, investigated, and evaluated. This realistic test aimed to assess the proposed scenarios for each uncertainty value.

Figure 10 Uncertainty analysis when different values were used in determining intervals.

Figure 10 indicates a relationship between increased in uncertainty (from 5 % to 55 %) and an increased rescue time. The increases differed among strategies. The increase was 67.7 h for the CNP (from 66.8 to 134.4 h), whereas increases of 63.4, 63.2, 61.7, and 56.5 h were obtained for strategies 1–4, respectively. Based on the evaluation results, the proposed methods are more efficient and present better responses in the presence of various uncertainties. Therefore, increased in uncertainty leads to a delay in USAR operations and possible task elimination. Accordingly, delaying rescue operations or removing tasks from the rescue list will increase USAR time.

6 Conclusion

Providing a suitable method for assigning tasks under uncertain conditions is important, according to the results of simulated USAR operations. This study presented a task allocation approach that aimed to better assign initial tasks, thus ensuring better conditions for potential reallocations of tasks and wasting the least time possible for rescue teams if problems were encountered during the initial allocations or a new task emerges. Some of the characteristics and advantages of the study include the focus on the necessity of task reallocation in disaster environments, the provision of an innovative approach for managing uncertainties that cause non-performance of tasks in the CNP method (the most widely used task allocation method in multi-agent systems), and the definition of spatial strategies for better task reallocation. The proposed approach can be used in combination with a wide range of algorithms for assigning tasks in accordance with the structure of the system.

The results obtained from simulations with the proposed approach revealed that the duration of rescue operations when the proposed strategies were implemented was always shorter than the time required using the CNP method. The worst improvement was identified for 2000 agents with 28 856 tasks (13 %) and the best for 1000 agents with 111 463 tasks (21 %). Furthermore, the results at different scales showed that the application of uncertainty in task allocation could improve the duration of USAR operations. There is a relationship between an increase in uncertainty and increased rescue operation duration. Furthermore, the results revealed a significant decrease in the numbers of deceased people and wrong allocations due to uncertainties, which demonstrated the importance of uncertainty inclusion in task allocation. The implemented method can be used for cooperation among agents. In an earthquake-stricken environment, rescuers can use assistant agents (devices such as mobile phones and tablets) to implement this methodology.

However, regarding comparisons of the proposed strategies, it is insufficient to consider only uncertainty in initial decision-making concerning task allocation because the working environment is quite dynamic, and the assigned tasks may encounter various problems. An effective assignment approach should consider both uncertainties in decision-making and strategies for reallocation to waste the least time during system disruptions. This optimizes planning to achieve better implementation time and allows for fault tolerance. The strategies for applying uncertainty during the implementation of task allocation improve the efficiency, performance, and stability of agent-based cooperation. Task allocation strategies lead to flexibility in decision-making and decrease the system's overall costs. Furthermore, spatial task allocation strategies can propose a specific arrangement of the rescue team within an environment to prevent time-wasting in the event of environmental uncertainties or task reallocation.

Additional research is recommended to provide new strategies and combine the proposed task allocation strategies of the present study with a coalition-forming method to select an appropriate coordinating agent in our proposed approach. Future studies should also consider other groups and other uncertainties within a range of dynamic simulations.