**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Optimal decision trees for point location in polytopic data sets - application to explicit MPC

Abstract

Explicit Model Predictive Control (EMPC) produces control laws defined over a set of polytopic regions in the state space. In this paper we present a method to create a binary search tree for point location in such polytopic sets, in order to provide a fast lookup of the control law corresponding to a given state. We use hyperplanes as decision criteria that are, contrary to previous works, not constrained to the boundaries of the polytopes. Each hyperplane is the solution of a mixed-integer optimization problem with two objectives: having the same number of polytopes on either side of the hyperplane and minimizing the number of polytopes cut by the hyperplane. Contrary to previous approaches, the method can be applied to polytopic sets where the polytopes are either adjacent with common facets (for classical EMPC) or separated in space (for suboptimal EMPC). There are two benefits using this approach: First, the method optimizes the balance of the tree. If a tree of the theoretically lowest possible depth (i.e. log2 depth) exists, the algorithm will find it, although the time to solve the optimization problem may become prohibitive for large problems. Second, the method provides an efficient evaluation of suboptimal EMPC policies since it allows to maximize the distance of the hyperplane to the closest polytope that is not intersected.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (36)

Related publications (46)

Related MOOCs (13)

Model predictive control

Model predictive control (MPC) is an advanced method of process control that is used to control a process while satisfying a set of constraints. It has been in use in the process industries in chemical plants and oil refineries since the 1980s. In recent years it has also been used in power system balancing models and in power electronics. Model predictive controllers rely on dynamic models of the process, most often linear empirical models obtained by system identification.

Binary tree

In computer science, a binary tree is a k-ary tree data structure in which each node has at most two children, which are referred to as the and the . A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root. Some authors allow the binary tree to be the empty set as well. From a graph theory perspective, binary (and K-ary) trees as defined here are arborescences.

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

Introduction to optimization on smooth manifolds: first order methods

Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).

Optimization: principles and algorithms - Linear optimization

Introduction to linear optimization, duality and the simplex algorithm.

Optimization: principles and algorithms - Linear optimization

Introduction to linear optimization, duality and the simplex algorithm.

Control systems operating in real-world environments often face disturbances arising from measurement noise and model mismatch. These factors can significantly impact the perfor- mance and safety of the system. In this thesis, we aim to leverage data to de ...

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling de ...

2023Many robotics problems are formulated as optimization problems. However, most optimization solvers in robotics are locally optimal and the performance depends a lot on the initial guess. For challenging problems, the solver will often get stuck at poor loc ...