Unified Mission Planner: Aircraft & Spacecraft Optimization

Constraint-based optimization framework using Google OR-Tools CP-SAT solver for optimal mission planning of both aircraft routes and spacecraft activity schedules with real-world constraints.

Comment

Inspiration

Real-world mission planning involves solving complex optimization problems with competing constraints and objectives. We were inspired by the challenge of creating a unified framework that elegantly handles two fundamentally different domains—aircraft routing and spacecraft scheduling—using a single optimization engine. This mirrors real operational scenarios where multiple assets must be planned simultaneously under resource constraints.

What it does

Our framework automatically optimizes missions for both aircraft and spacecraft:

Aircraft Module:

  • Plans optimal flight routes between waypoints
  • Respects no-fly zones using geofencing (Shapely polygons)
  • Manages battery constraints (300 Wh capacity, 120W power draw)
  • Achieves OPTIMAL 199-second routes with 100% reliability (Monte Carlo validated)

Spacecraft Module:

  • Schedules observations and downlinks based on satellite visibility windows
  • Handles complex mission constraints: battery, duty cycles, contact windows
  • Optimizes activity selection to maximize value
  • Achieves OPTIMAL schedules: 65 of 96 activities, zero constraint violations

How we built it

  1. Problem Formulation: Analyzed both problem domains and identified common patterns (activities, time windows, resource constraints)

  2. Unified Solver: Implemented UnifiedCPSATEngine using Google OR-Tools CP-SAT constraint programming solver

  3. Domain Adapters: Created separate adapters (Adapter Pattern) to map domain-specific problems into unified activity-based model

  4. Constraint Modeling: Implemented proper CP-SAT constraints using OnlyEnforceIf() for conditional logic, avoiding non-linear expressions

  5. Performance Optimization:

    • Removed N² transition graphs (112,560 → 2,048 constraints, 98% reduction)
    • Optimized time discretization (60s → 300s buckets)
    • Achieved 100x speedup

  6. Validation Framework: Built Monte Carlo analysis, route comparisons, and constraint violation checks

  7. Visualization: Created professional Matplotlib visualizations for routes, battery profiles, and timelines

Challenges we ran into

Challenge 1: Non-linear Constraint Bug

  • Problem: Solver returned UNKNOWN due to invalid constraint: e * in_bucket (variable multiplication)
  • Solution: Replaced with proper conditional constraints using OnlyEnforceIf()
  • Impact: Both solvers now achieve OPTIMAL

Challenge 2: Memory/Timeout Issues

  • Problem: Spacecraft solver timing out with 112,560 transition constraints
  • Solution: Removed unnecessary N² transition graphs, kept only OBS→DL transitions (2,048 constraints)
  • Impact: Solve time reduced from timeout to 0.3 seconds

Challenge 3: Complex Problem Formulation

  • Problem: Difficulty mapping domain-specific concepts to optimization model
  • Solution: Used adapter pattern for clean separation between domain and solver logic
  • Impact: Code became maintainable and extensible

Challenge 4: Reliability Validation

  • Problem: How to prove solution reliability in stochastic environment?
  • Solution: Implemented comprehensive Monte Carlo analysis (100 simulation runs)
  • Impact: Achieved 100% success rate with quantified battery margins

Accomplishments that we're proud of

✅ Dual OPTIMAL Solutions: Both aircraft and spacecraft solvers consistently achieve OPTIMAL status

✅ 100x Performance Improvement: Through intelligent constraint reduction and optimization

✅ 100% Reliability: Aircraft mission validated with Monte Carlo achieving 100% success rate

✅ Zero Constraint Violations: Spacecraft mission satisfies all battery and duty cycle constraints

✅ Professional Architecture: Clean code with proper design patterns (Adapter, separation of concerns)

✅ Comprehensive Validation: Monte Carlo analysis, route comparisons, battery experiments

✅ Production-Ready Quality: Professional visualizations, complete documentation, clean Git history

What we learned

  1. Constraint Programming Mastery: Deep understanding of how to properly model constraints in CP-SAT without non-linear expressions

  2. Performance is About Modeling: 98% performance improvement came from better problem formulation, not solver tuning

  3. Architecture Matters: Using adapter pattern and domain separation made code significantly more maintainable

  4. Validation is Critical: Comprehensive testing (Monte Carlo, statistical analysis) provides confidence in solutions

  5. Real-world Optimization: Balancing multiple competing objectives requires careful constraint hierarchy and objective design

  6. Time Discretization Trade-offs: Choosing appropriate time buckets (5-minute intervals) is crucial for both accuracy and performance

What's next for Unified Mission Planner: Aircraft & Spacecraft Optimization

Short-term Enhancements:

  • Add wind model for aircraft routing
  • Implement dynamic re-planning capabilities
  • Support for multi-aircraft/spacecraft coordination

Long-term Vision:

  • Extend to additional domains (ground vehicles, UAVs)
  • Real-time mission replanning under uncertainty
  • Integration with actual flight/orbital mechanics simulators
  • Cloud deployment for large-scale operations
  • Multi-objective optimization (cost, time, energy, risk)

Research Directions:

  • Machine learning for constraint prediction
  • Distributed solving for large problem instances
  • Robust optimization under uncertainty
  • Integration with IoT systems for live data

Built With

  • git
  • google-or-tools-9.0+-(cp-sat-solver)
  • matplotlib-(visualization)
  • numpy-(numerical-computing)
  • python-3.7+
  • shapely-(geospatial/geofencing)
Share this project:

Updates