|  | |
| --- | |
| license: mit | |
| tags: | |
| - pathfinding | |
| - simulation | |
| - reinforcement-learning | |
| - pyqt5 | |
| - autonomous-agents | |
| - ai-education | |
| - vacuum-cleaner | |
| - search-algorithms | |
| - bfs | |
| - a-star | |
| - manhattan-distance | |
| - euclidean-distance | |
| - chebyshev-distance | |
| - turn-cost | |
| - performance-metrics | |
| - >- | |
| - turn-cost - performance-metrics - algorithm-comparison - visualization-tool | |
| - educational-software - python - artificial-intelligence - | |
| robotics-simulation - grid-world - obstacle-avoidance - | |
| multi-algorithm-framework - heuristic-evaluation - computational-efficiency - | |
| node-expansion - path-optimization - interactive-learning - | |
| real-time-simulation - gui-application - academic-project - research-tool - | |
| algorithm-visualization - performance-analysis - turn-penalty - cost-analysis | |
| - exploration-strategies - search-techniques - autonomous-navigation - | |
| intelligent-agents - simulation-environment | |
| - >- | |
| - path-planning - heuristic-search - comparative-analysis - | |
| educational-resource - ai-simulation - robotics-education - | |
| algorithm-benchmarking - performance-metrics - visualization-framework - | |
| interactive-demonstration - learning-tool - academic-resource - | |
| simulation-software - ai-visualization - pathfinding-algorithms - | |
| search-methods - heuristic-functions - turn-cost-modeling - | |
| performance-evaluation - algorithm-testing - simulation-platform - | |
| educational-application - ai-demonstration - robotics-simulation - | |
| autonomous-systems - intelligent-systems - search-strategies - | |
| path-optimization - performance-comparison - heuristic-performance - | |
| algorithm-efficiency - simulation-tool - visualization-software - | |
| educational-software - ai-education - robotics-education - | |
| pathfinding-visualization - algorithm-visualization - | |
| performance-visualization - turn-cost-visualization - | |
| multi-algorithm-comparison - interactive-simulation - real-time-visualization | |
| - gui-simulation - pyqt5-application - python-simulation - grid-simulation - | |
| obstacle-navigation - dirty-cell-cleaning - autonomous-cleaning - | |
| vacuum-simulation - search-algorithm-comparison - heuristic-comparison | |
| --- | |
| --- | |
| title: Vacuum Cleaner Search Simulation | |
| emoji: 🏠 | |
| colorFrom: blue | |
| colorTo: green | |
| pinned: false | |
| license: mit | |
| --- | |
| # Vacuum Cleaner Search Simulation | |
| An interactive simulation that demonstrates various search algorithms for vacuum cleaner pathfinding in a grid environment. | |
| ## 🎯 Overview | |
| This application visualizes how different search algorithms navigate through a grid to find and clean dirty cells while avoiding obstacles. The simulation compares the performance of BFS and A* search with different heuristics. | |
| ## 🧠 Features | |
| - **Multiple Search Algorithms**: | |
| - BFS (Breadth-First Search) | |
| - A* with Manhattan distance heuristic | |
| - A* with Euclidean distance heuristic | |
| - A* with Chebyshev distance heuristic | |
| - **Interactive Controls**: | |
| - Reset environment | |
| - Step-by-step simulation | |
| - Auto-run mode | |
| - Turn cost toggle (adds cost for direction changes) | |
| - **Real-time Metrics**: | |
| - Steps taken and total cost | |
| - Nodes explored and expanded | |
| - Computation time | |
| - Algorithm performance comparison | |
| ## 🎮 How to Use | |
| 1. **Setup the Environment**: | |
| - The grid automatically generates with obstacles (blue) and dirty cells (red) | |
| - The vacuum starts at a random clean position | |
| 2. **Choose Algorithm**: | |
| - Select from the dropdown menu (BFS, A* Manhattan, A* Euclidean, A* Chebyshev) | |
| 3. **Configure Options**: | |
| - Toggle "Turn Cost" to enable/disable penalty for direction changes | |
| - Turn cost adds +0.5 for each 90° direction change | |
| 4. **Run Simulation**: | |
| - Click **Next** to advance one step | |
| - Click **Run** for continuous automatic execution | |
| - Click **Stop** to pause automatic execution | |
| - Click **Reset** to generate a new environment | |
| ## 🏗️ Technical Details | |
| ### Search Algorithms | |
| - **BFS**: Explores all directions equally, guarantees shortest path | |
| - **A* Manhattan**: Uses city-block distance heuristic (`|x1-x2| + |y1-y2|`) | |
| - **A* Euclidean**: Uses straight-line distance heuristic | |
| - **A* Chebyshev**: Uses chessboard distance heuristic (`max(|x1-x2|, |y1-y2|)`) | |
| ### Cell Types | |
| - 🟡 **Yellow**: Clean cells | |
| - 🔴 **Red**: Dirty cells (need cleaning) | |
| - 🔵 **Blue**: Obstacles (block movement) | |
| - 🟢 **Green**: Explored cells | |
| - 🟠 **Orange**: Current path | |
| ### Performance Metrics | |
| - **Nodes Explored**: Total unique positions visited | |
| - **Nodes Expanded**: Total nodes processed by algorithm | |
| - **Computation Time**: Time taken to find paths | |
| - **Turn Cost**: Additional cost from direction changes | |
| ## 📊 Algorithm Comparison | |
| The application tracks and compares: | |
| - Average nodes expanded per run | |
| - Average computation time | |
| - Efficiency across different heuristics | |
| Typically: | |
| - **BFS** explores more nodes but finds optimal paths | |
| - **A* Euclidean** is often most efficient for direct paths | |
| - **A* Chebyshev** may explore more nodes in grid environments | |
| ## 🚀 Local Development |