TrajAllocPy: Decentralized Multi-Robot Task Allocation for Area Coverage

TrajAllocPy is a Python library for decentralized multi-robot task allocation using the Consensus Based Bundle Algorithm (CBBA). It's designed for area coverage problems where multiple robots need to efficiently distribute and execute trajectory-based tasks while avoiding obstacles.

🚀 Key Features

• Decentralized Algorithm: Uses CBBA for distributed task allocation without central coordination
• Obstacle Avoidance: Built-in support for complex environments with obstacles
• Trajectory Tasks: Handles line-segment based coverage tasks (e.g., search patterns, surveillance routes)
• Visualization: Real-time plotting of robot paths and task allocation
• Flexible Configuration: Customizable robot capacities, velocities, and task rewards
• GeoJSON Support: Load real-world environments from GeoJSON files

📦 Installation

Quick Install

pip install trajallocpy

Development Install

git clone https://github.com/kasperg3/TrajAllocPy.git
cd TrajAllocPy
pip install -r requirements.txt
pip install -e .

🎯 Quick Start

Here's a simple example to get you started:

importnumpyasnpfromtrajallocpyimportAgent, CoverageProblem, Experiment, Taskimportshapely# Set random seed for reproducible resultsnp.random.seed(123)
# Create a simple environmentboundary=shapely.geometry.Polygon([(0, 0), (100, 0), (100, 100), (0, 100)])
obstacles=shapely.geometry.MultiPolygon([
shapely.geometry.Polygon([(20, 20), (40, 20), (40, 40), (20, 40)]),
shapely.geometry.Polygon([(60, 60), (80, 60), (80, 80), (60, 80)])
])
# Define tasks (trajectory segments to cover)tasks= [
Task.TrajectoryTask(0, shapely.geometry.LineString([(10, 10), (15, 15)]), reward=100),
Task.TrajectoryTask(1, shapely.geometry.LineString([(50, 30), (70, 35)]), reward=100),
Task.TrajectoryTask(2, shapely.geometry.LineString([(30, 70), (45, 85)]), reward=100),
]
# Create coverage problemcoverage_problem=CoverageProblem.CoverageProblem(
restricted_areas=obstacles,
search_area=boundary,
tasks=tasks
)
# Create agentsagents= [
Agent.config(0, [(10, 50)], capacity=500, max_velocity=10),
Agent.config(1, [(50, 10)], capacity=500, max_velocity=10),
Agent.config(2, [(90, 90)], capacity=500, max_velocity=10),
]
# Run the experimentexperiment=Experiment.Runner(
coverage_problem=coverage_problem,
enable_plotting=True, # Shows real-time visualizationagents=agents
)
# Solve and get resultsexperiment.solve()
compute_time, iterations, path_lengths, task_lengths, path_costs, rewards, routes, max_cost=experiment.evaluateSolution()
print(f"Computation time: {compute_time:.3f} seconds")
print(f"Total route length: {sum(path_lengths.values()):.2f}")
print(f"Total rewards: {sum(rewards.values()):.2f}")

📚 Complete Example

For a comprehensive example, see example_simple.py which includes:

• Creating environments programmatically
• Loading from GeoJSON files
• Configuring multiple agents
• Visualizing results
• Performance evaluation

Run the example:

python example_simple.py

🗺️ Working with GeoJSON

TrajAllocPy supports loading environments from GeoJSON files. Your GeoJSON should contain features with these IDs:

• "boundary": The search area boundary (Polygon)
• "obstacles": Restricted areas to avoid (MultiPolygon)
• "tasks": Trajectory segments to cover (MultiLineString)

fromtrajallocpyimportAgent, CoverageProblem, Experiment, Taskimportgeojsonfromshapelyimportgeometry# Load environment from GeoJSONwithopen("environment.geojson") asf:
geojson_data=geojson.load(f)
# Extract geometriesgeometries= {}
forfeatureingeojson_data["features"]:
iffeature["geometry"]:
geometries[feature["id"]] =geometry.shape(feature["geometry"])
# Create tasks from the loaded geometriestasks= [
Task.TrajectoryTask(i, task_geom, reward=100) fori, task_geominenumerate(geometries["tasks"].geoms)
]
# Continue with coverage problem setup...

🔧 Configuration Options

Agent Configuration

agent=Agent.config(
0, # Unique agent identifier
[(0, 0)], # Starting position [x, y]1000, # Maximum travel distancemax_velocity=10# Maximum speed
)

Task Configuration

task=Task.TrajectoryTask(
id=0, # Unique task identifiertrajectory=line_geometry, # Shapely LineStringreward=100# Task completion reward
)

Coverage Problem

problem=CoverageProblem.CoverageProblem(
restricted_areas=obstacles, # Areas to avoid (MultiPolygon)search_area=boundary, # Valid operation area (Polygon)tasks=task_list# List of tasks to allocate
)

📊 Understanding Results

The evaluateSolution() method returns a tuple with:

1. Computation time (seconds)
2. Algorithm iterations
3. Path lengths (dictionary: agent_id -> total path length)
4. Task lengths (dictionary: agent_id -> total task length covered)
5. Path costs (dictionary: agent_id -> total travel cost)
6. Rewards (dictionary: agent_id -> total rewards collected)
7. Route assignments (dictionary: agent_id -> coordinate list of full route)
8. Maximum route cost (bottleneck agent cost)

🎨 Visualization

Enable real-time visualization by setting enable_plotting=True in the experiment runner. This shows:

• Environment boundaries and obstacles
• Task locations and assignments
• Agent paths and positions
• Real-time algorithm progress

🏗️ Architecture

TrajAllocPy implements the CBBA algorithm with these key components:

• Agent: Individual robot with position, capacity, and capabilities
• Task: Trajectory segment with location, reward, and requirements
• CoverageProblem: Environment definition with boundaries and obstacles
• Experiment.Runner: Algorithm execution and visualization manager

📈 Performance Tips

• Task Density: More tasks than agents generally leads to better solutions
• Agent Capacity: Higher capacity allows longer routes but may reduce parallelism
• Environment Complexity: Simple convex environments solve faster
• Visualization: Disable plotting (enable_plotting=False) for faster computation

🔬 Research & Citations

This library implements the research presented in:

@inproceedings{grontved2023icar,
title={Decentralized Multi-UAV Trajectory Task Allocation in Search and Rescue Applications},
author={Gr{\o}ntved, Kasper Andreas R{\o}mer and Schultz, Ulrik Pagh and Christensen, Anders Lyhne},
booktitle={21st International Conference on Advanced Robotics},
year={2023},
organization={IEEE}
}

🤝 Contributing

We welcome contributions! Please see:

• CONTRIBUTING.md for guidelines
• CODE_OF_CONDUCT.md for community standards
• Open issues for bug reports and feature requests

Development Setup

git clone https://github.com/kasperg3/TrajAllocPy.git
cd TrajAllocPy
pip install -e .
python -m pytest tests/ # Run tests

📄 License

This project is licensed under the MIT License.

🆘 Support

• Issues: GitHub Issues
• Email: kaspergrontved@gmail.com
• Documentation: See examples and docstrings for detailed API usage

🔗 Related Projects

• CoverageTasks: Dataset format for coverage task problems
• Coverage Tasks Dataset: Benchmark problems for evaluation

---

TrajAllocPy - Efficient, decentralized task allocation for autonomous robot teams! 🤖✨