#quantum ### Motivation Mission planning --> Routing and scheduling problems are crucial, lead of combinatorial optimization because of the large search space. > Plan the action of some agents to perform a set of tasks. TASK PLANNING/ WORKFLOW SCHEDULING Satisfiability part: - Can all the constraints be satisfied simultaneously? - limited time / limited resources ### STRIPS representation A way to describe planning problems: Stanford Research Institute Problem Solver. - Finite set of binary variables - State is described by the value of these variables at a given time. - Special States: Initial and Final - Initial State = Starting Values of all variables - Actions = How to move from one state to another. - Characterization of actions: - A condition / boolean formula, action is allowed in a state if this state satisfies the condition. Usually, the condition only depends on a few variables. - Action modifies the value of some variables - Final / Target States - Find a succession of actions that lead from the initial state to one of the target states. task must be completed whatever the final positions of the vehicles are STRIPS is itself a solver, GraphPlan provides better performances for STRIPS-like problems. GraphPlan has been improved and extended. Existing Techniques to solve STRIPS-like problems with planning graphs. --- Use [[Erdos Renyi Model]] to generate random graphs to create STRIPS instances. 1. [[Hamiltonian Path]], Probability [[Parameters]] for the hardest instance is p = (log n + log logn) / n 1. STRIPS instance work be 1. Vertex U, ON or OFF 2. Edge Activation, with preconditions U is ON and v is OFF to make it work 3. [[Vertex Coloring]] 3 coloring, hardest asymptotical case is not known precisely, by p = 5/n ![[Pasted image 20220113013012.png]] ![[Pasted image 20220113013051.png]]