NDLI: Efficient Geometric Operations on Convex Polyhedra, with an Application to Reachability Analysis of Hybrid Systems

Please wait, while we are loading the content...

Efficient Geometric Operations on Convex Polyhedra, with an Application to Reachability Analysis of Hybrid Systems

Content Provider	Springer Nature Link
Author	Hagemann, Willem
Copyright Year	2015
Abstract	We present a novel representation class for closed convex polyhedra, where a closed convex polyhedron is represented in terms of an orthogonal projection of a higher dimensional $$\mathcal{H}$$ -polyhedron. The idea is to treat the pair of the projection and the polyhedron symbolically rather than to compute the actual described polyhedron. We call this representation a symbolic orthogonal projection, or a sop, for short. We show that fundamental geometrical operations, like affine transformations, intersections, Minkowski sums, and convex hulls, can be performed by simple block matrix operations on the representation. Due to the underlying $$\mathcal{H}$$ -polyhedron, linear programs can be used to evaluate sops, e.g. the usage of template matrices easily yields tight over-approximations. Beyond this, we will also show how linear programming can be used to improve these over-approximations by adding additional supporting half-spaces, or even facet-defining half-spaces, to the over-approximation. On the other hand, we will also discuss some drawbacks of this representation, e.g. the lack of an efficient method to decide whether one sop is a subset of another sop, or the monotonic growth of the representation size under geometric operations. The second part deals with reachability analysis of hybrid systems with continuous dynamics described by linear differential inclusions and arbitrary affine maps for discrete updates. The invariants, guards, and sets of reachable states are given as convex polyhedra. First, we present a purely sop-based reachability algorithm where various geometric operations are performed exactly. Due to the monotonic growth of the representation size of the sops, this algorithm is not suited for practical applications. Then we propose a combination of the sop-based algorithm with a support function based reachability algorithm. Accompanied by some simple examples, we show that this combination results in an efficient reachability algorithm of better accuracy than pure support function based algorithm. We also discuss the current limitations of the proposed techniques and chart a path forward which might help us to solve linear programs over huge sops.
Starting Page	283
Ending Page	325
Page Count	43
File Format	PDF
ISSN	16618270
Journal	Mathematics in Computer Science
Volume Number	9
Issue Number	3
e-ISSN	16618289
Language	English
Publisher	Springer Basel
Publisher Date	2015-09-23
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mathematics Computer Science
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A CSP Versus a Zonotope-Based Method for Solving Guard Set Intersection in Nonlinear Hybrid Reachability

Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces

Some aspects of reachability for parabolic boundary control problems with control constraints

An Efficient Simplex Coverability Algorithm in E2 with Application to Stochastic Sequential Machines

Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra

A CSP versus a zonotope-based method for solving guard set intersection in nonlinear hybrid reachability

An efficient compact quadratic convex reformulation for general integer quadratic programs

Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra

Application of Reachability Analysis for Stochastic Hybrid Systems to Aircraft Conflict Prediction

Efficient Geometric Operations on Convex Polyhedra, with an Application to Reachability Analysis of Hybrid Systems

Similar Documents

A CSP Versus a Zonotope-Based Method for Solving Guard Set Intersection in Nonlinear Hybrid Reachability

Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces

Some aspects of reachability for parabolic boundary control problems with control constraints

An Efficient Simplex Coverability Algorithm in E2 with Application to Stochastic Sequential Machines

Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra

A CSP versus a zonotope-based method for solving guard set intersection in nonlinear hybrid reachability

An efficient compact quadratic convex reformulation for general integer quadratic programs

Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra

Application of Reachability Analysis for Stochastic Hybrid Systems to Aircraft Conflict Prediction

Efficient Geometric Operations on Convex Polyhedra, with an Application to Reachability Analysis of Hybrid Systems