Using hash tables to manage the time-storage complexity in a point location problem: Application to explicit model predictive control

被引：66

作者：

Bayat, Farhad ^{[1
]}

Johansen, Tor Arne ^{[2
]}

Jalali, Ali Akbar ^{[1
]}

机构：

[1] Iran Univ Sci & Technol, Dept Elect Engn, Tehran 1684613114, Iran

[2] Norwegian Univ Sci & Technol, Dept Engn Cybernet, N-7491 Trondheim, Norway

来源：

AUTOMATICA | 2011年 / 47卷 / 03期

关键词：

Point location; Explicit model predictive control; Computational complexity; Data structures; MPC; ALGORITHM;

D O I：

10.1016/j.automatica.2011.01.009

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The online computational burden of linear model predictive control (MPC) can be moved offline by using multi-parametric programming, so-called explicit MPC. The solution to the explicit MPC problem is a piecewise affine (PWA) state feedback function defined over a polyhedral subdivision of the set of feasible states. The online evaluation of such a control law needs to determine the polyhedral region in which the current state lies. This procedure is called point location; its computational complexity is challenging, and determines the minimum possible sampling time of the system. A new flexible algorithm is proposed which enables the designer to trade off between time and storage complexities. Utilizing the concept of hash tables and the associated hash functions, the proposed method solves an aggregated point location problem that overcomes prohibitive complexity growth with the number of polyhedral regions, while the storage-processing trade-off can be optimized via scaling parameters. The flexibility and power of this approach is supported by several numerical examples. (c) 2011 Elsevier Ltd. All rights reserved.

引用

页码：571 / 577

页数：7

共 21 条

[1] An optimal algorithm for approximate nearest neighbor searching in fixed dimensions [J].

Arya, S ;

Mount, DM ;

Netanyahu, NS ;

Silverman, R ;

Wu, AY .

JOURNAL OF THE ACM, 1998, 45 (06) :891-923

[2] EFFICIENT ON-LINE COMPUTATION OF CONSTRAINED OPTIMAL CONTROL [J].

Baotic, Mato ;

Borrelli, Francesco ;

Bemporad, Alberto ;

Morari, Manfred .

SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2008, 47 (05) :2470-2489

[3] The explicit linear quadratic regulator for constrained systems [J].

Bemporad, A ;

Morari, M ;

Dua, V ;

Pistikopoulos, EN .

AUTOMATICA, 2002, 38 (01) :3-20

[4] Model predictive control based on linear programming - The explicit solution [J].

Bemporad, A ;

Borrelli, F ;

Morari, M .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2002, 47 (12) :1974-1985

[5]

Borrelli F, 2001, IEEE DECIS CONTR P, P1187, DOI 10.1109/CDC.2001.981046

[6] Set Membership approximation theory for fast implementation of Model Predictive Control laws [J].

Canale, M. ;

Fagiano, L. ;

Milanese, M. .

AUTOMATICA, 2009, 45 (01) :45-54

[7]

Christophersen Frank J., 2007, Proceedings of the European Control Conference 2007 (ECC), P2360

[8]

Cormen T., 2001, Introduction to Algorithms

[9] Approximate explicit receding horizon control of constrained nonlinear systems [J].

Johansen, TA .

AUTOMATICA, 2004, 40 (02) :293-300

[10] Approximate explicit constrained linear model predictive control via orthogonal search tree [J].

Johansen, TA ;

Grancharova, A .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2003, 48 (05) :810-815

← 1 2 3 →