Ant Colony Optimisation (ACO) for Robot Path Planning

This report presents the visualisations and analysis of using ACO to address NP-hard complexity within Robot Path Planning problems.
Explore the docs »

View Demo · Report Bug · Request Feature

Table of Contents

1. About The Project
   • Built With
2. Getting Started
   • Prerequisites
   • Installation
3. Usage
4. Roadmap
5. Contributing
6. License
7. Contact
8. Acknowledgments

About The Project

Why robot path planning matters: Picture a robot in your local warehouse, deftly weaving through stacks of boxes to fulfill your online shopping orders. Or imagine self-driving cars effortlessly navigating complex city streets. It's all about efficient path planning! 📦🚗

Robot path planning is like a GPS for robots. It helps them find the best way from A to B while dodging obstacles, saving time, and conserving energy. It's the brain behind the bots!

Enter Ant Colony Optimisation! Now, here's where it gets exciting. We're introducing ACO, a nature-inspired algorithm that mimics how ants find the shortest path to food. 🐜🍔

ACO is our robot's secret sauce. It's like giving them a sixth sense for navigating tricky terrains. By laying down 'virtual pheromones,' our robots learn and adapt, discovering the optimal routes in changing environments.

A glimpse at the artificial ant colony

Take a look at the final outcome of the work!

• 🎞️ Above animation visualises how the artificial ant colony navigate in a world full of obstacles.
• 🧀 Their goal is to identify the best (shortest and obstacle-free) route from their nest 🟢 to the food resources 🔴.
• ⛵ Exploration: They firstly bravely explore many possible routes because of no prior knowledge of the world.
• 🧔 Learn from excellent peers: Then they quickly learn from their past experiences.
• 🥇 Team work wins! Eventually, all of them merge on the optimal route!

(back to top)

How it works

• 🐜 Ant Colony Optimization (ACO) is like a picnic adventure for ants!
• 🥪 Ants need to find the shortest path to their favorite sandwich.
• 🗺️ Many paths to choose from, no GPS for ants!
• 🚶‍♂️ Ants leave scented breadcrumbs called 'pheromones' as they explore.
• 👃 Strong pheromone smell means "This way to the sandwich!"
• 🚶‍♀️ Other ants follow the strong pheromone trail.
• 💼 More ants travel the same path, making the trail even stronger.
• 🛤️ Ants converge on the shortest, most efficient route.
• 🤖 ACO mimics this natural process to solve complex problems for computers.
• 🤯 Helps robots find their way through mazes and optimises delivery routes.
• 🌎 Nature's way of showing us how to navigate the world, one picnic at a time! 🐜🥪🗺️

Getting started

Theory

Extensions:

• Ant Colony System
• Elitist Ant System
• Max-min Ant System

Mapping envrionment

Grid mapping method--discretisation of real world scenarios

Hyper-parameters optimisation

Its performance and rate of convergence are sensitive to the chosen parameter values, and especially to the value of the pheromone evaporation rate.

Test and results

Test Map

Results

Performance analysis

Archived Logs

The following is archived records of edit history.

Update dates & details

Ver. 17 Mar 2022

• Bug cleared
• No obstacles in the map

  numAnts = 17;
  numGen = 20;
  

• To ensure to find the diagonal-shortest path, deployed precedent parameters

Ver. 20 Mar 2022

• Added obstacles to the map

  gripMap(2:9, 5) = 1;
  

  • Ran well, but need to improve the accuracy and stability

• Solved a fail-to-detect-obstacles issue

  • When using the Delta_r2r(arr) function, globalDelta stored obstacles in the array by mistake.
  • Bug source still not found