New approach solves complex control problems with quantified constraints
Solving quantified constraint satisfaction problems with applications to control
Logic in Computer Science
Summary
Many control problems, like making sure a robot moves safely or designing controllers, can be described using constraints with mathematical 'for all' and 'there exists' statements. The authors developed a way to accurately find all possible solutions to these complex problems, even when the constraints have many layers of these statements. Their method uses a technique called set inversion combined with local checks to approximate the complete solution set. This helps better understand and solve control tasks that were previously hard to handle fully.
What this means in practice
- •For control system engineers: Accurately characterize the full range of control system behaviors, improving robust controller design under complex constraints.
- •For robotics developers: Improve motion planning by computing comprehensive safe paths using precise solutions to layered quantified constraints.
Authors
Éric Goubault, Nuwan Herath Mudiyanselage, Sylvie Putot
Abstract
Many problems in control can be expressed as quantified constraints, such as robust forward and backward reachability, synthesis of controllers, solutions to motion planning problems. In this paper, we develop a method for computing inner and outer approximations of global solutions to very general quantified constraints, generalizing widely the state of the art on similar problems, usually restricted to at most one alternation of quantifiers or to local solutions. By global solutions, we mean characterizing accurately the entire set of solutions, within some prescribed bounds. For this, our approach uses a set inversion technique relying on oracles for set inclusion using local solutions to related quantified reachability problems. We exemplify the approach throughout the paper on different examples related to control problems.