Graph Based Planning with Guarantees

This thesis presents two graph-based methods with formal guarantees for motion planning and routing. First, the invariant-set motion planner (ISMP), which uses constraint admissible positive invariant (CAPI) sets of closed-loop dynamics, is adapted for spacecraft attitude planning to avoid moving keep-out zones. Contributions include time bounds for maneuvers via exponential stability, a single-stage reachability graph from one-step backward reachable CAPI sets, and its multi-stage expansion to certify node safety over time. Simulations verify safe attitude control with moving obstacles. Second, we formulate a convex optimization problem over a network for evacuation planning with operational constraints such as helicopter capacity and route availability. When full evacuation is infeasible, a formal notion of blamelessness ensures ethical priorities are respected. The linear program (LP) enforces blamelessness and fuel-optimal routing via convex weighting, embedding ethical decision-making into autonomous control.