Tags:Hybrid Planning, Linear Hybrid Systems and Optimization
Abstract:
Planning in hybrid systems with both discrete and continuous control variables is important for dealing with real-world applications such as extra-planetary exploration and multi-vehicle transportation systems. Meanwhile, generating high-quality solutions given certain hybrid planning specifications is crucial to building high-performance hybrid systems. However, given hybrid planning is challenging in general, most methods use greedy search that is guided by various heuristics, which is neither complete or optimal and often falls into blind search towards an infinite-action plan. In this paper, we present a hybrid automaton planning formalism and propose an optimal approach that encodes this planning problem as a Mixed Integer Linear Program (MILP) by fixing the action number of automaton runs. By leveraging an efficient MILP optimizer, our method is able to generate provably optimal solutions for complex mixed discrete-continuous planning problems within a reasonable time. We demonstrate this by benchmarking our encoding against Scotty in the Mars exploration domains, air refueling domains, and the truck-and-drone delivery domains.
Optimal Mixed Discrete-Continuous Planning for Linear Hybrid Systems