# Methodology

## Overview
The methodology of this research focuses on developing and analyzing decentralized algorithms for multi-agent path planning. By leveraging principles from swarm robotics and autonomous systems, the proposed methods aim to enable agents to navigate dynamic environments efficiently and cooperatively. In this section, we will explore the key algorithms and techniques used, their underlying principles, and pseudocode representations. Additionally, we will discuss the simulation environment and evaluation criteria used for testing and analyzing the algorithms' performance.

## Key Algorithms Explored

### 1. Decentralized Decision Algorithm
The decentralized decision algorithm allows agents to operate autonomously while adhering to a global objective. Agents gather local information from their surroundings and neighboring agents to make real-time decisions. This approach ensures that decisions are made efficiently without relying on a central controller, thereby enhancing system robustness and scalability.

#### Core Features
- **Local Awareness**: Each agent perceives only its immediate environment and neighbors.
- **Decision Rules**: Each agent prioritizes actions based on predefined rules to avoid collisions and optimize travel efficiency.
- **Communication Minimization**: Agents communicate only when necessary, preserving bandwidth and reducing overhead.

#### Pseudocode
```pseudo
Algorithm: Decentralized Decision Algorithm
Inputs: 
    agent_state: Current state of the agent (position, velocity, goal)
    neighbors: Information about nearby agents (positions, velocities)
    environment: Local perception of obstacles
Output: Next action (move, wait, or communicate)

1. Initialize parameters (e.g., max_speed, preferred_distance)
2. Sense local environment to detect obstacles
3. For each neighbor in neighbors:
       a. Calculate relative distance and velocity
       b. Check for potential collisions
       c. Adjust velocity/trajectory to avoid collisions
4. Evaluate goal proximity:
       a. If destination is within range, stop
       b. Else, calculate optimal path to goal
5. Communicate with neighbors if needed to coordinate actions
6. Execute next action based on adjusted trajectory
```

---

### 2. Cooperative Pathfinding Algorithm
Cooperative pathfinding is essential for ensuring that agents not only avoid collisions but also work together to achieve a collective goal. This algorithm incorporates dynamic priority assignment and peer-to-peer negotiation to resolve conflicts in real-time.

#### Core Features
- **Dynamic Prioritization**: Adaptive priorities based on proximity to the goal or urgency.
- **Conflict Resolution**: Agents negotiate pathways by sharing local plans and reallocating tasks to minimize bottlenecks.
- **Global Optimization**: Despite local decision-making, the algorithm promotes a global perspective to achieve overall system efficiency.

#### Pseudocode
```pseudo
Algorithm: Cooperative Pathfinding Algorithm
Inputs: 
    agent_state: Current state of the agent (position, velocity, goal)
    neighbors: List of neighboring agents and their states
    environment: Local map of the environment
Output: Updated path for the agent

1. Initialize path to goal using heuristics (e.g., straight-line distance)
2. While not at goal:
       a. Observe local environment for dynamic changes (e.g., moving obstacles)
       b. Share intended path with neighbors
       c. Receive paths from neighbors
       d. Identify potential conflicts (e.g., collision points, bottlenecks)
       e. Resolve conflicts by adjusting paths based on priorities
           i. If holding higher priority, maintain path
           ii. If holding lower priority, yield and recompute path
       f. Move to the next position in the path
3. End
```

---

## Simulation Environment
To evaluate the proposed algorithms, simulations were conducted in a grid-based virtual environment that emulates real-world scenarios. The environment is populated with agents, obstacles, and dynamic elements (e.g., moving obstacles).

### Environment Setup
- **Grid World**: The environment is represented as a 2D grid with discrete cells. Each cell is marked as empty, occupied by an obstacle, or part of an agents path.
- **Agent Initialization**: Agents are randomly placed on the grid with unique start and goal locations.
- **Dynamic Elements**: The environment includes moving obstacles and dynamically changing layouts to test algorithm adaptability.

### Key Parameters
- **Agent Count**: Variable number of agents to test scalability.
- **Communication Range**: Defines the radius within which agents can exchange information.
- **Obstacle Density**: Proportion of the grid occupied by obstacles.

---

## Evaluation Metrics
The performance of the algorithms was evaluated using the following metrics:

1. **Path Efficiency**: Total distance traveled by all agents compared to the optimal paths.
2. **Collision Rate**: Number of collisions or near-collisions recorded during the simulation.
3. **Scalability**: Algorithm performance as the number of agents increases.
4. **Communication Overhead**: Frequency and size of messages exchanged between agents.
5. **Adaptability**: Ability to handle dynamic changes in the environment, such as moving obstacles or altered goals.

---

By combining these decentralized decision and cooperative pathfinding algorithms, the research aims to create a robust framework for multi-agent path planning that is both scalable and adaptable to real-world conditions. The next section will discuss the results of applying these methodologies in simulated environments.