João V. Tomotani
Universidade de São Paulo; São Paulo, Brazil.
Email: t.jvitor (at) gmail (dot) com
TECHNOLOGY IN VIDEO GAMES
In video games, technology has always played an important part (as technological advancements, futuristic technology, lost technology…), often taking a major role in games: the titans in Titanfall, the portal gun in Portal, the metal gears in Metal Gear, and all sorts of armor, equipment and gadgets in Metroid, Crisis, Halo, Batman, Call of Duty etc. This is not a surprise, given that the public of such video games has always been highly connected with the latest technology. Also, while being futuristic and sometimes exaggerated, technological representations in games always try to remain close to real-world tech and science, in order to meet demands for “realism” in games.
In this context, robots (and other automated equipment) have also been widely featured in many games. These devices, though, always have military and war purposes. Besides all the games mentioned above, we have the laptop gun in Perfect Dark, JACK in Gears of War and all the machines in the Final Fantasies. When taking part in search operations, robots are used either for protecting something/-one/-where or for surveillance and repression: the UAVs (Unmanned Aerial Vehicles) in several shooters, the Monokumas in Danganroompa, the 1984-esquee tech from Freedom Wars etc.
This view of technology is pretty much one-sided, overshadowing their possible applications in more humanitarian scenarios, such as using UAVs in “Search & Rescue” (SAR) operations. Although shooting stuff is the core and fun of many games, I think it is worthwhile to explore the more “pacifist” side and to show gamers what this technology is really capable of. After all, the use of UAVs in SAR operations is already a reality.
HUMANITARIAN LOGISTICS IN DISASTER RELIEF OPERATIONS
Modern humanitarian logistics operations originated during the Nigerian civil war, in the conflict of Biafra, which unfolded after an attempted military coup in the 1960s. This conflict was the first in which large-scale humanitarian operations were conducted (Blecken, 2010). Since then, such operations started to be carried out systematically, and humanitarian organizations have often seen their objectives and principles collide with those of other interested parties. The principles of humanitarian operations (humanity, impartiality and neutrality) were established because of the necessity to position themselves between the two opposing sides of any conflict, and now serve as a guide for all humanitarian organizations (Blecken, 2010).
The basis of humanitarian operations is the belief that individuals affected by crises have the right to life and dignity, and thus are entitled to assistance. The Sphere Project (2011), where several organizations set minimum standards for humanitarian assistance, defines the right to life with dignity as: the right to live free of treatments and punishments that are cruel, inhuman or unworthy. As such, the central ideas of humanitarian operations are: the right to life when it is threatened and taking necessary measures to save lives and reduce suffering.
Humanitarian Logistics is a relatively new academic field, but the number of contributions in the area have increased steadily in recent years (see Leiras et al., 2014, for a thorough review).
Wassenhove (2006) defines a disaster as a “break”, something that physically affects a system, threatening its priorities and objectives. Disasters can be classified either as natural or “man-made”. Likewise, they can be classified as having a sudden or slow onset. Examples of natural disasters with sudden onsets are earthquakes and hurricanes, while examples of natural disasters with slow onsets are hunger and drought. Examples of man-made disasters with sudden onsets are coups and terrorist attacks, while slow onset man-made disasters are political crises and refugee crises (Wassenhove, 2006).
Traditionally, four stages are defined in Operations Management in disaster scenarios: mitigation, preparedness, response and recovery (Wassenhove, 2006; Tomasini & Wassenhove, 2009). SAR operations are those conducted in the response phase, aiming to find and provide relief to the greatest number of people in the hours after the disaster, trying to maximize the survival chance of victims (Hoyos et al., 2015). Tsunemi et al. (2015) emphasize the importance of agility in such operations, as statistical studies show that the rate of survival of, for instance, trapped victims in collapsed buildings, plummets within 72 hours of the moment of disaster.
UAVs are able to act autonomously in dynamic and complex environments and thus, are used predominantly for military purposes, such as intelligence gathering, surveillance and reconnaissance (Gupta et al., 2013). This is, of course, what is reflected in video games. However, there has been increasing interest in using UAVs for SAR operations, since they are able to quickly reach areas of difficult access and to quickly build a network of information and communication among the affected areas (OCHA, 2014; Meier, 2015). This is particularly relevant given that the travel speed within a region affected by disasters such as floods or earthquakes tend to be greatly reduced (Yuan & Wang, 2009).
SAR operations have particular difficulties, such as the uncertainty of the time required to inspect different regions and the uncertainty of the number, amount and location of victims. Thus, traditional methods of routing and scheduling may be insufficient to define the best way of working with UAVs. The present study is divided in three parts: (a) a brief review of the literature on the use of UAVs for SAR operations; (b) an evaluation of how different heuristics (in particular the “sweep method” of Ballou, 2006) stack up against the uncertainties of said operations; and (c) the proposal of improvements in heuristics to adapt them to the specificities of SAR.
Heuristic: Sometimes, an exact (or “optimized”) solution to a problem cannot be mathematically guaranteed or would take too much time and resources to be calculated. Many times, though, an approximate solution is acceptable for such problems. A procedure that can produce a practical, though not perfect solution, is a heuristic (Henderson, 2009).
UAVs IN SEARCH & RESCUE OPERATIONS
Tsunemi et al. (2015) classify rescue operations in three types: (1) search operations in a wide area, conducted immediately after the disaster to assess its scale and impacts; (2) search operations in a narrow area, for obtaining more specific information of affected sites discovered by the type-1 search; and (3) pinpoint search operations, which physically access the sites from type-2 search to locate/rescue victims. Constant communication between the search teams and the HQ, as well as using real-time information to update them, is clearly necessary in all three search types (Huang et al., 2013).
Irrespectively of the types above, works usually distinguish between two kinds of SAR operations, according to the area in which they take place: urban and non-urban (or wild). SAR operations in wild areas are searches for people lost in deserts, mountains or any other sparsely populated natural environment. Most works dealing with SAR operations (particularly those that involve UAVs) are interested in these environments (e.g., Goodrich et al., 2007; Cooper & Goodrich, 2008; Lin & Goodrich, 2009; Lin et al., 2010; Morse et al., 2010; Molina et al., 2012; Karma et al., 2015). For SAR operations in urban areas, there are additional challenges, such as searching through debris and clearing roads (Chen & Miller-Hooks, 2012). However, not many works focus on urban settings (e.g., Jotshi et al., 2009; Ko et al., 2009; Chen & Miller-Hooks, 2012; Huang et al., 2013).
Chen & Miller-Hooks (2012) point that, although there is an extensive literature that addresses the management of emergencies, few studies propose optimization techniques for SAR operations: Jotshi & Batta (2008) present a search heuristic that minimizes the time to find a single stationary entity on a given area; Jotshi et al. (2009) bring solutions for dispatching and routing emergency vehicles in urban settings when roads have been compromised; and finally Chen & Miller-Hooks (2012) themselves propose a multistage stochastic programming algorithm for urban settings, increasing the efficiency of the operations and highlighting the importance of communication between the search teams.
Stochastic programming (or optimization) is a framework that allows the modeling of uncertainty in the input data, in contrast to deterministic optimization, which does not. In some complex cases, the inherent uncertainty of data, coupled with the evolution of such data over time, leads to a sequential optimization-under-uncertainty model (Casey & Sen, 2005), where data is input through a series of stages. Such problems are called multi-stage stochastic programming.
As for the use of UAVs in SAR operations, several works have already tackled different problems, ranging from building communication networks to improving images obtained by the UAVs’ sensors (e.g., image recognition and infrared). In a UAV-based SAR operation, there are four critical personnel roles (Goodrich et al., 2007; Cooper & Goodrich, 2008): (1) the commander responsible for managing the search; (2) the UAV operator; (3) the UAV’s sensor operator (it’s better to have a different person than the UAV operator for this); (4) the ground search team.
Ko & Lau (2009) built and tested an autonomous UAV for urban environments, which could circumnavigate debris and search for the heat signatures of survivors. Despite this line of research being still on its infancy (Lin et al., 2010), their focus have already changed a little. As a consequence of recent technological advances (mainly in electromechanical systems, communication technology and control theory), many proposals now focus on multiple cooperative robots, known as “swarms”. Swarms have many benefits over regular UAVs, such as: robustness against failures (other robots can continue the search if one has problems), increased flexibility in reorganizing as the mission progresses, and economies of scale (Çayurpunar et al., 2008; Waharte et al., 2009).
Regardless of UAV type, the way the search is in fact conducted is the crucial point and it depends on the algorithms used. Lin & Goodrich (2009) proposed and algorithm that considers the priority of the search regions (those most likely to have survivors), in order to define the search routes for the UAVs. Murtaza et al. (2013) proposed a similar algorithm, but using a partially observable Markov decision process method.
A very interesting (and geeky) work was conducted by Megalingam et al. (2012). They proposed the design of a rescue robot with a human-like upper-body that is controlled through gesture-based imitations, acquired through the Microsoft Kinect, a motion sensing input device developed originally for the Xbox 360 video game consoles (and later for Windows PCs and the Xbox One).
Would it look something like this maybe? (Nintendo’s R.O.B.; image by Evan-Amos, 2012, taken from Wikimedia Commons).
Waharte & Trigone (2010) tested three types of algorithms (greedy heuristic, heuristic based on attraction/repulsion potentials, and heuristic based on partially observable Markovian decision process) through simulations, and found that estimating the best search paths through the sharing of information between UAVs reduced the duration of the operations, albeit at a high computational cost. They also concluded that there are several important aspects to be met, such as the quality of the sensors, energy constraints, environmental hazards and communication restrictions between UAVs. Regarding the latter, Asadpour et al. (2012) point out that the communication capability of conventional UAVs is insufficient for the large volume of data required for SAR operations, such as images and videos. They thus proposed hybrid networks made with smartphones and ground stations. Environmental dangers are also quite problematic, as shown by the work of Karma et al. (2015), since they may incur on reduced visibility (thus making detection difficult) or severe damage to the usually fragile UAVs.
A Markov decision process is a model for sequential decision making when under uncertainty, in situations where outcomes are partly random and partly under control of the decision maker (or agent), considering both short-term outcomes of current decisions and opportunities for making decisions in the future. The partially observable Markov decision process is a generalization of the Markov decision process, and considers that the decision maker cannot directly observe the state of the system. Since the true state is hidden, the agent must choose actions based on past actions and observations, composing scenarios of possible state distributions (called belief states).
FORMULATION OF THE PROBLEM
As I mentioned above, here I intend to evaluate how different heuristics (in particular the “sweep method” of Ballou, 2006) stack up against the uncertainties of SAR operations, also proposing improvements for them. Therefore, I need to insert some of the difficulties present in real-life SAR operations. Thus, the problem formulated has the following characteristics:
- The maps where the search occurs are generated randomly, with random x and y coordinates being assigned to a defined number of regions (search sites). The maps can have 50, 100 or 500 regions. For the present study, it was decided that the coordinates may vary from (-3) to (+3), and the travel time between two regions is equal to the distance between them in the stipulated coordinated plane.
- A command base for the SAR operation is defined on the map at a random position. The base is the starting point of the UAVs’ routes. For this study, it was decided that the basis of the coordinates could range from (-1.5) to (+1.5). An example of a map, with the search regions, can be seen on Figure 1. The application for the map generation was developed in VBA, and its interface can be seen on Figure 2.
Figure 1. Example of a search map with 50 search locations (blue dots) and the command base (red diamond). The travel time between two points is directly proportional to the distance between them.
Figure 2. Interface of the map generator.
- The search is conducted by five UAVs. A maximum flight range is set for each vehicle, after which it must return to the base before leaving again (immediately) on the next route. It was decided that the flight range for all UAVs is (30).
- Each search location has a known “search complexity”, randomly assigned. Places with greater complexity require larger times to complete the search. In this study, it was decided that the complexity (search time) could be (1), (2), (3) or (4), with respective probabilities of being assigned (40%), (30%), (20%) or (10%).
- Each search location has a known probability of containing a victim, randomly assigned. The total number of victims is unknown. In the present study, it was defined that the likelihood of a location having a victim could be (10%), (30%), (60%) or (90%), with chances of (30%), (20%), (20%) or (30%), respectively.
- For testing the various heuristics, four instances were generated for each map scale (50, 100 and 500 search regions).
HEURISTICS TO SOLVE THE PROBLEM
For solving the proposed scenarios, two heuristics were developed, prioritizing areas where victims are most likely to be found (similar to the works of Lin & Goodrich, 2009, and Murtaza et al., 2013). After the initial results, a third hybrid heuristic was proposed. The interface developed in VBA, for the simulation of the heuristics can be seen on Figure 3.
Figure 3. Simulator interface.
“Greedy” Heuristic
The first heuristic proposed is the “greedy”, which takes into account the distance to the search areas, the complexity of the search operation and the probability of finding a victim, to compose a prioritization factor. Each UAV calculates the factor for all regions that have not yet been searched, and goes towards the region with the highest factor. The greedy heuristic is said to be “myopic”, because it does not have long-term vision. Three different factors were tested to evaluate how the “distance” and “probability of victim” parameters affected the quality of the solution: one that considers only the shortest time to come and inspect the regions (1/T); one that considers the shortest time and the square of the probability of finding a victim (1/T*P2); and one that takes the shortest time, and the fifth power of the probability of finding a victim of (1/T*P5).
“Sweep” Heuristic
The “sweep” heuristic is a simple and known vehicle routing algorithm, capable of solving a variety of problems rapidly and with relatively small average error rate (around 10%; Ballou, 2006). In this method, a line is drawn from the point of origin, and this line rotates on a defined direction. Search locations through which the line passes are the ones which will compose a route, the rotation stops when the length of the route equals the flight range of the UAV. Finally, prioritization logic is applied for all locations that compose this route, in order to define the route sequence. Because of this two-stage process, Ballou (2006) points out possible problems in the formation of routes, such as the non-compliance of flight range restriction.
In the present problem, prioritization logic applied in the second stage was the likelihood of a location having victims, with locations of greater probability being visited first. It should be noted that the “sweep” method implemented has a major constraint for the proposed problem, because the routes are generated complete one at a time, and assigned to a UAV, so that the last search sites tend to be visited by a single vehicle (for being part of the same route), and thus allowing for idle vehicles (those that have completed their own routes). This restriction is most noticeable for problems with few locations.
Hybrid Heuristic
After the first tests of the algorithms, it was found that the “greedy” heuristic quickly finds the first victims, but are slow to find all of them. Meanwhile the “sweep” method quickly finds all the victims, but is not so effective in the first moments of the SAR operation, which are the most critical. Because of this, a hybrid method was implemented, where the first routes are generated by “greedy” heuristics and the later routes are generated by the “sweep” method. For this problem, in scenarios with 50, 100 and 500 search sites, a greedy heuristic is used until time instances of 10, 30 and 90 respectively.
RESULTS AND DISCUSSION
The simulation results can be seen on Tables 1 to 3, showing the average time needed to find the indicated percentage of survivors.
Table 1. Results of the simulation for the different algorithms (with 50 search locations), showing the average time needed to finish.
Table 2. Results of the simulation for the different algorithms (with 100 search locations), showing the average time needed to finish.
Table 3. Results of the simulation for the different algorithms (with 500 search locations), showing the average time needed to finish.
The “greedy” heuristics that prioritize the probability of finding survivors had good results for the early stages of the operation, while the “sweep” method is more efficient in finding all survivors in the shortest possible time. This becomes more evident with the routes generated by each method (Fig. 4., the “sweep” method creates more efficient routes). Hybrid algorithms, in turn, use the “greedy” strategy for finding many survivors in the early moments of the search, switching to the “sweep” strategy later on in order to find all the victims faster. Figure 5 shows an example of comparative results for a specific scenario.
Figure 4. Example of routes generated by different algorithms for a scenario with 50 locations.
Figure 5. Example of the results of the different algorithms for a scenario with 500 locations. The “greedy” 1/T*P2 and 1/T*P5 had the same result, so only the latter is shown.
CONCLUSION
SAR is an essential part of humanitarian operations, and the use of UAVs for this purpose is already a reality. Still, few studies have focused on search algorithms for using UAVs and even fewer have considered the complexity and uncertainty of real-life problems. This work is a first attempt to tackle this problem.
The results provided by the simulations of the hybrid model were very promising, and the balance between “greedy” and “sweep” heuristics appear to be a good solution to meet conflicting objectives. The time spent for each algorithm during a hybrid approach can be calibrated according to the characteristics of the explored area. However, the model has a large number of complex parameters, being difficult to calibrate. A next step would be to test such model in real-life scenarios to assess the sensitivity of such parameters.
Perhaps the most obvious constraint on the proposed solutions is the lack of communication between UAVs. A more intelligent system of communication between different vehicles allows a more coordinated search (Çayurpurnar et al., 2008) and would probably show even better results, particularly in scenarios with many search sites. An idea would be to develop an UAV control simulator, where the “players” could communicate or not with each other, and the differences in performance could be analyzed systematically.
Another constraint presented in the work is the binary nature of the presence of victims on search sites. One possible improvement would be the use of Poisson distributions to set the number of victims for each location, which would affect the dynamics of prioritization factors, making the model more complex and closer to real-life scenarios.
Finally, we must remember that almost no video games include such a humanistic view on technology as SAR operations (unless it is for rescuing the main hero, of course). Although agreeing that combat, war, conflicts and violence are an important (and fun!) part of games, it is also nice to remember the positive impact brought by technological advancements, and that such education through games is always possible.
ACKNOWLEDGEMENTS
I am grateful for the suggestions from Dr. Adriana Leiras, Dr. Irineu de Brito Jr. and João Gilberto Sanzovo (USP), which greatly improved the text.
REFERENCES
Asadpour, M.; Giustiniano, D.; Hummel, K.A.; Egli, S. (2012) UAV networks in rescue missions. Proceedings of the 8th ACM International Workshop on Wireless Network Testbeds, Experimental Evaluation & Characterization: 91–92.
Ballou, R. H. (2006) Gerenciamento da cadeia de suprimentos / logística empresarial. Bookman, Porto Alegre.
Blecken, A. (2010) Humanitarian Logistics: Modelling Supply Chain Process of Humanitarian Organizations. Haupt Verlag AG, Berna.
Casey, M.S. & Sen, S. (2005) The scenario generation algorithm for multistage stochastic linear programming. Mathematics of Operations Research 30(3): 615–631.
Çayirpunar, O.; Tavli, B.; Gazi, V. (2008) Dynamic Robot Networks for Search and Rescue Operations. Proceedings of the EURON/IARP International Workshop on Robotics for Risky Interventions and Surveillance of the Environment: 1–9.
Chen, L. & Miller-Hooks, E. (2012) Optimal team deployment in urban search and rescue. Transportation Research, Part B, 46: 984– 999.
Cooper, J. & Goodrich, M. (2008) Towards combining UAV and sensor operator roles in UAV-enabled visual search. Proceedings of the 3rd ACM/IEEE International Conference on Human Robot Interaction: 351–358.
Goodrich, M.A.; Cooper, J.L.; Adams, J.A.; Humphrey, C.; Zeeman, R.; Buss, B.G. (2007) Using a Mini-UAV to Support Wilderness Search and Rescue: Practices for Human-Robot Teaming. Proceedings of the IEEE International Conference on Safety, Security and Rescue Robotics: 1–6.
Gupta, S.G.; Ghonge, M.M.; Jawandhiya, P.M. (2013) Review of Unmanned Aircraft System (UAS). International Journal of Advanced Research in Computer Engineering & Technology 2(4): 1646–1658.
Henderson, H. (2009) Encyclopedia of Computer Science and Technology, Revised Edition. Facts on File, New York.
Hoyos, M.C.; Morales, R.S.; Akhavan-Tabatabaei, R. (2015) OR models with stochastic components in disaster operations management: a literature survey. Computers & Industrial Engineering 82): 183–197.
Huang, A.; Ma, A.; Schmidt, S.; Xu, N.; Zhang, B.; Meineke, L.; Shi, Z,; Chan, J.; Dolinskaya, I. (2013) Integration of Real Time Data in Urban Search and Rescue. Northwestern University. Available from: http://www.ccitt.northwestern.edu/documents/Integration_of_real_time_data_in_urban _search_ and_rescue.pdf (Date of access: 16/Dec/2015).
Jotshi, A. & Batta, R. (2008) Search for an immobile entity on a network. European Journal of Operational Research 191(2): 347–359.
Jotshi, A.; Gong, Q.; Batta, R. (2009) Dispatching and routing of emergency vehicles in disaster mitigation using data fusion. Socio-Economic Planning Sciences 43(1): 1–24.
Karma, S.; Zorba, E.; Pallis, G. C.; Statheropoulos, G.; Balta, I.; Mikedi, K.; Vamvakari, J.; Pappa, A.; Chalaris, M.; Xanthopoulos, G.; Statheropoulos, M. (2015) Use of unmanned vehicles in search and rescue operations in forest fires: Advantages and limitations observed in a field trial. International Journal of Disaster Risk Reduction 13: 307–312.
Ko, A.W.Y. & Lau H.Y.K. (2009) Intelligent robot-assisted humanitarian search and rescue system. International Journal of Advanced Robot Systems 6(2): 121–128.
Leiras, A.; Brito, I. Jr.; Peres, E.Q.; Bertazzo T.R.; Yoshizaki H.T.Y. (2012) Literature review of humanitarian logistics research: trends and challenges. Journal of Humanitarian Logistics and Supply Chain Management 4(1): 95–130.
Lin, L. & Goodrich, M.A. (2009) UAV intelligent path planning for wilderness search and rescue. International Conference on Intelligent Robots and Systems: 709–741.
Lin, L.; Roscheck, M.; Goodrich, M.A.; Morse, B.S. (2010) Supporting wilderness search and rescue with integrated intelligence: autonomy and information at the right time and the right place. Proceedings of the 24th AAAI Conference on Artificial Intelligence: 1542–1547.
Megalingam, R.K. & Mahadevan, A.P.K.A. (2012) Kinect based humanoid for rescue operations in disaster hit areas. International Journal of Applied Engineering Research 7(11): 1–5.
Meier, P. (2015) UAVs and humanitarian response. In: New America (Ed) Drones and aerial observation: New Technologies for Property Rights, Human Rights and Global Development. A Prime, Washington, D.C.
Molina, P.; Colomina, I.; Vitoria, T.; Silva, P.F.; Skaloud, J.; Kornus, W.; Prades, R.; Aguilera C. (2012) Searching lost people with uavs: the system and results of the close-search project. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 39-B1: 441–446.
Morse B.; Engh, C.; Goodrich, M. (2010) UAV video coverage quality maps and prioritized indexing for wilderness search and rescue. 5th ACM/IEEE International Conference on Human-Robot Interaction: 227–234.
Murtaza, G.; Kanhere, S.; Jha, S. (2013) Priority-based coverage path planning for Aerial Wireless Sensor Networks. Proceedings of the 2013 IEEE 8th International Conference on Intelligent Sensors, Sensor Networks and Information Processing: 219–224.
OCHA. (2014) Unmanned Aerial Vehicles in Humanitarian Response. OCHA Policy and Study Series 10: 1–15.
Sphere Project. (2011) The Sphere Project: Humanitarian Charter and Minimum Standards in Humanitarian Response. Practical Action Publishing, UK.
Tomasini, R.; Wassenhove, L.V. (2009) Humanitarian Logistics. Palgrave Macmillan, London.
Tsunemi, Y.; Ishii, T.; Murata, M. (2015) Imaging solutions for Search & Rescue Operations. NEC Technical Journal 9(1): 90–93.
Waharte S. & Trigoni, N. (2010) Supporting search and rescue operations with UAVs. International Conference on Emerging Security Technologies: 142–147.
Waharte S.; Trigoni, N.; Julier, S.J. (2009) Coordinated search with a swarm of UAVs. SECON.
Wassenhove, L.N.V. (2006) Humanitarian aid logistics: supply chain management in high gear. Journal of Operational Research Society 57(5): 475–489.
Yuan, Y. & Wang, D. (2009) Path selection model and algorithm for emergency logistics management. Computers & Industrial Engineering 56(3): 1081–1094.
Journal of Geek Studies 