Home > mpt > extras > control > optmerge > mpt_optMergeDivCon.m

mpt_optMergeDivCon

PURPOSE

===============================================================================

SYNOPSIS

function [PAmer, colorMer] = mpt_optMergeDivCon(PA, Opt)

DESCRIPTION

```===============================================================================

Title:    mpt_optMergeDivCon

Project:  Optimal merging of a set of polyhedra using divide and
conquer strategy

Input:    PA: polyhedral array
Opt: Options with the following fields
.color: color of polyhedra
This is an integer 1,2,... The algorithm will merge
polyhedra with the same color. If color is not specified, it
is assumed to be 1 for all polyhedra.
the set of polyhedra (the so called domain) the problem is
defined in. If not given, the algorithm assumes the domain is
given by the hull (or envelope if the hull computation fails)
of PA.
.PAcompl:
polyhedral array that is within the domain and not
in PA - it is the so called complement. If not specified,
the algorithm assumes PAcompl is empty. Then the
complement is filled up optimally by the merging algorithm.
Refer also to the second remark below.
.verbose:
0: silent (=default)
1: verbose only important information
2: verbose everything
.algo:
0: overlapping merging (boolean minimization)
[1, inf]: optimal merging, with the given upper bound on nodes
(default is inf)
.maxHA: [1, inf]: maximal number of hyperplanes for which we
can compute the markings for sub1 or 2 (default inf)
.maxHA_sub1and2: [1, inf]: maximal number of hyperplanes for
which we can compute the markings for the combined problem
of sub1 and 2 (default maxHA+10)
.divideSub:
0: use an artificial hyperplane parallel to axis of the
coordinate with the longest edge of the bounding box to
divide a problem into 2 subproblems (fast)
1: go through all hyperplanes, choose the one that minimizes
the cost abs(# GL in Sub1 - # GL in Sub2) + # GL in Sub1 + # GL in Sub2 (slow) (=default)
.tol.simplifyHA: 1-norm of cluster of hyperplanes from center
clustering is done in order to simplify the hyperplane
arrangement and to thus reduce the complexity of the
solution. Clustering is beneficial, if we have many
hyperplanes that are almost the same.  Then we can take a
weighted average of such a cluster. When the tolerance is
0, no clustering is performed.

Output:       PAmer: merged polyhedra array
colorMer: colors with the following fields
.Reg:   color of each region
.Table: regions with the same color

Author:       Tobias Geyer <geyer@control.ee.ethz.ch>

Remarks:      some important remarks and explanations:
* the input polyhedral array may be overlapping
First, we identify all existing hyperlanes, remove unecessary ones,
and compute then the markings in the hyperplane arrangement. Then,
we identify the colors of the cells in the arrangement by chosing
one cell, getting the center of it and then identifying the
polyhedron in PA that includes the center. Thus overlaps do not matter.
* the input polyhedral array may contain small holes
Holes may always occur (also in the hyperplane arrangement based on
which we merge). Holes are assigned to 'don't cares' and are filled
with neighbouring polyhedra. Acutally, to reduce complexity, we remove
very small cells (say with radii < 1e-5) from the arrangement. These
are then 'don't cares'.
* we keep in the hyperplane arrangment only hyperplanes that are facets
of polyhedra with different colors
These hyperplanes separate the colors. Shouldn't we keep also the other
hyperplanes? No, as we are allowing for overlapping polyhedra (merging
based on boolean minimization), we only need these 'dividing' hyperplanes.
polyhedra. Proof?
* we plan to later allow to also simplify the hyperplanes, i.e. to
aggregate similar hyperplanes in only one.

History:      date        ver.    subject
2004.06.16  1.0     initial version based on mpt_iterMerge
2004.07.14  1.1     divide problem into subproblems using 'best' hyperplane
2005.07.20  1.2     improved help

espresso or merge5,
plotPaCol,
mpt2cell,
MPT toolbox

Contact:      Tobias Geyer
Automatic Control Laboratory
ETH Zentrum, CH-8092 Zurich, Switzerland

geyer@control.ee.ethz.ch

Comments and bug reports are highly appreciated

===============================================================================```

CROSS-REFERENCE INFORMATION

This function calls:
• horzcat HORZCAT Concatenation of MPTCTRL objects
• length LENGTH Returns number of regions over which the explicit control law is defined
• bounding_box BOUNDING_BOX Compute a bounding box for a given polytope
• dimension DIMENSION Returns dimension of the given polytope
• double DOUBLE Function used to access internal properties of the given polytope
• end END Returns the last element in a given polytope array
• envelope ENVELOPE Computes envelope of n polytopes
• extreme EXTREME Calculates extreme points of a given polytope
• horzcat HORZCAT Concatenates polytopes into a polytope array
• hull HULL Convex hull of n polytopes
• isfulldim ISFULLDIM Checks if a polytope is full dimensional
• length LENGTH Returns number of elements in a polytope array
• or OR Convex union of n polytopes
• polytope POLYTOPE Default constructor for the POLYTOPE object
• size SIZE Returns size of the given polytope object
• unique UNIQUE Removes redundant entries from a polytope array
• intersectHP1 Tobias Geyer, 2003-2004