Intelligent Transportation System to Facilitate Disaster Response Management: Using AI and Game Theory Models
Dr. Shruti Mantri
Email: shruti_mantri@isb.edu
ISB Institute of Data Science
I. Introduction
A deep monsoon depression over the west central Bay of Bengal, weekend over Telangana in mid-October 2020 resulted in heavy downpours over several districts in the State of Telangana, severely affecting the city of Hyderabad. Heavy downpour resulted in waterlogging, sand bars on roads, potholes etc., thereby disrupting the traffic at many places in the city of Hyderabad, even the flyovers could not avoid traffic disruption resulting in delay in response activity of Disaster Management Team reaching the disaster site.
Transportation network is an important component of people’s everyday life facilitating movement from one destination to another. In an urban metropolitan region, the road infrastructure includes the roads, flyovers, bridges, and signalized intersection. The number of vehicles registered in metropolitan cities like Greater Mumbai, Hyderabad etc. are growing at 4–5 percent per annum. The traffic density during peak hours in some areas of the city is so high that the average speed reduces to as low as 6 to 8 km per hour, especially in the areas of congested areas like Gachibowli, Charminar, Hi-Tech City etc. This scenario can be applicable to any metropolitan city. The factors affecting the urban transportation network are:
(i) The existing arterials linking from one place to another place are proving to be inadequate for the increasing traffic volumes,
(ii) Poor riding surfaces of internal roads, especially post monsoons result in traffic jams, and
(iii) Traffic bottlenecks and choking intersections results in slow traffic.
The transportation network in any day is made up of pedestrians and vehicles moving from origin to destination to complete a path or a trip. But in a dynamic environment the moving vehicles come across multiple different types of obstacles such as road diggings ,construction works, bridge construction works, water logging on the roads, road accidents, fire, heavy rains, pedestrian movement at the time of processions, public vehicles, break down in vehicles, vehicles parked along the road side in an undisciplined manner, narrow roads and lanes which are generally not detected in navigation systems resulting in traffic jam. Besides it, in commuting from one city to another; even landslides along the mountains, heavy vehicles and tankers, foggy atmosphere, can also restrict the traffic thereby causing traffic congestion and increasing the time taken by the vehicles in reaching their destination site.
II. Need of Handling Transportation Network for Disastrous Situations
Whenever there are normal situations the road traffic authorities try their level best to handle and resolve the transportation network related problems to the best of their capacities. The bridges, highways and freeways have resolved the problem of traffic jams to certain extent. But whenever there is a disastrous situation whatever care has been taken proves to be inadequate. Reaching the desired destination in the fastest manner using shortest possible path is the need of the hour during an emergency. The selection of the optimal shortest route to the disaster site, hospital or shelter is very important at that moment. This is achieved if the emergency vehicles reach to the disaster site within no time following the best possible route. The emergency services may have to do multiple return trips to the disaster site. Thus, there is a need to devise a plan to compute optimal path that not only consider the distance travelled, but also the number of deviations and number of re-planning required. It was observed that, during these disastrous situations there is an inappropriate handling of transportation network and traffic handling mechanism proved to be inadequate For example, Let V1 be vehicle travelling from node R1 to node R8 (Figure 1.1) . There are following possible paths available for V1: (i) R1-R3-R4-R7-R8 (ii) R1-R3-R4-R5-R6-R7-R8 (Figure 1.1)
The ideal shortest path mathematical algorithm for V1 to travel from node R1 to node R8 is R1-R3-R4-R7-R8 as it takes less time. But if there are four vehicles V1, V2, V3 and V4 travelling from R1 to R8 then all the vehicles taking the route R1-R3-R4-R7-R8 leads to congestion for the emergency vehicle E1 travelling from R1 to R8 (Figure 1.2). The ideal route for the emergency vehicle to traverse is R1-R3-R4-R5-R6-R7-R8 (Figure 1.2) thereby avoiding the traffic congestion and reaching the destination as fast as possible.
Best Route means the optimal geometrical path to be identified among different alternate paths available in different situations which takes minimal time. Realizing the dependence of society on transportation whether it is normal or disastrous situation; it is important to assess transportation system vulnerability points to manage risk and reduce disruption. These disruptions decrease serviceability of transportation network or even paralyze certain portions. For this purpose, in the current study, the authors have designed and developed an Intelligent Central Transportation System having extended capabilities that computes optimized shortest path for every vehicle on the path, including the emergency vehicle during disastrous situation.
The formulation of proposed Intelligent Central Transportation System includes:
(i) Visualizing the transportation network as large-scale complex — virtual environment,
(ii) Solving the path planning problems for the vehicles using the computational geometric methods,
(iii) Presenting the transportation network as Multi — Agent System, and
(iv) Designing a Spatial Database System which stores the various information elements of this transportation network and helps verifying the strategies and algorithms used for solving the path planning problems.
III. Application of Game Theory to Artificial Intelligence
Game Theory is a branch of mathematics used to model the strategic interaction between different players in a context with predefined rules and outcomes. Game Theory can be applied in different areas of Artificial Intelligence such as: (i) Multi-agent AI systems (ii) Imitation and Reinforcement Learning (iii) Training in Generative Adversarial Networks (GANs). Classification algorithm such as SVM(Support Vector Machines) in terms of game theory can be explained as two-player game in which one player is challenging the other to find the best hyper-plane giving him the most difficult points to classify. The game will then converge to a solution which will be a trade-off between the strategic abilities of the two players.
IV. Formulation of Transportation Network as a Large-Scale Complex — Virtual Environment
An agent is any entity that can perceive in the environment through its actuators (Russell & Norvig, 2003). A system that consists of a group of agents that can potentially interact with each other in an environment is called a Multi-Agent Systems (MAS). Multi-Agent System has the following are the characteristics:
1. Agent Design
Agents can be homogenous and heterogeneous. Homogenous agents are designed in an identical way and have a similar behavior. Agents that implement different behavior are called as heterogeneous. Agent heterogeneity can affect all functional aspects of an agent from perception to decision making, while in single-agent systems the issue is simply nonexistent. Transportation network is made up of static vehicles, moving vehicles, traffic central authority, moving pedestrian. Each of them exhibiting different type of behavior.
2. Environment
Agents deal with environment that is static or dynamic. In a Multi-Agent System, the presence of multiple agents makes the environment dynamic from the point of view of each agent. An agent needs to decide which part of the environment it needs to treat as other agent. For example: in a transportation network, the vehicle driver acts as an agent and other moving vehicles and pedestrian, buildings in narrow lanes, water logging acts as obstacles for that vehicle driver.
3. Perception
Every agent perceives data from the environment that may differ spatially, temporally, or even semantically. The decision making of every agent is a based on the data received. An agent can also optimally combine their perceptions to increase their collective knowledge about the current state for effective decision making.
4. Control
Control in a Multi-Agent System is decentralized. The decision making of each agent lies to a large extent within the agent itself. In a transportation network, based on the data perceived from the environment, the traffic central authority intelligent system needs to compute the optimized path for each agent but whether to follow the path or not is the decision of the vehicle driver.
5. Knowledge
In a Multi-Agent System, each agent may know the available actions set of other agents, both agents may know their current perceptions, or they can infer the intentions of each other based on some shared prior knowledge. On the other hand, an agent may be unaware of other agent’s actions set and their current perceptions and might be unable to infer their plans. In a transportation system, every vehicle driver depends upon his knowledge about the other vehicle drivers’ actions set.
6. Communication
In a Multi-Agent System, communication is a two-way process where all agents send and receive messages.
V. Mathematical Building Blocks for Intelligent Transportation System
Mathematically, all the entities of a transportation network except roads are called as “objects”. Vehicle drivers from artificial intelligence perspective, for which an optimal path needs to be computed, is called as an “agent” in the environment as described above. For any “agent”; surrounding environment consisting of objects and even the other vehicle agents on the roads present on the path are called as “obstacles”. To model the individual behavior of the agents and obstacles in the large — scale dynamic virtual environment; an agent based — technique is used (Sud et al., 2007). The agent — based technique is basically a computational geometry method where we use global data structures: Voronoi Regions, Diagrams and Graphs and Multi-Agent Navigation Graphs (Sud et al., 2007).
Voronoi Diagrams and Regions
Voronoi diagram is the partitioning of a plane with n points into convex polygons such that each polygon contains exactly one generating point and every point in each polygon is closer to its generating point than to any other. In the current study, the intelligent system computes 1st order Voronoi diagram and 2nd order Voronoi diagram to detect the obstacles and compute the navigation graph.
Multi-Agent Navigation Graph
One of the key challenges in transportation network is the global path planning for each agent. The path planning problem is very challenging for real-time applications with a large group of moving agents as each agent is a dynamic obstacle for other agents. Many prior techniques are either restricted to static environment or perform local collision avoidance computations.
Voronoi diagrams so far have been widely used for path planning in static environment (Sud et al., 2007) and we have extended the approach to dynamic environment. Voronoi diagram encode connectivity of space and provide a path of maximal clearance to an agent from other obstacles. Computing Voronoi diagram for each moving agent and obstacles can be costly. Instead computing the second order Voronoi diagram of all obstacles and agents and showing the pair-wise proximity information for all agents simultaneously is feasible. Therefore, we compute the Multi Agent Navigation Graph using first and second order Voronoi diagram for global path planning (Sud et al., 2007). The Multi-Agent Navigation Graph is a data structure computed for parallel computation of maximal clearance path for multiple virtual agents moving independently (Sud et al., 2007).
VI. Presentation of Transportation Network as Multi — Agent System: Game Theoretic Spatial Temporal Model
The steady increase of traffic demand in past decade has led to high rate of congestion on urban roads. Transportation network consists of vehicle, each heading towards its predefined destination. Each vehicle driver behaves selfishly to achieve his/her own objective there by resulting in obstruction of the path and the delay in reaching to the desired destination like a system composed of autonomous Multi-Agents. Multi-Agent system is a system composed of multiple autonomous agents that cooperate with each other to reach common objectives, while simultaneously pursuing individual objectives. The vehicle drivers are characterized as autonomous entities by the following aspects (Yu, 2004):
(i) Autonomy: Every vehicle driver is moving independent of other vehicle driver’s moving state and can exercise their own control over their actions.
(ii) Reactivity: They can perceive their environment and respond in a timely manner to the changes that occur in a dynamic environment.
(iii) Pro-activeness: The actions are initiated by themselves and their behaviors are goal directed.
(iv) Responsiveness: They can communicate and understand signals from other drivers and traffic authorities.
(v) Mobility: They have ability to transport themselves from one place to another
(vi) Rationality: The vehicle drivers maximize their utilities to achieve their goals
(vii) Embodied: They traverse along the entire transportation network
Intelligent traffic control system is a set of traffic strategies which are to be used to regulate the traffic flow in urban areas. Traffic control system have two parties involved namely vehicle road user (vehicle drivers on roads) who are supposed to travel according to his or her judgment of the traffic and the traffic control authority who are responsible for regulating the traffic. The drivers as autonomous entities display characteristics features of agents. Thus, the drivers be agents interacting with each other in a transportation network. While traversing its path each vehicle driver (agent) non-cooperatively seeks to minimize his/her cost of transportation time spent in the network. In most of the cases, the vehicle driver behaves selfishly by choosing the paths of minimum latency under the perceived traffic conditions. This independent and non-cooperative behavior of drivers evokes game theory and its main concepts of rational behavior.
Game Theory provides means/ways for analyzing situations and predicting what might happen when agents with conflicting interests interact. A game is made up of three basic components: a set of players, a set of actions and set of preferences. The players are the decision makers in the modeled scenario. The internal strategies and mathematical foundations of game theory provides a strong foundation for modeling and designing an automated interactive decision-making environment. To model different environments/scenarios of transportation network, the focus lies on: (i) Cooperative (ii) Non-Cooperative game.
A cooperative game is a high-level description of the situation, specifying only what payoffs each potential group can obtain by the coalition strategies. Cooperative game theory investigates such coalitional games with respect to the controlling strategy held by individual player, or how successful coalition gives the desired outcomes.
The non-cooperative game theory is concerned with the analysis of strategic choices. In a non-cooperative game theory, the details of player’s actions and timings of player’s choices are crucial to determine the outcome of a game.
In a transportation network, the players are either the vehicle drivers and/or the traffic authorities. The actions are the alternate paths available to each player. In dynamic environment, the set of actions might change over time. When each player chooses an action, the resulting “Action Profile” determines the outcome of the game. Preference relationship for each player represents that player’s evaluation of all possible outcomes. In many cases, preference relationship is represented by a utility function, which assigns the number of possible outcomes with higher utilities representing more desired outcomes. In a transportation network, the vehicle driver prefers paths with less traffic congestion and latency. When roadways are shared, vehicle drivers as Multi-Agents, are engaged in a game, where each attempt to reach to his/her destination as quickly as possible without getting in a traffic jam or coming across an obstacle. In the current study the authors have made use of both cooperative and non-cooperative game theory to depict the rational behavior of vehicle drivers in a transportation network.
Multi-Agent System focus on intentional and purposeful behavior between: (i) Agent and its environment and (ii) Multiple agents in communication with each other. Currently there is no such information system that provides: (i) Information about the dynamic traffic situation (ii) Compute a shortest path to reach to the destination (iii) Store the optimized path for traversing the same path again.
The system developed: (i) Identifies the vulnerability in the transportation network (ii) Detects the location of natural and human made obstacles causing traffic congestion (iii) Computes the Multi-Agent Navigation Graph for repeated traversal of path.
Conclusion:
The use of game theory allows handling cooperation and negotiation strategies between the vehicles, by which the system can realize the real time location of the vehicles. This resolves the state of congestion that can happen at the intersection or within the path. Therefore, coordination problem among vehicle drivers and traffic central authority can be handled. The communication between the agents is established through knowledge query and manipulation language by applying mathematical treatment to Spatial-Temporal Database Model. The effort to mathematically model conflict and cooperation in traffic involves not only the intelligent rational human decision makers, along with their irrational behavior, but also the potential intelligent rational (and maybe irrational) behavior of the vehicle drivers.
