Introduction
Controlling "switched hybrid systems"—which integrate continuous physical dynamics with discrete logical modes—presents a significant challenge in robotics and aerospace. Traditional Domain Predictive Control (DPC) approaches utilize AI planning but often suffer from two critical limitations: input discretization and imprecise goal reaching. Discretizing continuous inputs (e.g., thruster force) leads to a state-space explosion, while the inability to select exact intermediate values prevents the system from reaching specific target coordinates precisely.
This paper introduces Symbolic Domain Predictive Control (DPC), an extension that replaces fixed discrete control inputs with continuous, bounded input sets. By representing reachable states as geometric sets, the authors enable planners to find precise control strategies while significantly reducing the search space.
Methodology: Planning with Symbolic Sets
The core innovation of this work is the transition from point-based planning to planning with symbolic sets, specifically zonotopes.
Zonotopes and Reachability
A zonotope is a centrally symmetric polytope represented by a center point and a set of vectors called generators. They are computationally efficient for linear transformations, making them ideal for modeling how possible states evolve under physical laws.
By treating control as a reachability problem, the planner determines the entire volume of space the system could occupy at a given time step. If the goal point lies within this reachable volume, a valid control signal is guaranteed to exist.
Minkowski Sums and Continuous Inputs
To incorporate continuous input ranges (e.g., a thruster providing force between 2.24N and 10N), the authors employ the Minkowski sum. This operation "stretches" the current zonotope to encompass all states reachable by any valid input within the bounded range. This allows a single "symbolic action" to cover an infinite number of continuous input values, preventing the branching factor of the search tree from exploding.
Goal Checking and Heuristics
To verify if a goal is reachable, the authors use a Moore-Penrose pseudo-inverse to check if the goal point is contained within the symbolic reachable set. They also developed a specialized heuristic that calculates the distance between the zonotope and the goal, using a weighting matrix to prioritize critical variables like velocity or position.
Experimental Evaluation: Orbital Maneuver Domain
The approach was evaluated using a simulated Orbital Maneuver Domain. A 1000kg satellite must compensate for separation errors post-launch. The satellite features a single thruster with a continuous range (2.24N to 10N) and must perform "slew" rotations to orient the thruster along different axes. The benchmark included seven initial states ($P_1$ through $P_7$) with varying position and velocity errors.
Key Results
The symbolic approach demonstrated significant improvements over standard Breadth-First Search (BFS):
- Search Efficiency: In a representative problem ($P_4$), BFS explored over 1.6 million nodes. In contrast, the symbolic greedy search (using the $L_1$ norm) reached the solution in only 348 nodes.
- Precision: Because the plan identifies a symbolic set containing the goal, the exact sequence of continuous inputs required to hit the target with mathematical precision can be back-calculated.
- Feasibility: The generated control signals successfully respected physical thruster limits while managing complex maneuvers, such as alternating between thrusting and rotation phases.
Discussion and Future Directions
While Symbolic DPC offers a powerful framework for hybrid systems, it currently relies on linear or linearized dynamics. Extending this to highly non-linear systems remains a challenge. Additionally, while the approach is efficient in obstacle-free spaces, incorporating obstacle avoidance is computationally intensive due to the complexity of zonotope-obstacle intersection checks. Future work may involve "over-approximation" techniques to manage the increasing complexity of zonotope generators in long-duration plans.
Summary updated