Generative Planning for Hybrid Systems based on Flow Tubes
Hui X. Li, Brian C. Williams · 2009
When controlling an autonomous system, it is ineffi-cient or sometimes impossible for the human operator to specify detailed commands. Instead, the field of AI au-tonomy has developed goal-directed systems, in which human operators specify a series of goals to be accom-plished. Increasingly, the control of autonomous sys-tems involves performing a mix of discrete and contin-uous actions. For example, a typical autonomous under-water vehicle (AUV) mission involves discrete actions, like get GPS and set sonar, and continuous actions, like descend and ascend, which involve continuous dynam-ics of the vehicle. Accordingly, we develop a hybrid planner that determines a series of discrete and contin-uous actions that achieve the mission goals. In this paper, we describe a novel approach to solv-ing the generative planning problem for hybrid sys-tems, involving both continuous and discrete actions. The planner, Kongming1, incorporates two innovations. First, it employs a compact representation of all hy-brid plans, called a Hybrid Flow Graph, which com-bines the strengths of a Planning Graph for discrete ac-tions and Flow Tubes for continuous actions. Second, it encodes the Hybrid Flow Graph as a mixed logic lin-ear/nonlinear program, which it solves using an off-the-shelf solver. We empirically demonstrate that Kong-ming can efficiently plan for real-world scenarios that are based on science missions performed at the Mon-terey Bay Aquarium Research Institute (MBARI).