Robot Swarm Scheduling - Beach Cleanup Scenario

Overview

This project implements an AI-driven multi-agent system for autonomous debris collection on a simulated beach environment. The robots use an optimized path-planning strategy of Multi-Level A* (MLA*), ensuring efficient debris collection and transportation to a central collection point.

Features

• Multi-Agent Task Allocation: Assigns debris collection tasks to available robots dynamically.
• Path Planning with MLA*: Implements an enhanced A* search with multiple levels to optimize robot movement.
• Obstacle Avoidance: Ensures robots navigate without colliding with ongoing tasks.
• Dynamic Task Handling: Robots continuously receive and execute new tasks as the simulation progresses.
• Visualization: Displays a grid-based map of the environment, including robots, debris, and the collection point.

Research Paper Inspiration

The algorithm is inspired by the research paper: A Multi-Label A* Algorithm for Multi-Agent Pathfinding, which explores efficient task allocation and path planning in multi-agent environments. Our implementation adapts these principles to a real-world scenario of autonomous beach cleanup.

Installation & Usage

Prerequisites

• Python 3.x
• Required libraries: heapq, random, math, copy

Running the Simulation

Clone the repository and run the script:

git clone https://github.com/yourusername/beach-cleanup-ai.git
cd beach-cleanup-ai
python beach_cleanup.py

Code Structure

📂 beach-cleanup-ai
│-- 📜 beach_cleanup.py   # Main simulation script
│-- 📜 README.md          # Project documentation

Algorithm Explanation

Multi-Label A* Algorithm

• Initialization:
  • The search starts from the agent’s current location.
  • An initial node is added to a queue.
• Search Process:
  • Nodes are expanded based on their cost values.
  • If a node reaches the maximum allowed time step, it is discarded.
  • The algorithm operates in multiple levels:
    • Level 1: The agent is searching for a task.
    • Level 2: The agent is executing the assigned task.
  • Once the agent reaches the goal location in Level 2, the path is returned.
  • If no valid path is found, the algorithm terminates with failure.

Task Assignment Procedure

• Time-Stepped Execution:
  • The process runs iteratively, updating at each time step.
• At each time step:
  • Identify available agents and newly released tasks.
  • Form agent-task pairs and prioritize them based on a heuristic value, based on Manhattan distance .
  • Assign tasks if the Multi-Label A* algorithm successfully finds a path.
  • Update agent paths accordingly and remove assigned tasks from the pool.
• Completion:
  • The loop continues until all tasks are assigned, returning the final solution.

Example Output

These images showcase the output of the Multi-Level A* (MLA*) Path Planning Algorithm for task assignment and navigation in a robotic debris collection scenario.

Initial State (Time = 0)

• This image represents the initial setup with robots (R0-R4) and debris (D0-D4).
• The task list displays the locations of debris, and the robot list shows their starting positions.
• The grid represents the environment where robots will navigate to collect debris and transport it to the collection point (C0).

Progressed State (Time = 17)

• The algorithm assigns tasks to robots based on the Manhattan distance heuristic.
• Debris collected: D0, D1, D3, D4, indicating successful task completion.
• Resting robots: R0, R1, R3, R4, showing which robots have completed their tasks.
• The grid reflects robot movement, with some robots reaching their goal while others are still in transit.