Cooperative communication in UAVs

Project report submitted in partial fulfillment

of the requirements for the degree of

Bachelor of Technology
in
Computer Science and Engineering

by

Khushal Goyal - 21ucs109

Kaustubh - 21ucs108

Under Guidance of
Dr. Saurabh Kumar

Department of Computer Science and Engineering

The LNM Institute of Information Technology, Jaipur

November 2024
©The LNM INSTITUTE OF INFORMATION TECHNOLOGY Jaipur-2022.
All rights reserved.
 The LNM Institute of Information Technology
Jaipur, India

CERTIFICATE

This is to certify that the project entitled “Cooperative communication in UAVs” , submitted
by Khushal Goyal (21ucs109) and Kaustubh (21ucs108) in partial fulfillment of the require-
ment of degree in Bachelor of Technology (B. Tech), is a bonafide record of work carried out
by them at the Department of Computer Science and Engineering, The LNM Institute of Infor-
mation Technology, Jaipur, (Rajasthan) India, during the academic session 2024-2025 under
my supervision and guidance and the same has not been submitted elsewhere for award of any
other degree. In my/our opinion, this report is of standard required for the award of the degree
of Bachelor of Technology (B. Tech).

Date Supervisor: Dr. Saurabh Kumar

Acknowledgments

I would like to take this opportunity to express my deepest gratitude to all those who have sup-
ported me throughout the completion of this project report titled “Cooperative communication
in UAVs”.

First and foremost, I would like to express my sincere thanks to Prof. Dr. Saurabh Kumar,
Department of Computer Science and Engineering, LNMIIT, for his invaluable guidance, con-
stant encouragement, and support throughout the course of this project. His extensive knowl-
edge and insightful suggestions have been pivotal in the successful completion of this work.

I am also grateful to the faculty and staff of Computer Science and Engineering for providing
the necessary resources and for their continuous assistance during the project period. I would
also like to acknowledge my friends and classmates for their constant support, constructive
feedback, and cooperation during the various stages of this project. Lastly, I would like to
thank my family for their unwavering support, patience, and encouragement throughout my
academic journey. Without their love and understanding, the successful completion of this
project would not have been possible.

Thank you all.

iv
Abstract

In emergency situations such as fire outbreaks, deploying drones for quick response can sig-
nificantly reduce damage and improve safety. This project presents an algorithm to efficiently
assign multiple drones to fire events in a structured terrain. The terrain is represented as an N ×
M grid with cells that can contain drones, fire events, land, or blocked areas. Each cell is asso-
ciated with different weights for each drone, reflecting the energy cost required for that drone
to traverse the cell. The algorithm leverages Dijkstra’s shortest path algorithm to dynamically
allocate drones to fire events based on the minimal energy expenditure. The system uses ad-
ditional memory structures to store distance values and parent matrices, allowing for efficient
pathfinding and assignment. By maintaining a priority queue, the algorithm selects drones to
reach fire locations while considering varying energy costs across different cells. The proposed
solution is validated with simulations demonstrating how drones are optimally assigned to fire
events. Adjustments to terrain weights are also analyzed to observe the impact on drone be-
havior. The results highlight the algorithm’s ability to adapt to changing terrain conditions and
optimize resource allocation. This system can be further extended for real-world applications
like disaster management, surveillance, and search-and-rescue missions, where rapid response
is crucial.

v
Contents

List of Figures viii

1 Introduction 1
1.1 The Area of Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problem Addressed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Proposed Solution Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.1 Phase 1: Individual UAV Navigation Algorithms . . . . . . . . . . . 3
1.3.2 Phase 2: Cooperative Multi-Drone Coordination . . . . . . . . . . . 4
1.4 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Creation of bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Literature Review 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Reinforcement Learning-Based Approaches . . . . . . . . . . . . . . 5
2.1.2 Heuristic-Based Approaches . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3 Deep Reinforcement Learning-Based Approaches . . . . . . . . . . . 6
2.1.4 Signal Processing-Based Approaches . . . . . . . . . . . . . . . . . 6
2.1.5 Computer Vision-Based Approaches . . . . . . . . . . . . . . . . . . 6
2.1.6 Markovian-Based Approaches . . . . . . . . . . . . . . . . . . . . . 7
2.2 Gaps in Existing Literature and Proposed Approach . . . . . . . . . . . . . . 7

3 Proposed Work 8
3.1 Phase 1: Multi-Source Dijkstra’s Algorithm for UAV Disaster Response . . . 8
3.2 Phase 2: Game Theory Optimization for Multi-Robot Path Planning . . . . . 10
3.2.1 Core Classes and Their Roles . . . . . . . . . . . . . . . . . . . . . 10
3.2.2 Game Theory Implementation . . . . . . . . . . . . . . . . . . . . . 11
3.2.3 Visualization and Output . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.4 Key Innovations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Simulation and Results 14

4.1 Phase1: Multi-Source Dijkstra’s Algorithm Analysis . . . . . . . . . . . . . 14
4.1.1 Algorithmic Complexity Analysis . . . . . . . . . . . . . . . . . . . 14
4.1.2 Path Analysis for Event at Node 9 . . . . . . . . . . . . . . . . . . . 14
Drone 1 Path Analysis: . . . . . . . . . . . . . . . . . . . . . 14
Drone 2 Path Analysis: . . . . . . . . . . . . . . . . . . . . . 15
4.1.3 Decision-Making Process . . . . . . . . . . . . . . . . . . . . . . . 15
4.1.4 Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.5 Key Findings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

vi
CONTENTS vii

4.1.6 Practical Implications . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4.2 Phase 2: Game Theory Optimization Analysis . . . . . . . . . . . . . . . . . 17
4.2.1 Test Case Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Test Case 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Test Case 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2.2 Game Theory Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2.3 Optimization Effectiveness . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.4 System Performance Analysis . . . . . . . . . . . . . . . . . . . . . 19
4.2.5 Key Findings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.6 Practical Implications . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2.7 Statistical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5 Conclusions and Future Work 21

5.1 Performance Analysis from Box Plot . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Phase 1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 Phase 2 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.5 Research Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.6 Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Bibliography 26
List of Figures

3.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.1 Drone Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.2 Map of Test Case 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5.1 Box Plot of Execution Time . . . . . . . . . . . . . . . . . . . . . . . . . . 21

viii
Chapter 1

Introduction

1.1 The Area of Work

The increasing vulnerability of communities around the world is being driven by intercon-
nected factors such as rapid population growth, accelerated urbanization, climate change, and
persistent poverty. As a result, the frequency and severity of natural disasters, such as floods,
wildfires, and storms, are on the rise. These challenges underscore the urgent need for robust
disaster preparedness and response mechanisms to protect lives and livelihoods. Recognizing
this need, the European Union has prioritized funding for early warning systems and disaster
resilience initiatives in vulnerable regions. In 2022, the EU allocated C76.5 million to sup-
port 69 projects across more than 40 countries. These initiatives focus on enhancing disaster
readiness by developing advanced early warning systems, improving infrastructure resilience,
and building local and national capabilities to respond effectively to emergencies. For 2023,
the EU has increased its commitment with an allocation of over C78 million for catastrophe
preparedness efforts. The focus of these investments is on strengthening disaster management
frameworks, particularly in regions most susceptible to climate-induced risks. By supporting
initiatives that bolster local response capabilities, the EU aims to reduce disaster-related vul-
nerabilities and enhance the resilience of communities. This approach not only emphasizes the
deployment of early warning systems but also addresses the broader context of disaster pre-
paredness, ensuring that nations are better equipped to manage the impacts of climate change.
The area of work therefore revolves around proactive disaster management, leveraging tech-
nology and strategic funding to build resilient systems that can withstand the increasing threat
of natural disasters, driven by environmental and socio-economic factors. This aligns with
global efforts to mitigate the impacts of climate change and reduce vulnerabilities in at-risk
populations, ensuring sustainable development and safety for future generations.

1
chapter: 01 2

1.2 Problem Addressed

The development of AI-based solutions for Unmanned Aerial Vehicle (UAV) navigation
is currently facing substantial challenges, primarily due to the complexities inherent in
real-world environments. UAVs are increasingly being used for a range of applications
such as disaster response, surveillance, and delivery services. However, for UAVs to operate
autonomously and effectively, they must navigate complex environments without human inter-
vention. This presents significant obstacles that existing AI models have yet to fully overcome.

One of the primary challenges is navigating unknown environments. Unlike controlled

settings, real-world terrains are often unpredictable and continuously changing, making it
difficult for UAVs to chart optimal paths. Current AI algorithms struggle to adapt in real-time
to unknown obstacles, terrain variations, and dynamically changing conditions.
Furthermore, UAVs must operate in partially observable environments, where not all relevant
information is readily available. Limited sensor ranges and blind spots can cause UAVs
to miss crucial environmental details, leading to suboptimal or even hazardous navigation
decisions. The partial observability problem remains a critical hurdle, as it requires AI models
to make decisions with incomplete data, often in real-time.
Additionally, UAVs frequently encounter cluttered environments filled with obstacles such
as trees, buildings, or debris, especially in urban areas or disaster zones. Navigating through
such spaces requires sophisticated path-planning and obstacle-avoidance capabilities, which
current AI-based solutions struggle to achieve reliably.
The lack of effective solutions to address these challenges is impeding the progress of UAV
technology. Existing navigation algorithms are limited in their ability to handle the combined
complexities of unknown, partially observable, and cluttered environments. As a result, there
is an urgent need for more advanced AI models that can adapt to these challenges, ensuring
that UAVs can safely and efficiently navigate diverse and unpredictable terrains.
Developing robust AI solutions that address these issues is crucial to unlocking the full
potential of UAVs in critical applications, especially in scenarios where human access is
limited or unsafe.

Unmanned Aerial Vehicles (UAVs) have emerged as critical tools in disaster management,
enabling rapid response and assessment in environments that are too dangerous or inaccessible
for humans. However, despite the potential benefits, current UAV navigation systems face
significant challenges that limit their effectiveness in real-world scenarios. These limitations
are particularly pronounced when multiple drones are deployed simultaneously in complex,
dynamic environments such as disaster zones.

The primary challenges for UAV navigation in these contexts include:

1. Unknown and Dynamic Environments: In disaster scenarios, the terrain is often
unpredictable and continuously changing due to debris, collapsing structures, fires, and other
chapter: 01 3

hazards. UAVs must operate in real-time without prior knowledge of the terrain, making it
difficult for them to determine safe and efficient paths. Current navigation systems struggle
to adapt quickly to such unknown conditions, which can lead to inefficient routes, increased
energy consumption, or even mission failure.
2. Partial Observability: UAVs rely on sensors to perceive their surroundings, but these
sensors have limitations, such as restricted range and susceptibility to environmental condi-
tions like smoke or dust. In partially observable environments, UAVs do not have access to
complete information, forcing them to make decisions based on limited data. This increases
the risk of collisions, inefficient navigation, and failure to reach critical areas in time.
3. Cluttered and Constrained Spaces: Disaster environments are often cluttered with
obstacles, such as collapsed buildings, trees, or debris. Navigating through these tight spaces
requires advanced obstacle avoidance and path planning. The complexity of navigating safely
in cluttered environments is compounded when multiple drones are deployed, as they must
also avoid colliding with each other.
4. Lack of Coordination in Multi-Drone Systems: While deploying multiple drones can
significantly enhance coverage and response time, it introduces additional challenges related
to coordination and resource allocation. Without effective communication and cooperation
strategies, drones may end up redundantly covering the same areas or competing for access to
critical zones, leading to inefficient use of resources and increased response times.
Given these challenges, current AI-based navigation solutions are proving insufficient. They
either lack the adaptability to handle unknown and partially observable environments or are
unable to coordinate multiple drones effectively in real-time. Addressing these limitations is
crucial to enable UAVs to operate autonomously in complex and high-stakes environments.

1.3 Proposed Solution Overview

To overcome the above challenges, we propose a comprehensive solution comprising two dis-
tinct phases aimed at enhancing UAV navigation in disaster scenarios:

1.3.1 Phase 1: Individual UAV Navigation Algorithms

The first phase focuses on developing robust algorithms to enable individual UAVs to navigate
efficiently in disaster environments. This includes: Multi-Source Dijkstra Algorithm: This
algorithm is designed to optimize the pathfinding process for multiple drones, allowing them
to reach critical areas more efficiently while considering varying terrain conditions and energy
costs.
chapter: 01 4

1.3.2 Phase 2: Cooperative Multi-Drone Coordination

The second phase aims to improve the overall efficiency and effectiveness of UAV navigation
by fostering cooperation among multiple drones. This involves integrating principles from
Game Theory to enable drones to coordinate their actions, optimize resource allocation, and
avoid conflicts. By encouraging cooperative behavior, the system can achieve better coverage,
reduce redundancy, and ensure that critical areas are addressed promptly.

1.4 Objective

The goal of this two-phase approach is to develop an adaptive, efficient, and scalable UAV nav-
igation system that can be deployed in real-world disaster scenarios. By combining advanced
pathfinding algorithms with cooperative game theory strategies, the proposed solution seeks
to overcome the current limitations of UAV systems, ensuring faster, safer, and more effective
disaster response.

1.5 Creation of bibliography

Use bibch1.bib file to save your bib format citations. Use the command [1] for referring to a
particular article [2]. and a new citation [3].
Chapter 2

Literature Review

2.1 Introduction

To gain a comprehensive understanding of the challenges and potential solutions in the field of
UAV navigation, especially in complex and disaster-prone environments, we conducted an in-
depth review of 22 research papers. These studies highlighted a wide range of algorithmic ap-
proaches that have been explored to enhance the autonomous navigation capabilities of UAVs.
The review identified several prominent techniques, each with its strengths and limitations in
addressing specific challenges related to UAV navigation in unknown, partially observable,
and cluttered environments. Below, we summarize key approaches from the literature:

2.1.1 Reinforcement Learning-Based Approaches

Reinforcement learning (RL) focuses on training agents (in this case, UAVs) to make a se-
quence of decisions by maximizing cumulative rewards. Some of the traditional RL meth-
ods explored in the literature include SARSA (State-Action-Reward-State-Action) and Q-
Learning. These approaches enable UAVs to learn optimal policies by interacting with the
environment. However, traditional RL methods can struggle in high-dimensional and dynamic
environments due to their reliance on discrete state-action spaces and their inability to handle
continuous inputs efficiently. While they are effective in simpler scenarios, their scalability
and adaptability to complex environments remain limited.

2.1.2 Heuristic-Based Approaches

Heuristic algorithms are widely used for path planning due to their ability to find near-optimal
solutions efficiently. Methods like A* (A-star) and AO* (And-Or graph search) have been ex-
tensively applied in UAV navigation for finding the shortest path in a grid-based environment.
These algorithms use heuristics to reduce the search space, making them suitable for real-time
5
chapter: 02 6

applications. However, their performance degrades significantly in highly dynamic and par-
tially observable environments, as they require complete and deterministic information about
the terrain. This limitation reduces their effectiveness in scenarios like disaster zones where
obstacles and conditions change rapidly.

2.1.3 Deep Reinforcement Learning-Based Approaches

To overcome the limitations of traditional reinforcement learning, researchers have turned

to Deep Reinforcement Learning (DRL), which combines neural networks with RL to han-
dle high-dimensional inputs. Techniques like Deep Q-Networks (DQN) and Proximal Policy
Optimization (PPO) are among the most popular DRL methods applied to UAV navigation.
These approaches enable drones to learn complex navigation strategies directly from raw sen-
sor inputs, allowing them to adapt to dynamic environments. For example, DQN uses a deep
neural network to approximate the Q-value function, enabling efficient decision-making in
high-dimensional spaces, while PPO optimizes policies in a stable and efficient manner. De-
spite their promise, DRL approaches often require extensive training data and computational
resources, which may not always be feasible in real-world disaster scenarios.

2.1.4 Signal Processing-Based Approaches

Signal processing techniques are crucial for UAVs to interpret sensor data, such as radar, Li-
DAR, and camera inputs, which are used for obstacle detection and terrain mapping. These
methods enhance the UAVs’ ability to navigate cluttered and partially observable environ-
ments. Techniques like Kalman filtering and Fourier transforms are employed to filter noise
from sensor data and improve the reliability of the UAV’s perception systems. However, while
signal processing approaches are effective in enhancing the quality of sensor data, they do not
directly address the decision-making and path-planning challenges that UAVs face in dynamic
and unknown terrains.

2.1.5 Computer Vision-Based Approaches

With advancements in computer vision, UAVs can leverage Convolutional Neural Networks
(CNNs) and other deep learning models to interpret visual data, identify obstacles, and detect
fire or other hazards in real time. By using camera feeds, UAVs can classify terrain types
and adjust their navigation strategies accordingly. Computer vision techniques are particularly
useful in environments where other sensors might fail, such as in low-visibility conditions.
However, these approaches are computationally intensive and require robust hardware, which
may not be feasible for all UAV platforms, especially those with limited processing capabili-
ties.
chapter: 02 7

2.1.6 Markovian-Based Approaches

Markovian models, such as the Markov Decision Process (MDP) and Partially Observable
Markov Decision Process (POMDP), are used to model the decision-making process of UAVs
in uncertain environments. MDPs are effective in scenarios where the environment is fully
observable, while POMDPs extend this capability to environments where the UAV has lim-
ited visibility. These approaches are valuable for modeling uncertainty and enabling UAVs to
make decisions based on probabilistic predictions of future states. However, solving POMDPs
is computationally complex, making them less suitable for real-time navigation in highly dy-
namic environments.

2.2 Gaps in Existing Literature and Proposed Approach

Despite the diversity of approaches reviewed, existing solutions often fall short in address-
ing the combined challenges of unknown environments, partial observability, and multi-drone
coordination. Traditional reinforcement learning and heuristic-based approaches lack the flex-
ibility needed for dynamic environments, while deep reinforcement learning models require
significant computational resources and extensive training data, which may not be practical in
real-world disaster scenarios. To overcome these limitations, our proposed solution integrates
multiple advanced algorithms to enhance UAV navigation. In Phase 1, we focus on develop-
ing both a Multi-Source Dijkstra Algorithm to improve individual UAV navigation in disaster
environments. The Dijkstra algorithm allows for efficient pathfinding. In Phase 2, we aim
to enhance the effectiveness of multi-drone deployments by leveraging principles from Game
Theory to foster cooperation among drones. This phase addresses the coordination challenges
by optimizing resource allocation and minimizing conflicts between UAVs, ensuring efficient
coverage and response in disaster-stricken areas. This two-phase approach aims to bridge the
gaps identified in the literature by combining the strengths of traditional pathfinding, adaptive
learning, and cooperative strategies to create a robust and scalable solution for UAV navigation
in complex environments.
Chapter 3

Proposed Work

3.1 Phase 1: Multi-Source Dijkstra’s Algorithm for UAV Disaster

Response

F IGURE 3.1: Algorithm

8
chapter: 02 9

The algorithm presented is a specialized adaptation of Dijkstra’s algorithm designed for coor-
dinating multiple UAVs (drones) in disaster response scenarios. Let me break down the key
components and execution flow

Input Requirements

• D: Number of agents (drones).

• k: Number of disaster instances.

• G: A rectangular terrain of size N × M .

Initialization Phase (Lines 1-6)

The algorithm begins by defining a terrain G with weights. For each cell u in the terrain:

• Sets the initial distance u.d to ∞.

• Sets the initial predecessor u.π to NIL.

This ensures all locations are initially marked as unreachable.

Source Processing (Lines 7-12)

1. Creates an empty Priority Queue Q.

2. For each source s in the set of sources S:

• Sets the source distance s.d to 0.

• Sets the source predecessor s.π to NIL.
• Enqueues the source into Q.

This establishes the starting points for the pathfinding process.

Main Processing Loop (Lines 13-22)

1. While the priority queue Q is not empty:

(a) Extracts the node u with the minimum distance (EXTRACTMIN(Q)).

(b) If the current node u is identified as a disaster location:
• Initializes and traces the path to this location.
(c) For each adjacent node w to u:
• Performs the RELAX operation to update distances.
chapter: 02 10

Key Features of the Algorithm

The algorithm efficiently handles:

Multiple starting points (drone positions). Multiple target points (disaster locations). Optimal
pathfinding on a weighted terrain. Path tracing once disaster locations are found.

Enhancements Over Traditional Dijkstra’s Algorithm

The algorithm extends traditional Dijkstra’s algorithm by:

Supporting multiple source points simultaneously. Incorporating disaster detection function-
ality. Enabling path tracing. Operating on a grid-based terrain instead of a general graph.

Effectiveness for Disaster Response

This algorithm is particularly effective for disaster response as it:

Finds optimal paths from multiple drones to disaster locations. Considers terrain character-
istics through weights. Can handle multiple simultaneous disaster scenarios. Maintains effi-
ciency through priority queue-based processing.

The use of a priority queue ensures that the algorithm always expands from the most promising
(closest) locations first, maintaining optimality while reducing computational overhead.

3.2 Phase 2: Game Theory Optimization for Multi-Robot Path

Planning

The problem in our first phase is that only address one parameter, that is distance. For a real
time scenario we have multiple factors or variables. Hence the real life problem is a bivariate
or multivariate problem. The problem is not to find solution that are optimal. For this we are
using game theory to introduce corporation among variables. We take two variables battey
and distance. We compute nash equillibrium to find the optimal solution.

Let us break down the key components and algorithmic approach in this phase:

3.2.1 Core Classes and Their Roles

• Robot Class: The Robot class manages individual robot attributes and facilitates the
computation of game theory strategies.
1 class Robot:
2 def __init__(self, robot_id, terrain, battery_level=100):
3 self.robot_id = robot_id
chapter: 02 11

4 self.battery_level = battery_level
5 self.current_node = random.choice(list(terrain.graph.nodes))
6 self.payoff_matrices = []
7

Key Features:
Initialization: Assigns a unique ID, battery level, and initial position. Stores payoff
matrices.
State Management: Tracks battery levels and position updates.
Methods: Includes functions for battery management and payoff matrix storage.

• Terrain Class: The Terrain class handles the graph representation of the environ-
ment and game-theory-related statistics.
1 class Terrain:
2 def __init__(self, places):
3 self.graph = ox.graph_from_place(places, network_type=’drive’)
4

Key Features:
Generates navigable graphs using OpenStreetMap data.
Implements Dijkstra’s algorithm for pathfinding and multi-source path computation.
Calculates game theory statistics based on resource efficiency.

• SystemController Class: The SystemController orchestrates the system by man-

aging robots and terrain, and integrates game theory principles.
1 class SystemController:
2 def __init__(self, robots, terrain):
3 self.robots = robots
4 self.terrain = terrain
5 self.target_node = self.terrain.choose_random_target()
6

Key Features:
Coordinates multiple robots and assigns targets. Executes optimal path planning and
resource-aware routing.

3.2.2 Game Theory Implementation

• Statistics Calculation: The system calculates efficiency ratios to evaluate the perfor-
mance of robots using the following function:
1 def calculate_game_theory_statistic(self, battery_levels, distances):
2 statistic = np.array(battery_levels) / np.array(distances)
3 return statistic
4
chapter: 02 12

Key Process:
Normalizes battery levels and scales them by distance. Higher ratios indicate better
efficiency and positioning.

• Pairwise Competition Analysis: Payoff matrices are generated for robots using relative
efficiency:
1 R1, R2 = statistics[i], statistics[j]
2 alpha = R1 / R2
3 row = np.array([[R1, R1/alpha], [R1/alpha, 0]])
4 column = np.array([[R2, R2*alpha], [R2*alpha, 0]])
5

Battery
Where statistic[i] i ∈ 1, 2, 3, . . . n is distance . The reason is for a robot we want to
assign utility on the bases of two parameters battery(this focus of servicability) and
distance(this focuses on Accessibility). This is a game theoric heuristic that we are
defining.
We want to increase utility as battery level increases and decrease utility as battery level
decreases. α is a value that is defined by statistics of both robots. Its function is to build
a relation between the heuristic of pair of robots. This can then further be used to define
utility in a game matrix.
Components:

– Constructs strategy matrices based on resource efficiency.

– Facilitates comparative analysis of robot capabilities.

• Nash Equilibrium Calculation: Optimal strategies are determined using Nash equilib-
rium:
1 rps = nash.Game(row, column)
2 equilibria = rps.support_enumeration()
3 payoffs = list(equilibria)[0]
4

Process Steps:

– Creates game matrices for strategic mapping.

– Finds stable solutions using support enumeration.

• Dominance Graph Construction: A directed graph is created to represent robot dom-

inance relationships:
1 if strategy1_i > strategy2_i and strategy2_j > strategy1_j:
2 dominance_graph.add_edge(self.robots[i].current_node, self.robots[
j].current_node)
3

Key Aspects:
 chapter: 02 13

– Models relationships based on Nash equilibrium payoffs.

– Enables optimal robot selection through dominance evaluation.

3.2.3 Visualization and Output

Visualization tools highlight robot positions, targets, and optimal paths:

1 def plot_map(self, best_robots):
2 # Visualization logic
3 # Color coding: blue for robots, red for target
4 # Path highlighting in blue
5 # Node size variation for emphasis

Features:
Shows robot and target locations with clear visual hierarchy. Uses color coding for intuitive
understanding.

3.2.4 Key Innovations

Resource Efficiency: Balances battery levels and distances.

Strategic Decision Making: Implements game theory for optimal robot selection.
Scalability: Efficiently manages increasing system size and complexity.
Chapter 4

Simulation and Results

4.1 Phase1: Multi-Source Dijkstra’s Algorithm Analysis

4.1.1 Algorithmic Complexity Analysis

• Time Complexity: O(n log(n))

The algorithm utilizes a priority queue implementation for node selection. For a graph
with n nodes:
Each node is extracted from the queue once: O(log n). Each edge relaxation opera-
tion: O(1). Total edges processed: O(m), where m is the number of edges. Overall
complexity remains O(n log(n)) due to priority queue operations.

4.1.2 Path Analysis for Event at Node 9

F IGURE 4.1: Drone Positioning

Drone 1 Path Analysis: Drone 1 was assigned to follow a multi-segment path to reach the
target node efficiently. The path was determined to be: Source → Node 1 → Node 5 → Node
8 → Node 9. Each segment of the path was evaluated based on its distance:
14
chapter: 02 15

• Distance Breakdown:

– Source to Node 1: 1 unit

– Node 1 to Node 5: 5 units
– Node 5 to Node 8: 1 unit
– Node 8 to Node 9: 1 unit

• Total Distance: The total travel distance for Drone 1 was calculated as 8 units, which
reflects a well-optimized path considering the shortest available connections between
the nodes.

Drone 2 Path Analysis: Drone 2 was assigned a simpler path structure with fewer nodes,
represented as: Source → Node 11 → Node 9. While the path had fewer segments, the dis-
tances involved were significantly longer, particularly in the initial segment.

• Distance Breakdown:

– Source to Node 11: 11 units

– Node 11 to Node 9: 1 unit

• Total Distance: The total travel distance for Drone 2 was calculated as 12 units, making
it less efficient compared to Drone 1 despite its simpler structure.

4.1.3 Decision-Making Process

The decision-making process focused on comparing the paths of both drones to identify the
optimal choice.

• Path Comparison: Drone 1’s path was 8 units long, while Drone 2’s path was 12 units
long. This revealed a clear advantage for Drone 1, with a 4-unit shorter path.

• Selection Criteria: Using the minimum distance principle, Drone 1 was selected as
the more efficient option, as 8 < 12. The shorter path resulted in a 33.33% efficiency
improvement over Drone 2’s path, demonstrating the algorithm’s ability to prioritize
resource optimization.

• Optimization Validation: The algorithm successfully identified the optimal path

among available options. Task assignment to Drone 1 was validated as the most effi-
cient choice. This highlighted the effectiveness of multi-source pathfinding techniques
in real-time scenarios.
chapter: 02 16

4.1.4 Efficiency Analysis

Efficiency is a critical measure for evaluating the performance of the pathfinding algorithm.
The analysis showed substantial improvements in resource utilization.

• Path Efficiency:

12 − 8
Efficiency Gain = × 100% = 33.33%
12

The significant reduction in travel distance directly translated to better resource uti-
lization, minimizing battery consumption and travel time. Such efficiency is crucial in
real-world disaster response scenarios where time and resources are limited.

• Algorithm Performance: The algorithm successfully handled multiple source points

and effectively processed alternative paths. It maintained an optimal decision-making
capability, ensuring robust and consistent results across test cases.

4.1.5 Key Findings

The implementation provided several key insights into the effectiveness of the proposed ap-
proach:

• Optimal Path Selection: The algorithm consistently identified the shortest available
path, demonstrating its capability to evaluate multiple options effectively. It maintained
optimality in decision-making processes, ensuring the best possible outcomes.

• Resource Optimization: By minimizing travel distance, the algorithm achieved sig-

nificant resource savings. Reduced response time allowed faster deployment of drones,
critical in high-stakes situations like disaster management. Efficient drone deployment
ensures better coverage and lower operational costs.

• System Performance: Reliable pathfinding algorithms ensured consistent performance

under varying conditions. Scalable design enabled the system to handle multiple nodes
and drones without degradation in decision-making quality.

4.1.6 Practical Implications

The study’s findings have several practical applications in real-world scenarios, particularly in
emergency response and resource management.

• Emergency Response: Faster reach to disaster sites ensures timely aid and resource
delivery. Optimized resource allocation enhances operational efficiency, allowing better
chapter: 02 17

management of drones and other assets. Improved response efficiency reduces down-
time and increases the success rate of operations.

• System Reliability: The system’s ability to guarantee optimal pathfinding enhances

trust in its deployment for critical missions. Consistent performance across test sce-
narios highlights the robustness of the proposed algorithm. Reliable decision-making
capabilities ensure safer and more predictable outcomes.

4.2 Phase 2: Game Theory Optimization Analysis

4.2.1 Test Case Analysis

Test Case 1: In this test case, three robots were assigned to different nodes in a simulated
environment. The configuration for each robot was as follows:

F IGURE 4.2: Map of Test Case 1

• Initial Configuration:
chapter: 02 18

– Robot 1: Located at Node 240297573 with 1% battery.

– Robot 2: Located at Node 65581512 with 1% battery.
– Robot 3: Located at Node 529003007 with 100% battery.
– Target Node: 65588983.

• Selected Robot: Robot 3, located at Node 529003007, was selected as the optimal robot
for the task due to its full battery level.

• Rationale: The decision was influenced by the critical battery levels of Robots 1 and 2,
both of which had only 1% battery, while Robot 3 with a 100% battery offered the best
chance of success in reaching the target node.

Test Case 2: In this test case, similar configurations were tested with a slightly different
setup. The robots were once again assigned to different nodes, with the target node slightly
altered.

• Initial Configuration:

– Robot 1: Located at Node 65637757 with 1% battery.

– Robot 2: Located at Node 65422436 with 1% battery.
– Robot 3: Located at Node 65493143 with 100% battery.
– Target Node: 65461657.

• Selected Robot: Robot 3, located at Node 65493143, was again selected as the optimal
robot, based on its fully charged battery.

• Rationale: As in Test Case 1, the low battery levels of Robots 1 and 2 made them
unsuitable for the task, and Robot 3’s full battery provided a strategic advantage in
completing the task efficiently.

4.2.2 Game Theory Analysis

• Resource-Based Decision Making: The battery levels were the primary criterion influ-
encing the robot selection process. Robots with a 1% battery were consistently excluded
from selection due to the high likelihood of failure. The robot with 100% battery domi-
nated the decision-making process in both test cases. This highlights the importance of
resource availability (battery) in making optimal decisions.

• Nash Equilibrium Results: In both Test Case 1 and Test Case 2, Robot 3 was selected,
as its full battery provided a clear dominance over the other robots. The low-battery
robots had no strategic advantage, as they would be unable to complete the task effec-
tively. The Nash equilibrium was stable, with Robot 3 being the rational choice in both
cases.
chapter: 02 19

• Dominance Graph Outcomes: In Test Case 1, Robot 3 was dominant, with no incom-
ing edges, indicating it was the clear choice. Similarly, in Test Case 2, Robot 3 had no
incoming edges, reaffirming its superiority over the low-battery robots.

4.2.3 Optimization Effectiveness

• Battery-Distance Ratio Impact: The high battery level of Robot 3 (100%) provided a
strategic advantage, allowing it to cover longer distances without the risk of depleting
its power before reaching the target. Robots with only 1% battery were automatically
disadvantaged, as they lacked the necessary resources to complete the mission. The
battery-to-distance ratio proved to be a critical factor in decision making, ensuring that
robots with higher resources were selected for the task.

• Strategic Selection: The algorithm consistently selected the robot with the highest bat-
tery level. Low-battery robots were systematically eliminated from consideration, as
they posed a high risk of failure. This robust decision-making process ensured that the
task was assigned to the most capable robot, improving the chances of success.

4.2.4 System Performance Analysis

• Decision Consistency: The algorithm demonstrated consistent performance across both

test cases, selecting the optimal robot in each scenario. There was a clear preference
for high-battery robots, indicating that the algorithm prioritized reliability and mission
success over other factors. The exclusion of low-battery robots was also consistent,
ensuring the system made rational decisions based on available resources.

• Resource Optimization: The algorithm effectively considered battery levels as the

most important factor in decision making. Position-based optimization was secondary
but still contributed to the overall selection process, especially in scenarios where bat-
tery levels were similar. The combination of these two metrics allowed for a balanced,
reliable selection of robots.

4.2.5 Key Findings

• Battery Level Significance: Battery level was the most critical factor in robot selec-
tion, with robots having 100% battery consistently being selected. Robots with only
1% battery were not selected, as they would have been unlikely to complete the mis-
sion successfully. The battery level’s significance highlights the importance of resource
management in robotic systems.

Position Impact: While position played a role in the decision-making process, it was sec-
ondary to the battery level. In both test cases, the robots with the highest battery were selected,
chapter: 02 20

even though other positional factors may have been favorable for the low-battery robots. This
ensured that the algorithm focused on minimizing the risk of mission failure.

Algorithm Robustness: The algorithm showed consistent performance across multiple test
cases, reaffirming its robustness. Clear decision-making was demonstrated, with the algo-
rithm always selecting the robot with the highest available resources. This demonstrated the
algorithm’s reliability in real-world robotic missions where resources are often limited.

4.2.6 Practical Implications

• Resource Management: The algorithm’s ability to effectively manage battery re-

sources ensures that robots are deployed efficiently, avoiding unnecessary risks associ-
ated with low-battery robots. This improves the overall system’s operational efficiency
and effectiveness in high-stakes situations, such as search and rescue or disaster re-
sponse.

• System Reliability: The consistent behavior of the algorithm guarantees that robots
will be selected based on their ability to successfully complete the mission. Predictable
behavior increases trust in the system, making it more likely to be adopted in critical
applications.

• Operational Efficiency: The quick decision-making capabilities of the algorithm allow

it to respond rapidly to dynamic situations, such as emergency missions where time is
of the essence. The clear selection criteria ensure that the best possible robot is always
chosen, improving overall system performance.

4.2.7 Statistical Analysis

• Battery Level Distribution:

Test Case 1 & 2:
Low Battery (1%): 2 robots. High Battery (100%): 1 robot. Success Rate: In both test
cases, the high-battery robot was selected 100% of the time, reinforcing the importance
of battery level in the selection process.

• Decision Making Metrics: Battery weight - The primary factor influencing robot se-
lection. Position weight - Played a secondary role, but did not override the battery
level in decision making. Combined metric - The combination of battery and posi-
tion metrics allowed for effective robot selection based on resource availability and task
requirements.
Chapter 5

Conclusions and Future Work

5.1 Performance Analysis from Box Plot

The box plot analysis clearly demonstrates a significant performance difference between the
Single-Source Shortest Path (SSSP) algorithm and the Multi-Source Shortest Path (MSSP)
algorithm. This analysis reveals key insights into execution times and the variability of each
algorithm’s performance across multiple test scenarios.

F IGURE 5.1: Box Plot of Execution Time

21
chapter: 02 22

• Execution Time Comparison: The median execution time for SSSP is approximately
2.5 seconds. This is the time taken by the algorithm to compute the shortest path from a
single source node to all other nodes in the network. In contrast, the median execution
time for MSSP is much lower, approximately 0.6 seconds. This improvement can be
attributed to the MSSP algorithm’s ability to simultaneously process multiple source
nodes, reducing the time complexity compared to the SSSP. Overall, the performance
improvement between the two algorithms is quite substantial, with MSSP showing about
a 76% reduction in execution time, making it a more efficient choice in multi-source
scenarios.

• Variability Analysis: The SSSP algorithm exhibits higher variability in its perfor-
mance, as indicated by the larger box height (approximately 2 seconds). This suggests
that the execution time fluctuates significantly depending on the size and structure of the
graph being processed. On the other hand, MSSP shows a more consistent performance
with a smaller box height (approximately 0.5 seconds). This reflects the algorithm’s
stability, indicating that it delivers predictable results regardless of the network’s com-
plexity.The reduced variability in MSSP suggests that it is a more reliable choice for
scenarios where consistent execution time is essential, such as real-time systems or ap-
plications requiring quick decision-making.

5.2 Phase 1 Conclusions

The results from Phase 1 of the research highlight the successful implementation and per-
formance of the Multi-Source Dijkstra’s algorithm, as well as identifying several areas of
improvement and limitation.

• Algorithm Effectiveness: The Multi-Source Dijkstra’s algorithm was successfully im-

plemented, offering a significant improvement over the traditional single-source ap-
proach. With a time complexity of O(n log n), the algorithm was efficient enough to
handle large-scale networks and was suitable for real-time applications. The algorithm
demonstrated its ability to select optimal paths for disaster response scenarios, ensuring
that the most efficient routes were chosen for drone coordination.

• Limitations: One of the major limitations of the current system is partial observability
in real-time systems. This means that the algorithm may not have complete information
about the network’s state at any given moment, which could lead to suboptimal deci-
sions. There is also uncertainty in environmental conditions, such as changes in weather
or obstacles that might arise unexpectedly, which could disrupt the pathfinding process.
Another limitation is the limited processing of sensor inputs. In dynamic environments,
the system may not always process new sensor data quickly enough to make real-time
decisions.
chapter: 02 23

• Key Achievements: The algorithm enabled efficient multi-drone coordination, ensuring

that drones could work together to cover a wider area and complete tasks more effec-
tively. The system successfully achieved optimal resource utilization, making the best
use of available battery power and positioning of the drones. Overall, the system demon-
strated a significant reduction in response time, making it suitable for critical missions
that require fast action, such as search-and-rescue operations.

5.3 Phase 2 Conclusions

Phase 2 focused on the integration of game theory to enhance decision-making in the robot
selection process, as well as on optimizing the system’s performance through resource man-
agement strategies.

• Game Theory Integration: A Nash equilibrium-based selection method was success-

fully implemented, allowing for the selection of robots based on their battery levels and
proximity to the target node. Effective battery-distance optimization was achieved, en-
suring that robots with the highest battery levels and shortest distances to the target were
selected for the task. This integration of game theory provided a robust decision-making
framework that improved the efficiency of robot deployment in real-time scenarios.

• Resource Optimization: The system demonstrated efficient battery management, en-

suring that robots with lower battery levels were excluded from selection, reducing the
risk of failure. Position-based optimization was also incorporated, allowing the system
to choose robots that were not only well-resourced but also strategically positioned for
success. The reliable robot selection criteria further ensured that only the most capable
robots were assigned tasks, minimizing the likelihood of mission failure.

• System Performance:

– The system exhibited consistent decision-making across multiple test scenarios,

reinforcing its reliability in dynamic environments.

– Clear strategic advantages were realized by selecting high-battery robots and op-
timizing their paths, leading to more efficient missions.

– Overall, the system showed robust performance in real-world settings, with reli-
able mission execution that met predefined objectives.

5.4 Future Work

While the current system has shown promising results, there are several key areas that could
be improved and expanded upon in future research.
chapter: 02 24

• Algorithm Enhancement: The integration of a Markov Partially Observable Markov

Decision Process (POMDP) model could help address the uncertainty and partial ob-
servability issues present in real-time systems. The implementation of computer vision-
based learning could enable the robots to better understand their surroundings and make
more informed decisions in dynamic environments. Future research should also focus
on the development of adaptive path planning strategies that can adjust to changes in the
environment or mission requirements.

• System Improvements: Real-time environmental mapping would allow the system to

continuously update the network graph, providing robots with the most up-to-date in-
formation for decision-making. Dynamic obstacle avoidance would improve the sys-
tem’s robustness, allowing robots to respond more effectively to unexpected obstacles
or hazards. Multi-objective optimization could be explored to ensure that the system
can simultaneously optimize for multiple factors, such as battery usage, time, and path
efficiency.

• Advanced Features: Proposed implementations of machine learning techniques could

be explored to enable robots to learn from their experiences and improve performance
over time. Dynamic resource allocation models should be developed to allow the system
to adjust robot tasks and resources based on real-time conditions and system require-
ments. Predictive maintenance algorithms could be integrated to anticipate and prevent
system failures, improving reliability and reducing downtime. Swarm intelligence tech-
niques could be further investigated to allow for more advanced coordination among
multiple robots, enhancing the system’s scalability.

Extended Capabilities: Future work should focus on enhancing multi-robot collaboration by

implementing more sophisticated task allocation mechanisms that dynamically assign tasks
based on robot capabilities and availability. Real-time adaptation mechanisms should be de-
veloped to enable the system to adjust robot behaviors and strategies based on changing envi-
ronmental conditions or mission objectives.

Technology Integration: The integration of sensor fusion techniques would improve the sys-
tem’s situational awareness by combining data from multiple sensors to create a more accurate
representation of the environment. IoT device integration would allow robots to communicate
more effectively with other devices in the network, enabling more coordinated and efficient
mission execution. Cloud-based computation support could be used to offload computation-
ally intensive tasks, providing additional processing power for real-time decision-making and
optimization.
chapter: 02 25

5.5 Research Directions

Several important research directions have emerged from the current work, which can be fur-
ther explored to advance the field of robotic systems and optimization algorithms.

• Theoretical Extensions: Advanced game theory models can be developed to further

refine the decision-making process and handle more complex scenarios involving mul-
tiple agents and competing interests. Research into multi-agent learning systems can
lead to more autonomous and intelligent robot behavior, enabling more efficient coordi-
nation among multiple robots. Distributed decision-making models should be explored
to enable robots to make local decisions while still contributing to a global objective,
improving scalability and robustness.

• Practical Applications: The developed system could be applied to urban search and res-
cue missions, where multiple robots need to collaborate in a dynamic and unpredictable
environment. Disaster response optimization could be further explored by applying the
system to real-world scenarios, improving the speed and efficiency of rescue operations.
Environmental monitoring applications could be enhanced by deploying multiple robots
to collect data in remote or hazardous areas.

• System Evolution: Autonomous learning algorithms should be developed to allow

robots to adapt their behaviors and strategies based on experience. Research into adap-
tive behaviors will enable robots to adjust their actions in response to changing envi-
ronmental or task conditions, making them more flexible and resilient. Further research
into resilient operations is necessary to ensure that the system can function reliably even
in the face of failures or unexpected conditions.

5.6 Recommendations

The following recommendations are proposed to guide future developments and improvements
of the system.

• Short-term Goals: Focus on further optimizing the algorithm for improved perfor-
mance and reduced computational complexity. Improve the system’s robustness to han-
dle real-time uncertainties and dynamic environments. Establish performance bench-
marks to evaluate system effectiveness in various scenarios and compare it to existing
solutions.

• Long-term Vision: Aim for full autonomy of the robot system, allowing it to operate
independently without human intervention. Pursue the integration of multiple systems to
create a more scalable and versatile solution that can address a wider range of tasks and
chapter: 02 26

environments. Ensure the system is ready for real-world deployment, with the ability to
perform reliably in various mission types and environments.

This research provides a strong foundation for autonomous multi-robot systems while iden-
tifying clear paths for future development and enhancement. The significant performance
improvements demonstrated in the box plot analysis, combined with the successful imple-
mentation of game theory optimization, suggest promising directions for future research and
practical applications in disaster response and autonomous navigation systems.
Bibliography

[1] S. Saini, A. M. Kumar, S. Veeramachaneni, and M. Srinivas, “An alternative approach to buffer
insertion for delay and power reduction in vlsi interconnects,” in VLSID’10. 23rd International
Conference on VLSI Design, 2010., pp. 411–416, IEEE, 2010.

[2] A. Imre, G. Csaba, L. Ji, A. Orlov, G. Bernstein, and W. Porod, “Majority logic gate for magnetic
quantum-dot cellular automata,” Science, vol. 311, no. 5758, pp. 205–208, 2006.

[3] L. Chen, S. Ma, D. Zhang, F. Wei, and B. Chang, “On the pareto front of multilingual neural
machine translation,” arXiv preprint arXiv:2304.03216, 2023.

27