Skip to content

README.md

Latest commit

 

History

History
184 lines (133 loc) · 8.86 KB

README.md

File metadata and controls

184 lines (133 loc) · 8.86 KB
Raw

AI-Based Drone Delivery Route Planner — Jaipur Airspace

MIT License Streamlit App Python Version Google OR-Tools

Description

This project is an AI-Based Conflict-Aware Path Recommendation and Fleet Optimization System designed for the Jaipur Airspace in India. The application targets the challenge of drone logistics in complex, dense urban environments where routes must navigate around static obstacles (buildings) and regulated airspaces (No-Fly and Restricted Zones).

Features

  • Jaipur Airspace Classification: Integration of hand-crafted GeoJSON maps with 12 Red Zones (No-Fly) and 20 Yellow Zones (Restricted) representing airport runways, military bases, hospitals, and schools.
  • GIS Building Footprints: Downloads and parses real building data from OpenStreetMap (OSM) via the OSMnx API.
  • Stochastic Density Simulation: Procedural Gaussian-clustered building generator adding 1,079 simulated obstacles with normal height distributions matching urban profiles.
  • Multi-Algorithm Pathfinder: Highly optimized search engines including A* Pathfinder, Dijkstra's algorithm, Greedy Best-First Search, Breadth-First Search (BFS), and Depth-First Search (DFS).
  • Heuristic Navigation & Smoothing: Uses an admissible Octile distance heuristic on an 8-directional 401×400 grid combined with a String-Pulling smoothing algorithm that eliminates 96% of redundant waypoints.
  • Multi-Drone Fleet Optimizer: Solves the Vehicle Routing Problem (VRP) with Google OR-Tools using A*-safe cost matrices, payload constraints, and battery ranges.
  • Interactive Dashboards: Streamlit dashboards featuring interactive 2D maps (Folium) and 3D extruded visualizations (PyDeck).

Background Context

Developed as part of the B.Tech (AI&DS) program at Gati Shakti Vishwavidyalaya, Vadodara, this system simulates safe urban cargo delivery vectors, taking into account drone limits, payload weight, speed, and vertical and horizontal safety buffers.

Visuals

The project generates several types of visualizations:

  1. 2D Folium Map: Renders color-coded airspace zones (Red for no-fly, Yellow for restricted) and building footprints with popup metadata. Users can click on the map to interactively define pickup/drop coordinates.

  2. 3D PyDeck Visualization: Extrudes building geometries into 3D columns according to their heights and shows the calculated drone flight vector floating at the specified cruise altitude.

  3. Zone Analysis Chart: Generates static map plots of the operational area showing spatial zone distribution (saved as output/zone_analysis_map.png).

    Jaipur Airspace Zone Analysis Map

Installation

Requirements

  • Python 3.10 or higher
  • pip (Python Package Installer)
  • Virtualenv (optional but recommended)

Step-by-Step Setup

  1. Clone the Repository:

    git clone https://github.com/Vishvendra47/droneIQ.git
cd droneIQ

  2. Initialize a Virtual Environment:

    # Create environment
python -m venv venv

# Activate environment (Mac/Linux):
source venv/bin/activate

# Activate environment (Windows):
venv\Scripts\activate

  3. Install Dependencies:

    pip install -r requirements.txt

    (Note: The main deployment dashboard does not require installing OSMnx since it relies on pre-computed geojson files).

Usage

The project is designed to run either as a unified web dashboard or as independent command-line processing pipeline steps.

Running the Web Dashboard (Streamlit)

Launch the primary entry point to load both the Single-Drone Navigation and Multi-Drone Fleet Optimizer modes:

streamlit run app.py

Open http://localhost:8501 in your browser.

Running Pipeline Steps Independently

You can execute each stage of the data-processing pipeline individually:

# Step 1: Parse and validate the GeoJSON airspace map
python src/step1_analyze_map.py

# Step 2: Download real building footprints from OpenStreetMap (requires internet + OSMnx)
python src/step2_fetch_buildings.py

# Step 3: Generate simulated buildings using Gaussian clusters
python src/step3_simulate_buildings.py

# Step 4: Merge zones and buildings into the jaipur_master_map.geojson
python src/step4_merge_master.py

# Step 5: Test pathfinding algorithms from CLI
python src/step5_pathfinder.py

# Step 6: Launch single-drone Streamlit dashboard standalone
streamlit run src/step6_dashboard.py

# Step 7: Test fleet routing with Google OR-Tools VRP Solver
python src/step7_fleet_optimizer.py

# Step 8: Launch fleet optimization Streamlit dashboard standalone
streamlit run src/step8_fleet_dashboard.py

Configurable Parameters

The dashboard sidebar allows the operator to adjust the following variables:

Parameter Range Default Purpose
Flight Altitude 20–120m 60m Cruise altitude of the drone.
Flight Speed 10–100 km/h 50 km/h Cruise speed used for travel time estimation.
Vertical Safety Margin 0–30m 10m Min clearance above buildings (buildings $\ge$ altitude - margin are blocked).
Building Buffer 0–20m 3m Min horizontal gap around building boundaries.
Drone Capacity 0.5–20 kg 2.5 kg Payload weight capacity limit per drone in fleet mode.
Battery Range Rate Fixed 3 km/% Battery consumption rate (100% capacity = 300 km range).

Cost Matrix Computation (Vehicle Routing Problem)

In multi-drone fleet mode, Google OR-Tools solves the VRP based on an A*-safe cost matrix rather than straight-line (Haversine) distances:

  1. For $N$ locations (1 depot + $N-1$ drops), $C(N, 2)$ pairs of paths are generated.
  2. For each pair, the A* Pathfinder is run. If the route crosses a red zone, blocked yellow zone, or tall building, it detours.
  3. The matrix is populated with symmetric A*-safe distances. If no path is found, a high cost value (99999) is assigned.
  4. Google OR-Tools models the fleet routing with capacity limits, battery constraints, and aGuided Local Search metaheuristic to find the optimal assignment.

Support

If you encounter issues, require assistance, or have questions, please use the following resource:

  • GitHub Issue Tracker: Submit bug reports, feature requests, or queries directly at GitHub Issues.

Roadmap

Future developments planned for this system include:

  • Dynamic Weather Integration: Adjust path costs and battery discharge rates dynamically based on real-time wind speed, direction, and precipitation data.
  • Hybrid Genetic Pathfinder: Introduce sample-based algorithms (like RRT* or Genetic Algorithms) for continuous airspace routing rather than grid-based pathfinding.
  • MAVLink / PX4 Telemetry Sync: Add real-world telemetry connection support to export flight paths directly to drone autopilots.
  • Dynamic Obstacle Avoidance: Integrate dynamic no-fly zones that change based on localized events (e.g., temporary VIP movement or accidents).

Contributing

We are open to academic contributions, refactoring suggestions, and general pull requests.

Getting Started with Development

  1. Fork this repository on GitHub.
  2. Create a local branch representing your work: 
    git checkout -b feature/my-new-feature
  3. Make sure to preserve all existing code comments and modular steps in src/ to ensure documentation integrity.
  4. Run scripts to verify changes don't break existing steps: 
    python src/step5_pathfinder.py
python src/step7_fleet_optimizer.py
  5. Submit a Pull Request explaining the rationale behind your additions or modifications.

Acknowledgment

References & Literature

  1. Hart, P.E., Nilsson, N.J., Raphael, B. — A formal basis for the heuristic determination of minimum cost paths. IEEE, 1968.
  2. Dijkstra, E.W. — A note on two problems in connexion with graphs. Numerische Mathematik, 1959.
  3. Dantzig, G.B., Ramser, J.H. — The truck dispatching problem. Management Science, 1959.
  4. DGCA India — The Drone Rules, 2021. Ministry of Civil Aviation, Government of India.
  5. Karaman, S., Frazzoli, E. — Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research, 2011.

License

This project is licensed under the MIT License - see the LICENSE file for details.