# Towards a Scalable and Trustworthy Blockchain: IoT Use Case

Hajar Moudoud 13, Soumaya Cherkaoui 1, Lyes Khoukhi 2  1 Department of
Electrical and Computer Engineering, Université de Sherbrooke, Canada
2 GREYC CNRS, ENSICAEN, Normandie University, France
3 University of Technology of Troyes, France
{hajar.moudoud<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Recently, blockchain has gained momentum as a novel technology that gives rise
to a plethora of new decentralized applications ($e.g.$, Internet of Things
(IoT)). However, its integration with the IoT is still facing several problems
($e.g.$, scalability, flexibility). Provisioning resources to enable a large
number of connected IoT devices implies having a scalable and flexible
blockchain. To address these issues, we propose a scalable and trustworthy
blockchain (STB) architecture that is suitable for the IoT; which uses
blockchain sharding and oracles to establish trust among unreliable IoT
devices in a fully distributed and trustworthy manner. In particular, we
design a Peer-To-Peer oracle network that ensures data reliability,
scalability, flexibility, and trustworthiness. Furthermore, we introduce a new
lightweight consensus algorithm that scales the blockchain dramatically while
ensuring the interoperability among participants of the blockchain. The
results show that our proposed STB architecture achieves flexibility,
efficiency, and scalability making it a promising solution that is suitable
for the IoT context.

###### Keywords:

Blockchain, Internet of Things (IoT), Oracle, Sharding, Consensus.

##  I Introduction

With the widespread adoption of blockchain technology and global endorsement
of cryptocurrencies, it is expected that transaction traffic will skyrock [1].
According to [2], the worldwide adoption of blockchain technology is expected
to grow from 1.5 billion in 2018 to an estimated 15.9 billion by 2023; this
will lead to an exponential growth in the number of transactions. Giving the
inherent characteristics of nowadays blockchain ($i.e.$, extremely complex
computing, low latency, and lacking dynamic scalability), handling the
constantly growing number of transactions is becoming complex and very
laborious. Blockchain sharding is a concept that was proposed to improve the
blockchain scalability issue, which artificially partitions the workload of
one single transaction procession to several members working in parallel. This
separation brings about numerous advantages, including high flexibility, high
throughput, and high scalability. The first proposed blockchain sharding
solutions ($e.g.$, [3], [4], [5]) deploy and on-chain sharding using Byzantine
consensus protocol to improve the shards’ throughput and off-chain sharding
moving transactions off the blockchain. Despite their efficiency and
simplicity, these solutions have failed to meet the data validity required by
nowadays applications [6]. The reason is twofold: (1) with the increasing
number of members working on a single transaction, a malicious member can
compromise the work process, which may lead to security issues; and (2) any
minor mishandling of a transaction may lead to its loss.

Today blockchain applications enable various industry verticals, such as
supply chain management, healthcare, finance, and the Internet of Things
(IoT). In particular, the blockchain may play a role in how IoT connected
devices communicate and exchange information with each other. In this case, a
blockchain transaction is defined as the basic communication primitive to
exchange information among IoT connected devices. Handling a large number of
transactions coming from these devices, particularly when they have
heterogeneous security parameters, put the transaction reliability at risk,
and introduces new security challenges. For instance, a compromised IoT device
may deliver falsified information that will be stored permanently on the
blockchain. This may impact the reliability of the transactions, which in turn
affects the security of the blockchain.

There have been several researchers have tried to address the challenges of
using blockchain in an IoT context [7, 8]. For instance, [9] and [10] used a
distributed time-based consensus algorithm to ensure end-to-end security and
ensure trustworthy transactions. Meanwhile, researchers in [11] and [12] have
proposed a trustworthy blockchain to establish reliable and transparent data.
However, the transactions verification coming from the outside world is
challenging. In this context, oracles were proposed to verify transactions
coming from off-chain applications. However, using a third party to verify the
data may lead to a single point of failure, especially if the oracles are
jeopardized [13].

To address these challenges, in his paper we present a scalable and
trustworthy blockchain (STB) architecture; which provides scalable,
trustworthy, transparent, and secure data exchange between unreliable IoT
devices.

The main contributions of our paper can be summarized as follows:

  * •

We design a secure blockchain architecture, called STB, which is a distributed
and hierarchical architecture that is suitable for IoT applications. STB
implements sharding and oracles to ensure efficient, scalable, and trustworthy
data exchange among unreliable IoT devices.

  * •

We propose a lightweight blockchain consensus that uses a decentralized trust
method; which ensures secure deployment of the shards and prevents data loss.

  * •

We evaluate the performance of our architecture in terms of efficiency,
latency, computing power, and scalability. The experiment results show that
STB architecture can effectively be used to ensure a trustworthy, scalable,
and efficient data exchange among IoT devices.

The rest of this paper is organized as follows. Section II surveys some
related work. Section III describes the architecture of the scalable and
trustworthy blockchain (STB) for IoT and explains the lightweight blockchain
consensus. Section IV presents a simulation-based case study while Section V
concludes the paper.

##  II Related work

Blockchain technology is considered as the new solution to establish trust
among unreliable entities. Due to the limited block size and block intervals
($i.e.$, the time needed to forge a new block) of traditional blockchain; the
scalability and efficiency of the blockchain need to be further investigated.
To overcome these problems, several blockchain networks were introduced to
optimize these parameters [14] [15]. In [16], Kouzinopoulos et al. proposed a
new method to improve the block creation rate, an alteration to the way miners
construct and reorganize blocks. In [17], Lewenberg et al. proposed increasing
the block size limit to improve the performance. However, increasing the block
size or decreasing the block interval can lead to a stale block rate or
double-spending vulnerability [18]. In [19], Yang et al. proposed to only
delegate blockchain consensus to a limited number of miners in the network.
Although this solution decreased block intervals, it is prone to centralize
since only a limited number of miners are responsible for the mining.

Another approach to scale blockchain is to spread the workload on multiple
blockchains simultaneously, this is referred to as blockchain sharding. To
increase the blockchain scalability, multiple shards work in parallel.
Consequently, this approach may lead to several security issues ($e.g.$, data
loss, single shard attack). Particularly, a shard may be compromised and lead
to data leakage [20] [21]. Besides the security issues, blockchain sharding
can suffer from a wide range of security challenges, such as data
interoperability or data validity. For instance, when a transaction is sent to
the blockchain shards, each shard verifies a partition of the transaction,
when all the sub-shards are verified, the cross-interoperability ($i.e.$,
communication) is difficult.

A major limitation of blockchain technology is its inability to interact with
data outside of the chain ($i.e.$, outside world data) [22]. To overcome this
issue, oracles were proposed to attest to facts in an effort to bring outside
world data into the chain. In [23], Nelaturu et al. proposed an oracle that
verifies and transfers online data to the blockchain. However, online data
could be maliciously altered or may be disclosed. In [24], Ritzdorf et al.
proposed a zero-knowledge oracle that authenticates data without disclosing
full data. This oracle eliminates the need for a trusted third party and
ensures data confidentiality. Although useful, their proposal have high
computational costs.

To address the weaknesses of these existing solutions, we propose STB, a
scalable and trustworthy blockchain architecture that ensure trust among IoT
device in a distributed manner [25]. STB architecture employs multiple shard
chains processing transactions and one main chain to coordinate between the
shards and ensure the transaction interoperability. Furthermore, we proposed
using a decentralized oracle network to overcome the problem of single point
failure and ensure a distributed trust among the participants of the network.
And using a using lightweight blockchain consensus, our architecture is less
computing intensive in comparison with [23][24], making it suitable for IoT
constrained device.

##  III SCALABLE AND TRUSTHWORTHY BLOCKCHAIN

STB is a distributed blockchain architecture that enables devices with
constrained resources ($e.g.$, IoT sensors) to exchange data in a reliable
manner [6]. This section first describes STB’s overall architecture and then
explains how the shards and oracles services are carried out.

###  III-A Architecture

As illustrated in Fig.1, this paper considers data exchange in an IoT
environment where a large number of unreliable IoT devices are connected
through a wireless network ($i.e.$, LTE, 4G, 5G, etc.) and accessible to the
outside world [26]. We propose a scalable and trustworthy blockchain
architecture composed of three layers, as follows:(1) IoT devices responsible
for sending data that need to be verified and stored in the blockchain; (2)
decentralized oracle network responsible for verifying the external data out
of the chain and ensuring its reliability; and (3) the shards responsible for
scaling the blockchain while keeping security guarantees.

Figure 1: Scalable and Trustworthy Blockchain architecture

####  III-A1 Shared Blockchain

The scalability has been a core problem in the integration of blockchain
within the IoT. This is because the IoT connects a large number of devices
that generate big data. To enable horizontal scalability, blockchain sharding
was proposed, it consists of partitioning each transaction into several shards
and to process it independently. In this paper, we propose building clusters
with multiple nodes ($i.e.$, miners) to process each shard in parallel.

Figure 2: Scalable and Trustworthy Blockchain sharding

Fig.2 shows the 3 main components of the STB sharding, as follows: (1) the
main chain; (2) the master clusters’; and (3) slave nodes’. The master cluster
contains $n$ slave nodes, that could be either honest or dishonest. Let
$T_{i}(x)$ represents the $i_{th}$ transaction in a block. To enable the
sharding, each transaction is divided into $n$ disjoint portion. All master
clusters are responsible for verifying a portion of the transaction
$t_{i,j}(x)$, where $i$ is the transaction number on a block and $j$ is the
cluster number. All slave nodes could verify a transaction portion, outputs 0
or 1 indicates invalid and valid transaction, respectively. Let $n$ denote the
total number of slave nodes in a master cluster $j$ that can tolerate up to
$t\leqslant\frac{n}{3}$ dishonest node. We define a transaction verification
process as follows:

$T_{i}(x)=\sum_{j=0}^{n}\sum_{k=0}^{m}t_{i,j}(x)\times C_{j,k}(x)$ (1)

where, $C_{j,k}(x)$ is the trust value in a cluster$j$, proportional to a
transaction portion $t_{i,j}$ and $\sum_{k=0}^{m}C_{j,k}=1$.

The transaction verification process has two possible outcomes: valid and
invalid, each of which carries its own reward structure. As compensation for
their efforts, the clusters are awarded ($R$) whenever they verify a
transaction correctly. In the case of correct verification, a cluster reward
is as follows.

$R(T_{i,j})=\frac{R(t_{i,j}(x))}{R(T_{i,Total}(x))}\times C_{j,k}$ (2)

where, $R(t_{i,j}(x))$ and $R(T_{i,Total}(x))$ represents, respectively, the
reward for a valid transaction portion and total reward for a valid
transaction. Note that the cluster trust value is only used to determine
rewards and penalties, and does not necessarily correspond to the cluster
output. Consequently, we enable secure sharding, prevent data loss, and
incentive clusters to behave honestly.

####  III-A2 Peer-To-Peer Oracle network

We propose using a Peer-To-Peer (P2P) oracle network to verify the data
queries and authenticate its source. Blockchain cannot access external data of
the network. This is where the blockchain oracle interferes, it’s a service
provider (trusted third party) that verifies the data authenticity. However,
trusting a single third party may lead to providing corrupt or inaccurate
data. To this end, we propose using a P2P oracle network that ensures the
truth value of IoT retrieved data. We assume each received data sent from an
IoT device could be either valid $V$ or false $F$. There is $m$ oracle in the
P2P network, only $n$ oracle verify the data. For each oracle $o$ $\in$ [n,m]
has a $q$ probability that data $d$ is correct about a given proposition.

$O_{i}(d)=\begin{cases}q\quad\text{when data is valid}\\\ 1-q\quad\text{when
data is false}\end{cases}$ (3)

The value of $o_{i}(d)$ is independent of $o_{j}(d)$ for all $i\neq j$. In
other words, each oracle’s trust values are independent of other oracles in
the network trust values. Furthermore, oracles need to place a deposit to
participate in a random-chosen verification process. First, the oracle submits
its verification probability $q$ $\in$ [0,1] about a data $d$. Then, this
probability is applied to a trust weight $W$ $\in$ [0,1] that is, informally,
the parameter within the network that verifies the input data within the
network’s hidden layers. Formally:

$W_{i}=\frac{\alpha_{i}}{\beta_{i}}$ (4)

where $\alpha_{i}$ is the sum of corrected verification performed and
$\beta_{i}$ is the total number of verification performed.

$V(d)=\sum_{i=0}^{n}o_{i}(d)\times W_{i}$ (5)

Once a data verification process $V(d)$ has accumulated sufficient
verifiability during a maximum of a period of time $\delta(t)$, it is decided.
This period of time is a fixed value decided by network operators. The
verification process has three possible outcomes:1) valid ($V$), if $V(d)$
value to be strictly positive, 2) false ($f$), if $V(d)$ value to be strictly
negative, and 3) undefined ($U$) if $V(d)$ value is equal to zero. In this
last case, the data verifiability process is only assigned to the oracle with
the highest trust weight.

Broadly speaking, oracles are rewarded when they participate in a verification
process and their verification probability matches it[27]. Conversely, those
who gave incorrect verification are penalized. In the case of undetermined
outcomes, oracles receive no rewards or penalties. As argued in the paper, the
proposed data verification process incentives the oracles to behave honestly
on the validity of data [28, 29].

###  III-B Design Components

The transaction verification procedure of our STB consists of the following
(1) Initialization; (2) Consensus; and (3) Reward. This procedure starts with
the initialization and then proceeds in periods, where each period consists of
several iterations of consensus and finally the rewarding phase. We now
explain each component in more detail.

####  III-B1 Initialization

The initial set of participants ($i.e.$, nodes) are invited to provide a
deposit ($stake$) to validate or endorse a transaction. That is, a node is
given the chance to verify a transaction chosen uniformly at random from the
unverified transaction pool. The deposit is placed before the verification
process. Because the nodes are grouped in clusters, the outcome of the
transaction verification reward is a function of the sum of the total
transaction verification reward weighted by the cluster value in the cluster
and the deposits.

####  III-B2 Consensus

Once nodes of each cluster are done with the initialization step, they wait
for an IoT device to submit their transactions. The transaction is partitioned
uniformly on $n$ partition. Each transaction partition is sent to a cluster
that forwards the transaction to corresponding nodes. These clusters run an
intra-cluster consensus protocol to approve the transaction partition. The
inter-cluster consensus is a protocol where each node places a portion of its
deposit in their confidence of their verification being valid.

Meanwhile, it is challenging to build a consensus that processes transactions
and ensures interoperability among the shards. Sharding consensus could lead
to possible attacks, and thus without an efficient and secure cross-shard
consensus data may be compromised and the blockchain interoperability may be
lost. To solve this problem, we propose in this article an intra-cluster
lightweight consensus to approve a transaction and add it to its ledger.
Algorithm 1 illustrates the logic of this consensus. In STB we have the main
chain and shard chains that accommodate $n$ sub-chains(shard). This consensus
takes as input all partitions of a transaction $T_{i,j}$ and returns a new
block if the transaction verification is valid; otherwise, it returns false.
This intra-shard consensus will be invoked at the moment when all the
collaborators (master clusters) try to forge a new block into the ledger. A
transaction $T$ is partitioned equally among $n$ collaborators. First, we
verify that the transaction has been verified by the P2P oracle network. We
then calculate the transaction verification process according to Eq.1. If the
output is superior to $\frac{n}{3}$, we then accept the transaction;
otherwise, it is considered false. Finally, if the transaction is verified, we
then forge a new block and update the ledger.

Input $\forall t_{i,j}(x)\in T$, $O_{i}\in O$, $C_{i,j}\in C$;
Output $T$, $B_{i+1}$; Initialize:

1:$T$: A transaction from the unverified transaction pool;

2:$n$: The number of master clusters;

3:$t_{i,j}$: A transaction partition;

4:$O_{i}$: An oracle form the P2P network;

5:$C_{i,j}$: A master cluster trust value;

6:if $T.signature==O_{i}.sigature$ then

7: while $i\leqslant n$ do

8: while $C_{i,j}\in C$ do

9: $T(x)=t_{i,j}\times C_{i,j}+T(x)$

10: $W=W+C_{i,j}$

11: end while

12: end while

13: if $W(x)\neq 1$ then

14: Break;

15: end if

16:else

17: if $T(x)\leqslant\frac{n}{3}$ then

18: AddBlock($B_{i+1}$)

19: $Return$ $Valid$ $Transaction$

20: end if

21: $Return$ $False$ $Transaction$

22:end if

23:$Break$

Algorithm 1 Inter-Shard Consensus Algorithm.

####  III-B3 Reward

Figure 3: Adding data to the STB

Broadly speaking, nodes ($i.e.$, miners) are rewarded for transaction
verification in which they took part. Conversely, those who provided false
verification are penalized. The steps of reward/penalize are depicted in
Fig.3. Let $r_{i}$ denote the reward amount that a node $i$ used to verify
that a transaction partition is equal to $0$ or $1$. In the case of a valid
verification, the reward is as follows:

$r_{i}=\frac{R(T_{i,j})}{Total}+\alpha_{i}$ (6)

where, $R(T_{i,j})$ is the master cluster reward, $Total$ refers to the total
number of the cluster node participating in the verification process, and
$\alpha_{i}$ node deposit. A node’s reward is equal to his participating share
in the transaction verification process. For instance, if a cluster has a
reward equal to 1000, and the number of participant nodes is equal to 100, the
reward is distributed equally and each node will receive 100 as a stake. In
the case of false verification, the node is penalized and the reward is
deducted from its deposit.

##  IV Evaluation

This section presents the evaluation STB architecture. We compare our STB to
other prominent works in terms of scalability, computing power, and latency
[8]. We consider several variant of the proposed architecture:(1) STB, which
is a blockchain network that implements all of our proposed components and the
proposed lightweight consensus; (2) Bitcoin [30], which is a basic blockchain
network that uses Proof-of-work(PoW)consensus; and (3) Quarkchain [31], which
is a blockchain network that implements the clustering feature and employs
boson consensus- a blockchain sharding consensus to scale the network. The
simulations were conducted on a laptop with 2.2 GHz Intel $i7$ processors and
16GB of memory.

TABLE I: SIMULATION SETUP PARAMETER Parameters | Value
---|---
Oracles | 3
IP | localhost
Master clusters | 8
Slave nodes | 10
Maximum period of time $\delta(t)$ | 10$s$
PoW difficulty | 4
Figure 4: Scalability comparison

To examine the scalability of different architecture, we evaluate the
computing power needed to add one block to the chain. Fig. 4 depicts the
results. Because Quarkchain uses the sharding concept, we can observe that the
computing power needed to add blocks decreases with time. This happens because
the block workload is separated among 8 shards. We clearly observe that the
proposed STB architecture is less computing intensive than others. This
happens because the proposed consensus algorithm does not have a difficulty
level that limits block generations.

In Fig. 5, we evaluate the CPU in a function with time needed to add 10 blocks
to the chain. In this experiment, we only compare STB with Quarkchain. This
because, the time needed to add one block using Pow is much higher than other
architecture. We observe that the local max, which point on the maximum CPU
needed to forge blocks, of STB is less higher than Quarkchain. This is
because, STB implements a distributed trust model that partition the work load
needed to add blocks on several master clusters. These clusters in their turn
partition the work load on the slave nodes that work in parallel.

In Fig. 6, we compare the latency of variant blockchains. As evidenced by the
figure, the PoW latency increases with the number of blocks to add in the BC.
Meanwhile, the time needed to add block ins Quarkchain is a fixed value $10s$
and $0.1s$ for the STB. The results demonstrate the efficiency of STB, in
terms of scalability, computing power, and latency in comparison with other
architectures.

Figure 5: Computational power comparison Figure 6: Latency comparison

##  V Conclusion

This paper proposed, STB, which is a scalable and trustworthy blockchain
architecture that is suitable for the IoT. Because of the large number of IoT
unreliable and constrained device, the integration of the blockchain with the
IoT is not straightforward. To this aim, we first design the distributed and
hierarchical blockchain architecture. We then describe the 2 main components
of the chain, each of which is responsible for scaling the blockchain and
verifying the reliability of information before storing them into the chain.
Finally, we propose lightweight blockchain consensus that is suitable with IoT
constrained device. The simulation results demonstrate that out architecture
outperforms existing blockchain in terms of flexibility, scalability, and
latency.

## acknowledgement

The authors would like to thank the Natural Sciences and Engineering Research
Council of Canada, as well as FEDER and GrandEst Region in France, for the
financial support of this research.

## References

  * [1] H. Moudoud, L. Khoukhi, and S. Cherkaoui, “Prediction and Detection of FDIA and DDoS Attacks in 5G Enabled IoT,” _IEEE Network_ , vol. 35, no. 2, pp. 194–201, Mar. 2021.
  * [2] “Blockchain - Statistics & Facts | Statista.”
  * [3] H. Dang, T. T. A. Dinh, D. Loghin, E.-C. Chang, Q. Lin, and B. C. Ooi, “Towards Scaling Blockchain Systems via Sharding,” in _Proceedings of the 2019 International Conference on Management of Data - SIGMOD ’19_. Amsterdam, Netherlands: ACM Press, 2019, pp. 123–140.
  * [4] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding,” in _2018 IEEE Symposium on Security and Privacy (SP)_ , May 2018, pp. 583–598.
  * [5] B. Nour, S. Cherkaoui, and Z. Mlika, “Federated Learning and Proactive Computation Reuse at the Edge of Smart Homes,” _IEEE Transactions on Network Science and Engineering_ , pp. 1–1, 2021.
  * [6] H. Moudoud, S. Cherkaoui, and L. Khoukhi, “An IoT Blockchain Architecture Using Oracles and Smart Contracts: the Use-Case of a Food Supply Chain,” in _2019 IEEE 30th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)_ , Sep. 2019, pp. 1–6.
  * [7] Z. A. E. Houda, A. Hafid, and L. Khoukhi, “Blockchain Meets AMI: Towards Secure Advanced Metering Infrastructures,” in _ICC 2020 - 2020 IEEE International Conference on Communications (ICC)_ , Jun. 2020, pp. 1–6.
  * [8] E. D. N. Ndih and S. Cherkaoui, “Chapter 17 - Simulation methods, techniques and tools of computer systems and networks,” in _Modeling and Simulation of Computer Networks and Systems_ , M. S. Obaidat, P. Nicopolitidis, and F. Zarai, Eds. Boston: Morgan Kaufmann, Jan. 2015, pp. 485–504.
  * [9] A. Dorri, S. S. Kanhere, R. Jurdak, and P. Gauravaram, “LSB: A Lightweight Scalable BlockChain for IoT Security and Privacy,” _arXiv:1712.02969 [cs]_ , Dec. 2017.
  * [10] L. Zhu, Y. Wu, K. Gai, and K.-K. R. Choo, “Controllable and trustworthy blockchain-based cloud data management,” _Future Generation Computer Systems_ , vol. 91, pp. 527–535, Feb. 2019.
  * [11] C. Cai, H. Duan, and C. Wang, “Tutorial: Building Secure and Trustworthy Blockchain Applications,” Sep. 2018, pp. 120–121.
  * [12] H. Al-Breiki, M. H. U. Rehman, K. Salah, and D. Svetinovic, “Trustworthy Blockchain Oracles: Review, Comparison, and Open Research Challenges,” _IEEE Access_ , vol. 8, pp. 85 675–85 685, 2020.
  * [13] M. Lakoju, A. Javed, O. Rana, P. Burnap, S. T. Atiba, and S. Cherkaoui, ““Chatty Devices” and edge-based activity classification,” _Discover Internet of Things_ , vol. 1, no. 1, p. 5, Feb. 2021.
  * [14] Z. Tu and C. Xue, “Effect of bifurcation on the interaction between Bitcoin and Litecoin,” _Finance Research Letters_ , vol. 31, Dec. 2019.
  * [15] Y. Kwon, H. Kim, J. Shin, and Y. Kim, “Bitcoin vs. Bitcoin Cash: Coexistence or Downfall of Bitcoin Cash?” in _2019 IEEE Symposium on Security and Privacy (SP)_ , May 2019, pp. 935–951.
  * [16] C. S. Kouzinopoulos, K. M. Giannoutakis, K. Votis, D. Tzovaras, A. Collen, N. A. Nijdam, D. Konstantas, G. Spathoulas, P. Pandey, and S. Katsikas, “Implementing a Forms of Consent Smart Contract on an IoT-based Blockchain to promote user trust,” in _2018 Innovations in Intelligent Systems and Applications (INISTA)_ , Jul. 2018, pp. 1–6.
  * [17] Y. Lewenberg, Y. Sompolinsky, and A. Zohar, “Inclusive Block Chain Protocols,” in _Financial Cryptography and Data Security_ , ser. Lecture Notes in Computer Science, R. Böhme and T. Okamoto, Eds. Berlin, Heidelberg: Springer, 2015, pp. 528–547.
  * [18] K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. Kosba, A. Miller, P. Saxena, E. Shi, E. Gün Sirer, D. Song, and R. Wattenhofer, “On Scaling Decentralized Blockchains,” in _Financial Cryptography and Data Security_ , ser. Lecture Notes in Computer Science, J. Clark, S. Meiklejohn, P. Y. Ryan, D. Wallach, M. Brenner, and K. Rohloff, Eds. Berlin, Heidelberg: Springer, 2016, pp. 106–125.
  * [19] F. Yang, W. Zhou, Q. Wu, R. Long, N. N. Xiong, and M. Zhou, “Delegated Proof of Stake With Downgrade: A Secure and Efficient Blockchain Consensus Algorithm With Downgrade Mechanism,” _IEEE Access_ , vol. 7, pp. 118 541–118 555, 2019.
  * [20] J. Zhang, Z. Hong, X. Qiu, Y. Zhan, S. Guo, and W. Chen, “SkyChain: A Deep Reinforcement Learning-Empowered Dynamic Blockchain Sharding System,” in _49th International Conference on Parallel Processing - ICPP_ , ser. ICPP ’20. New York, NY, USA: Association for Computing Machinery, Aug. 2020, pp. 1–11.
  * [21] A. Chauhan, O. P. Malviya, M. Verma, and T. S. Mor, “Blockchain and Scalability,” in _2018 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C)_ , Jul. 2018, pp. 122–128.
  * [22] M. E. Peck, “Blockchains: How they work and why they’ll change the world,” _IEEE Spectrum_ , vol. 54, no. 10, pp. 26–35, Oct. 2017.
  * [23] K. Nelaturu, J. Adler, M. Merlini, R. Berryhill, N. Veira, Z. Poulos, and A. Veneris, “On Public Crowdsource-Based Mechanisms for a Decentralized Blockchain Oracle,” _IEEE Transactions on Engineering Management_ , vol. 67, no. 4, pp. 1444–1458, Nov. 2020.
  * [24] H. Ritzdorf, K. Wüst, A. Gervais, G. Felley, and S. Čapkun, “TLS-N: Non-repudiation over TLS Enabling Ubiquitous Content Signing for Disintermediation,” p. 16.
  * [25] Z. Mlika and S. Cherkaoui, “Massive IoT Access With NOMA in 5G Networks and Beyond Using Online Competitiveness and Learning,” _IEEE Internet of Things Journal_ , vol. 8, no. 17, pp. 13 624–13 639, Sep. 2021.
  * [26] z. Mlika and S. Cherkaoui, “Competitive Algorithms and Reinforcement Learning for NOMA in IoT Networks,” in _ICC 2021 - IEEE International Conference on Communications_ , Jun. 2021, pp. 1–6.
  * [27] A. Rachedi, M. H. Rehmani, S. Cherkaoui, and J. J. P. C. Rodrigues, “IEEE Access Special Section Editorial: The Plethora of Research in Internet of Things (IoT),” _IEEE Access_ , vol. 4, pp. 9575–9579, 2016\.
  * [28] E. D. Ngangue Ndih and S. Cherkaoui, “On Enhancing Technology Coexistence in the IoT Era: ZigBee and 802.11 Case,” _IEEE Access_ , vol. 4, pp. 1835–1844, 2016.
  * [29] E. D. Ngangue Ndih, S. Cherkaoui, and I. Dayoub, “Analytic Modeling of the Coexistence of IEEE 802.15.4 and IEEE 802.11 in Saturation Conditions,” _IEEE Communications Letters_ , vol. 19, no. 11, pp. 1981–1984, Nov. 2015.
  * [30] M. Vukolić, “The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication,” in _Open Problems in Network Security_ , J. Camenisch and D. Kesdoğan, Eds. Cham: Springer International Publishing, 2016, vol. 9591, pp. 112–125.
  * [31] J. S. Aldakheel, M. A. AlAhmad, and A. Al-Foudery, “Comparison Between Bitcoin and Quarkchain,” _Journal of Computational and Theoretical Nanoscience_ , vol. 16, no. 3, pp. 818–822, Mar. 2019.


# Computing Controlled Invariant Sets of Nonlinear Control-Affine Systems

Scott Brown  Mohammad Khajenejad  Sze Zheng Yong  Sonia Martínez S. Brown, M,
Khajenejad and S. Martínez are with the Mechanical and Aerospace Engineering
Department, University of California San Diego, San Diego, CA, USA.
<EMAIL_ADDRESS>S. Z. Yong is with the Mechanical and
Industrial Engineering Department, Northeastern University.
<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider the computation of controlled invariant sets (CIS)
of discrete-time nonlinear control-affine systems. We propose an iterative
refinement procedure based on polytopic inclusion functions, which is able to
approximate the maximal controlled invariant set to within a guaranteed
precision. In particular, this procedure allows us to guarantee the invariance
of the resulting near-maximal CIS while also computing sets of control inputs
which enforce the invariance. Further, we propose an accelerated version of
this procedure which refines the CIS by computing backward reachable sets of
individual components of set unions, rather than all at once. This reduces the
total number of iterations required for convergence, especially when compared
with existing methods. Finally, we compare our methods to a sampling based
approach and demonstrate the improved accuracy and faster convergence.

##  I Introduction

Invariance is an important concept for ensuring robustness and safety of
control systems. For a dynamical system, a set is (_forward_) _invariant_ if
every trajectory starting in that set remains in the set for all time. For
control systems, this notion can be generalized with the determination of a
control input which is able to render a set invariant, leading to the notion
of a _controlled invariant set_ (CIS). For systems which are subject to
uncertainty or noise, the concept of a _robust controlled invariant set_
(RCIS) is critical for safety, as it guarantees invariance in the presence of
disturbances.

Controlled invariant sets have been thoroughly studied for linear systems,
e.g., [1, 2, 3, 4, 5]. Many of these methods employ iterative procedures based
on a one-step backward operator [2, 3] to find backward reachable sets of the
system for computing the CIS with high precision. In order to improve the
computation time for high-dimensional systems, other non-iterative techniques
have also been proposed which rely on lifting to a higher dimensional space to
compute the CIS in closed form and projecting the resulting set to the
original domain, e.g., [4, 5].

On the other hand, determining controlled invariant sets of nonlinear systems
remains a significant challenge. Some works employ convex or zonotopic
approximations, e.g., [6, 7], in order to reduce the computational complexity.
However, as the maximal controlled invariant sets are nonconvex in general,
these methods can be overly conservative.

Another related work pertains to the study of invariant sets of _switched_
systems, e.g., [8, 9, 10], where the input controls switching between a finite
number of modes. In that case, the input is easily determined by considering
all possible modes and selecting those which lead to invariance [9]. By
sampling a continuous set of inputs, these methods can be applied to more
general nonlinear systems, but the accuracy and scalability may be limited
[10]. These methods result in sets that are guaranteed to be invariant, but
the sampling is an additional source of computational complexity as it must be
fine enough to properly capture the nonlinear behavior of the system. As a
result, these methods are difficult to apply to systems with multiple inputs.

In this paper, we propose two iterative algorithms to compute the near-maximal
(non-convex) controlled invariant set of control affine systems up to a
guaranteed precision, _without_ sampling the set of allowable inputs. Inspired
by [9], our methods use a bisection approach to over- and under-approximate
the one-step backward reachable set operator. The main idea of the approach is
to compute the _forward_ reachable set of the region of interest, which is
described by a union of intervals. The parts of this forward set that are
entirely contained in the original set are used as an under-approximation of
the backward reachable set. To check the containment, we use polyhedral over-
approximations of reachable sets, which allows us to cast the problem of
determining the control input as a translation of a polyhedron. This technique
allows us to determine a _continuous_ , rather than sampled, set of invariance
enforcing control inputs. In addition, we leverage the structure of set unions
in the accelerated version, which has the potential to significantly reduce
the total number of iterations required for convergence, when compared with
existing methods.

###  I-A Notation

Let $\mathbb{Z}_{\geq 0}$ be the set of nonnegative integers, and n and n×p be
the $n$-dimensional Euclidean space, and the set of $n\times p$ matrices,
respectively. By means of $\mathcal{B}_{r}$, we denote the $\infty$-norm
hyperball of radius $r$. We make use of $\mathbb{I}{}^{n}$ to denote the
collection of (multidimensional) intervals of n, and denote its elements as
$[x]\triangleq[\underline{x},\overline{x}]\in\mathbb{I}{}^{n}$ with lower and
upper bounds $\underline{x}$ and $\overline{x}$. The function $w([x])$
measures interval width (i.e., $w([x])=\|\overline{x}-\underline{x}\|$ with
any vector norm $\|\cdot\|$), $\operatorname{mid}([x])$ selects the midpoint
of $[x]$ (i.e.,
$\operatorname{mid}([x])=\frac{1}{2}(\overline{x}+\underline{x})$), and a
function in brackets $[f]([x])$ represents an interval inclusion function (cf.
Definition 1). The operator $\oplus$ denotes the Minkowski sum of two sets,
and $\ominus$ denotes the Pontryagin difference. For a function
$f:{}^{n}\to{}^{m}$ and a set $\mathcal{S}\subset{}^{n}$, $f_{0}(\mathcal{S})$
denotes the image of $\mathcal{S}$ under $f_{0}$. For a bounded polyhedron
(polytope) $\mathcal{P}$, we use $H_{\mathcal{P}}$ and $b_{\mathcal{P}}$ to
denote the components defining the halfspace representation $\mathcal{P}=\\{x\
:\ H_{\mathcal{P}}x\leq b_{\mathcal{P}}\\}$. The symbol $V_{\mathcal{P}}$
denotes the vertices of $\mathcal{P}$. Finally,
$\operatorname{conv}\mathcal{X}$ denotes the convex hull of the set
$\mathcal{X}$.

##  II Preliminaries

This section introduces preliminary notions that will be used throughout the
paper. We begin by defining inclusion functions, which are critical for
tractably approximating the images of sets under nonlinear functions.

######  Definition 1.

Given a function $f:{}^{n}\to{}^{m}$, an _inclusion function_ is an interval
function $[f]:\mathbb{I}{}^{n}\to\mathbb{I}{}^{m}$ that satisfies

$\displaystyle[f]([x])\supseteq f([x]),\ \forall[x]\in\mathbb{I}{}^{n},$

where $f([x])$ denotes the exact image of $[x]$ under $f$.

The reader is referred to [11, Section 2.4] and [12] for a thorough discussion
of different types of inclusion functions, such as natural, centered, etc., as
well as mixed-monotone decomposition-based inclusion functions. The results of
this paper are not specific to any one type of inclusion function. However,
different inclusion functions may produce more or less precise approximations
depending on the system.

###  II-A Translating Polytopes

This section defines two different operations on polytopes: translating one
into another, and translating one so it intersects another. These will be used
in our algorithm to determine safe control inputs.

######  Definition 2.

Given two polytopes $\mathcal{P}$ and $\mathcal{Q}$, the set of translations
of $\mathcal{P}$ that _insert_ $\mathcal{P}$ into $\mathcal{Q}$ is denoted by

$\displaystyle\mathcal{I}(\mathcal{P},\mathcal{Q})\triangleq\\{r\in{}^{n}:\mathcal{P}\oplus\\{r\\}\subseteq\mathcal{Q}\\}.$

Similarly, the set of translations of $\mathcal{P}$ that _overlap_
$\mathcal{P}$ with $\mathcal{Q}$ is defined as

$\displaystyle\mathcal{O}(\mathcal{P},\mathcal{Q})\triangleq\\{s\in{}^{n}:\mathcal{P}\oplus\\{s\\}\cap\mathcal{Q}\neq\emptyset\\}.$

######  Proposition 1 ([13, Theorem 2.3]).

For polytopes $\mathcal{P}$ and $\mathcal{Q}$,

$\displaystyle\mathcal{I}(\mathcal{P},\mathcal{Q})=\\{r\in{}^{n}:H_{\mathcal{Q}}r\leq
b_{\mathcal{Q}}-\beta\\},$

where $\beta_{i}=\max_{v\in V_{\mathcal{P}}}(H_{\mathcal{Q}})_{i}v$. If
$\mathcal{P}$ cannot be embedded into $\mathcal{Q}$, then this results in
$\mathcal{I}(\mathcal{P},\mathcal{Q})=\emptyset$.

######  Proposition 2.

Given two polytopes $\mathcal{P}$ with $\mathcal{Q}$,

$\displaystyle\mathcal{O}(\mathcal{P},\mathcal{Q})=\left\\{s\in{}^{n}:\begin{bmatrix}H_{\mathcal{Q}}\\\
-H_{\mathcal{P}}\end{bmatrix}s\leq\begin{bmatrix}b_{\mathcal{Q}}-\alpha\\\
b_{\mathcal{P}}-\gamma\end{bmatrix}\right\\},$

where $\alpha_{i}=\min_{v\in V_{\mathcal{P}}}(H_{\mathcal{Q}})_{i}v$ and
$\gamma_{i}=\min_{v\in V_{\mathcal{Q}}}(H_{\mathcal{P}})_{i}v$.

###### Proof.

See Appendix -A. ∎

##  III Invariance Control Problem

Here we introduce the class of systems under consideration and define the
concept of controlled invariance. Specifically, we consider nonlinear control
affine systems of the form

$\displaystyle x_{k+1}=f(x_{k},u_{k})\triangleq
f_{0}(x_{k})+\sum_{i=1}^{m}g_{i}(x_{k})u_{i,k},$ (1)

where $x\in{}^{n}$ is the state and $u\in\mathcal{U}\subset{}^{m}$ is the
input. We assume that $\mathcal{U}$ is a compact interval, and we will
restrict our attention to a region of interest, $\Omega\subset{}^{n}$, which
we assume to be given as a finite union of compact intervals.

######  Assumption 1.

The functions $f_{0}$, and $g_{1}$, $\dots$, $g_{m}$ are Lipschitz continuous,
i.e.,

$\displaystyle\forall i\in\\{1,\dots,m\\},\ \exists$ $\displaystyle
L_{i}\text{ s.t. }\|g_{i}(x)-g_{i}(y)\|\leq L_{i}\|x-y\|,$ and $\displaystyle
L\text{ s.t. }\|f_{0}(x)-f_{0}(y)\|\leq L\|x-y\|,$

for every $x,y\in\Omega$.

Next we define the precise notions of invariance which we will consider in
this work.

######  Definition 3.

A set $\mathcal{X}\subset{}^{n}$ is _controlled invariant_ with respect to the
dynamics (1) if for every $x_{0}\in\mathcal{X}$, there exists an input $u$
such that $f(x_{0},u)\in\mathcal{X}$.

There are many computational challenges associated with computing controlled
invariant sets, many of which arise due to the infinite precision required to
adequately handle regions near the boundary of the set. As such, it is
convenient to modify the definition to incorporate a robustness margin $r$.

######  Definition 4.

A set $\mathcal{X}\subset{}^{n}$ is _$r$ -robustly controlled invariant_ for
system (1) if for every $x_{0}\in\mathcal{X}$, there exists an input $u$ such
that $f(x_{0},u)\in\mathcal{X}\ominus\mathcal{B}_{r}$.

Intuitively, in order to be robustly invariant, every point must be mapped
into the interior of the set, at some distance $r$ from the boundary.

We are ready to formally state the problem which we aim to address in this
paper.

######  Problem 1 (Controlled Invariant Set Computation).

For a system (1) that satisfies Assumption 1 and a region of interest
$\Omega\subset{}^{n}$, given by a union of compact intervals, compute the
maximal controlled invariant set contained in $\Omega$ up to a guaranteed
precision. Additionally, compute the corresponding set of control inputs that
enforces this invariance.

######  Remark 1.

For ease of exposition, we do not consider any noise or uncertainty in the
system dynamics (1). However, it is straightforward to include robustness to
bounded noise in our algorithm by increasing the robustness margin $r$.

##  IV Computation of Controlled Invariant Sets

This section starts by reviewing a well-known iterative procedure for
computing maximal controlled invariant sets [14]. After this, we describe our
main contribution, which approximates the operator used in each iteration.

######  Definition 5.

The _pre-set_ , or the _one-step backward reachable set_ of a set
$\Omega\subset{}^{n}$ is defined as

$\displaystyle Q(\Omega)\triangleq\left\\{x\in{}^{n}:\exists
u\in\mathcal{U}\text{ s.t. }f(x,u)\in\Omega\right\\}.$

We further define the operator

$\displaystyle I(\Omega)\triangleq Q(\Omega)\cap\Omega,$

which will enable computation of the maximal controlled invariant set.
Repeated application is denoted as $I^{i}(\Omega)=I(I^{i-1}(\Omega))$,
$i\in\mathbb{Z}_{\geq 0}$, with $I^{0}(\Omega)=\Omega$. We also define
$I_{r}(\Omega)\triangleq Q(\Omega\ominus\mathcal{B}_{r})\cap\Omega$.

######  Lemma 1 ([14, Special Case of Proposition 4]).

If $\Omega\subset{}^{n}$ is closed, then

$\displaystyle I^{\infty}\triangleq\lim_{i\to\infty}I^{i}(\Omega)$

is the maximal controlled invariant set contained in $\Omega$.

This result is the basis for many iterative algorithms, e.g., [2, 3, 14], but
there are several computational challenges when dealing with nonlinear
systems. In addition to operations involving _backward_ reachability, our
algorithm also utilizes operations related to _forward_ reachability, which we
define here.

######  Definition 6.

The _one-step forward reachable set_ of a set $\Omega\subset{}^{n}$ is defined
as

$\displaystyle P(\Omega)\triangleq\\{x\in{}^{n}:\exists
x_{0}\in\Omega,u\in\mathcal{U}\text{ s.t. }x=f(x_{0},u)\\}.$

The following definition restricts the previous reachable set to that of a
particular input, which is used later for determining a suitable controller.

######  Definition 7.

For a given $u\in\mathcal{U}$, the _fixed-control one-step forward reachable
set_ of a set $\Omega\subset{}^{n}$ is defined as

$\displaystyle P_{u}(\Omega)\triangleq\\{x\in{}^{n}:\exists
x_{0}\in\Omega\text{ s.t. }x=f(x_{0},u)\\}.$

From the definitions, it is clear that
$\bigcup_{u\in\mathcal{U}}P_{u}(\Omega)=P(\Omega)$.

###  IV-A Polyhedral Approximation of Reachable Sets

Our algorithm will employ polyhedral over-approximations of $P(\Omega)$ and
$P_{u}(\Omega)$ to determine feasible control inputs that can lead to
invariance.

To this end, we use a decomposition of the function $f$, which we will show to
satisfy certain properties. This decomposition will vary depending on the
interval $[x]$ under consideration. We first compute $A$ and $\phi$ such that

$\displaystyle f_{0}(x)=Ax+\phi(x),\ \forall x\in[x],$ (2)

decomposing $f$ into a linear term plus a remainder. This is always possible
(since we can let $A=0$) and can be done in multiple different ways. For
example, if $f$ is differentiable, this can be done via linearization about
the midpoint of the interval. Another possibility is that $f$ has a bounded
Jacobian matrix on $[x]$, in which case we can apply a Jacobian sign-stable
decomposition [15, Proposition 2] to compute (2). The method of decomposition
will affect the accuracy of the final approximation, as we will discuss at the
end of this section. Then, by using an inclusion function
$[\Phi]:\mathbb{I}{}^{n}\to\mathbb{I}{}^{n}$ satisfying
$[\Phi]([x])\supseteq\phi([x])$, we can guarantee that

$\displaystyle f_{0}([x])\subseteq A[x]\oplus[\Phi]([x]),$ (3)

where $A[x]$ denotes the exact (polytope) image of $[x]$ under the linear map
$A$.

We also decompose the individual input functions $g_{i}$. For an inclusion
function $[g_{i}]$, let $s_{i}=\operatorname{mid}([g_{i}]([x]))$ and
$[\Psi_{i}]([x])=[g_{i}]([x])\ominus\\{s_{i}\\}$, so that

$\displaystyle g_{i}([x])\subseteq\\{s_{i}\\}\oplus[\Psi_{i}]([x]),$ (4)

and $[\Psi_{i}]([x])$ is centered at the origin. A centered $[\Psi_{i}]([x])$
will result in a better approximation later on. We will use the notation
$S\in{}^{n\times m}$ and $[\Psi]:\mathbb{I}{}^{n}\to\mathbb{I}{}^{n\times m}$
to denote the matrices with columns $s_{i}$ and $[\Psi_{i}]$, respectively.

In order to guarantee the accuracy of the algorithm, we must first compute
bounds on the error of these overapproximations. Assumption 1 allows us to
upper bound the width of the resulting inclusion functions.

######  Proposition 3.

Under Assumption 1, inclusion functions $[\Phi]$ and $[\Psi_{i}]$,
$i\in\\{1,\dots,m\\}$, and constants $\tilde{L}_{i}>0,\ i\in\\{0,\dots,m\\}$
can be found so that

$\displaystyle w([\Phi]([x])\leq\tilde{L}_{0}w([x])\ \text{ and }\
w([\Psi_{i}]([x])\leq\tilde{L}_{i}w([x]).$

for every interval $[x]\subseteq\Omega$.

###### Proof.

We can, for example, use inclusion functions based on mixed-monotone
decompositions (cf. [16, Lemma 1]) or the mean-value form (cf. [11] and [9,
Eq. (3)]) that can be shown to satisfy these bounds. ∎

With these decompositions in mind, we can define our approximations of the
forward reachable sets. Let

$\displaystyle\overline{P}([x])\triangleq A[x]\oplus[\Phi]([x])\oplus
S\mathcal{U}\oplus[\Psi]([x])\mathcal{U}$

be the polyhedral overapproximation of the one-step forward reachable set, and
let

$\displaystyle\overline{P}_{u}([x])\triangleq A[x]\oplus[\Phi]([x])\oplus
Su\oplus[\Psi]([x])\mathcal{U}$

be the polyhedral overapproximation of the fixed-control reachable set. The
expression $S\mathcal{U}$ denotes the polytopic image of $\mathcal{U}$ under
the linear transformation $S$, and $[\Psi]([x])\mathcal{U}$ denotes the
interval-valued product of two interval matrices that can be computed using
interval arithmetic.

######  Lemma 2.

Let $\rho\triangleq\tilde{L}_{0}+\max_{1\leq i\leq
m}\tilde{L}_{i}w(\mathcal{U}_{i})$. Then for all intervals $[x]\subset\Omega$,
the polytopic approximations of the forward reachable sets satisfy

$\displaystyle P_{u}([x])$
$\displaystyle\subseteq\overline{P}_{u}([x])\subseteq
P_{u}([x])\oplus\mathcal{B}_{\rho w([x])}$

and

$\displaystyle P([x])$ $\displaystyle\subseteq\overline{P}([x])\subseteq
P([x])\oplus\mathcal{B}_{\rho w([x])}.$

###### Proof.

The inclusion $P_{u}([x])\subseteq\overline{P}_{u}([x])$ is guaranteed by
construction, since

$\displaystyle P_{u}([x])=A[x]\oplus\phi([x])\oplus
Su\oplus\sum_{i=1}^{m}\hat{g}_{i}([x]))u_{i},$

$\phi([x])\subseteq[\Phi]([x])$, and
$\hat{g}_{i}([x])\subseteq[\Psi_{i}]([x])$. The inclusion
$\overline{P}_{u}([x])\subseteq P_{u}([x])\oplus\mathcal{B}_{\rho w([x])}$
follows from Proposition 3 and the definition of the Minkowski sum. The second
statement is proved in the same way. ∎

###  IV-B Interval Approximation of Pre-Sets

We describe our main contribution next, which is a novel algorithm for
approximating the operator $I$ for systems of the form (1). Given a union of
compact intervals $\Omega$, we propose an iterative refinement procedure that
approximates $I(\Omega)$ by another union of compact intervals. Algorithm 1
summarizes the main steps of this process, described in detail next.

Algorithm 1 $\underline{I}(\Omega)$

1:$\Omega$, $\varepsilon$

2:$Q\leftarrow\\{\Omega\\}$, $N\leftarrow\emptyset$,
$\underline{I}\leftarrow\emptyset$, $\mathcal{E}\leftarrow\emptyset$,
$\mathcal{U}_{I}\leftarrow\emptyset$

3:while $Q\neq\emptyset$ do

4: $[x]\leftarrow\operatorname{pop\\_front}(Q)$

5: Compute $A$, $\Phi$, $s_{i}$, and $\Psi_{i}$ on $[x]$

6: if $\overline{P}([x])\cap\Omega=\emptyset$ then

7: $N\leftarrow N\cup[x]$

8: else if $\exists u\in\mathcal{U}\text{ s.t.
}\overline{P}_{u}([x])\subseteq\Omega$ then

9: $\underline{I}\leftarrow\underline{I}\cup[x]$

10:
$\mathcal{U}_{I}\leftarrow\mathcal{U}_{I}\cup([x],S^{\dagger}(S\mathcal{U}([x])))$

11: else if $w([x])\leq\varepsilon$ then

12: $\mathcal{E}\leftarrow\mathcal{E}\cup[x]$

13: else

14: $(l,r)\leftarrow\operatorname{bisect}([x])$

15: $\operatorname{push\\_front}(Q,l)$

16: $\operatorname{push\\_front}(Q,r)$

17: end if

18:end while

19:return $\underline{I}$, $\mathcal{U}_{I}$

The algorithm is a loop that operates on a queue ($Q$) of intervals. An
element of the queue is retrieved (and removed) from the front of the queue
using the $\operatorname{pop\\_front}$ operation, while an element is added to
the front of the queue using the $\operatorname{push\\_front}$ operation. The
following steps are implemented until the queue is empty. Every interval $[x]$
is checked to see whether it may be part of the pre-set of $\Omega$. Two tests
are performed:

  1. 1.

Is the forward reachable set from $[x]$ disjoint with $\Omega$? If so, $[x]$
is disjoint from $I(\Omega)$.

  2. 2.

Can an input $u$ be found so that the reachable set from $[x]$, restricted to
the input $u$, lies entirely within $\Omega$? If so, $[x]\subset I(\Omega)$.

If either condition is satisfied, then the set $[x]$ is saved in lists labeled
$\mathcal{N}$ (the collection of intervals disjoint with $I(\Omega)$) and
$\mathcal{S}$ (the collection of intervals contained in $I(\Omega)$).

If neither condition is satisfied and the $[x]$ is wider than the specified
tolerance, it is bisected along its largest dimension and both resulting
intervals are added to the front of the queue using the
$\operatorname{push\\_front}$ operation. Otherwise, $[x]$ is added to
$\mathcal{E}$, which is a collection of the so-called “indeterminate” sets,
which are neither disjoint from nor subsets of $I(\Omega)$.

Line 8 of Algorithm 1 requires checking the condition

$\displaystyle\exists u\in\mathcal{U}\text{ s.t.
}\overline{P}_{u}([x])\subseteq\Omega,$ (5)

which is a nonconvex feasibility problem, due to the nonconvexity of $\Omega$.
Luckily, we can exploit the structure of both $\overline{P}_{u}([x])$ and
$\Omega$ in order to efficiently and precisely compute the set of $u$ that
satisfy (5).

Notice that, in the definition of $\overline{P}_{u}$, the term
$A[x]\oplus[\Phi]([x])\oplus[\Psi]([x])\mathcal{U}$ is a convex polyhedron,
and the additive term $Su$ serves only to _translate_ the resulting
polyhedron. On the other hand, $\Omega$ is a union of intervals, and also more
generally a union of polyhedra. Therefore, we can reduce the feasibility
problem in (5) to a problem of translating a polyhedron into a union of
polyhedra. We describe here an equivalence which helps solve this problem,
inspired by [17].

######  Lemma 3.

Let $\mathcal{P}=\operatorname{conv}(\Omega\cap\overline{P}([x]))$ and
$\mathcal{Q}=\mathcal{P}\setminus(\Omega\cap\overline{P}([x]))$. Then, the
following statements are equivalent:

  1. 1.

$\exists u\in\mathcal{U}\text{ s.t. }\overline{P}_{u}([x])\subseteq\Omega$;

  2. 2.

$S\mathcal{U}([x])\triangleq\mathcal{I}(\overline{P}_{0}([x]),\mathcal{P})\setminus\mathcal{O}(\overline{P}_{0}([x]),\mathcal{Q})\neq\emptyset.$

###### Proof.

By defining $\overline{P}_{0}([x])\triangleq
A[x]\oplus[\Phi]([x])\oplus[\Psi]([x])\mathcal{U}$, we obtain that for any
$u$, $\overline{P}_{u}([x])=\overline{P}_{0}([x])\oplus\\{Su\\}$. Furthermore,
$\overline{P}([x])=\overline{P}_{0}([x])\oplus S\mathcal{U}$. This gives rise
to the equivalance

$\displaystyle\exists u\in\mathcal{U}\text{ s.t.
}\overline{P}_{u}([x])\subseteq\Omega$ $\displaystyle\iff\exists
r\in{}^{n}\text{ s.t.
}\overline{P}_{0}([x])\oplus\\{r\\}\subseteq\Omega\cap\overline{P}([x]),$

where it must be true that $r=Su$. We see that by intersecting with
$\overline{P}([x])$ on the right hand side, we can identify a translation by a
vector $r$, which is automatically restricted to the range of $S$. To find the
$r$ in the latter expression, we first find the translations into the _convex
hull_ of $\Omega\cap\overline{P}([x])$ (i.e.,
$\mathcal{I}(\overline{P}_{0}([x]),\mathcal{P})$), then remove the
translations that cause overlap with parts of the convex hull that are not in
the original set (i.e., $\mathcal{O}(\overline{P}_{0}([x]),\mathcal{Q})$).
This gives the set of translations $r$ that result in containment in
$\Omega\cap\overline{P}([x])$, therefore yielding the expression for
$S\mathcal{U}([x])$. ∎

Since $S\mathcal{U}([x])$ is the difference between a polytope and a union of
polytopes, it can be expressed as the union of a finite number of polytopes.
The equivalence in Lemma 3 gives us a tractable method of solving the
feasibility problem in (5), using procedures to efficiently compute
$\mathcal{I}$ and $\mathcal{O}$. Finally, since $\forall r\in
S\mathcal{U}([x]),\ \exists u\in\mathcal{U}$ such that $r=Su$, we can recover
the set of inputs with the Moore-Penrose pseudoinverse,
$\mathcal{U}([x])=S^{\dagger}(S\mathcal{U}([x]))$, which is stored/saved in
$\mathcal{U}_{I}$ as pairs $([x],\mathcal{U}([x]))$.

######  Remark 2.

The computation of the set difference between two polyhedra can be represented
as a union of polyhedra. This procedure is computationally expensive,
especially when considering the difference between a polyhedron and a union of
polyhedra, for which the best algorithms [18] have exponential complexity. In
fact, the computation of set differences is the largest computaional burden of
our method. Caching of results from previous iterations may reduce the number
of differences that must be computed in the final implementation, although
these details are not described here for the sake of brevity. $\bullet$

We finish this section by proving that Algorithm 1 returns a useful
approximation of $I(\Omega)$, which is within some known bound of the maximal
CIS.

######  Lemma 4.

Let $\Omega$ be a finite union of compact intervals. Then, for any precision
$\varepsilon>0$, Algorithm 1 terminates in a finite number of iterations.
Furthermore, letting $\underline{I}(\Omega)$ denote the output of Algorithm 1,
it holds that

$\displaystyle I(\Omega\ominus\mathcal{B}_{\rho\varepsilon})\subseteq
I_{\rho\varepsilon}(\Omega)\subseteq\underline{I}(\Omega)\subseteq I(\Omega).$
(6)

###### Proof.

The proof is similar to [9, Lemma 1], relying on the bounds provided by Lemma
2. ∎

###  IV-C Near-Maximal Controlled Invariant Sets

With the ability to compute $\underline{I}(\Omega)$ using Algorithm 1, all
that remains is to repeat this operation until convergence is achieved.
Algorithm 2 describes this simple procedure, which is guaranteed to terminate
in finite time.

Algorithm 2 Approximation of $I^{\infty}(\Omega)$

1:$\Omega$, $\varepsilon$

2:$I_{0}\leftarrow\Omega$, $I_{1}\leftarrow\emptyset$

3:while $I_{0}\neq I_{1}$ do

4: $I_{1}\leftarrow I_{0}$

5: $I_{0}\leftarrow\underline{I}(I_{0})$ $\triangleright$ via Algorithm 1

6:end while

7:return $I_{0}$

######  Theorem 1.

For any finite union of compact intervals $\Omega$ and precision
$\varepsilon>0$, Algorithm 2 terminates in a finite number of iterations.
Furthermore, denoting the output of the algorithm as
$\underline{I}^{\infty}(\Omega)$, the following inclusions hold:

$\displaystyle
I_{r}^{\infty}(\Omega)\subseteq\underline{I}^{\infty}(\Omega)\subseteq
I^{\infty}(\Omega),$

where $r=\rho\varepsilon$. Finally, $\underline{I}^{\infty}(\Omega)$ is
controlled invariant.

Note that it is possible for the algorithm to return an empty set only if the
system does not admit an $r$-robustly controlled invariant set, meaning
$I_{r}^{\infty}=\emptyset$.

###### Proof.

Let $\underline{I}^{k}(\Omega)$ denote the value of
$\underline{I}(\underline{I}^{k-1}(\Omega))$ in the $k$-th iteration, with
$\underline{I}^{0}(\Omega)=\Omega$. Since the algorithm terminates if
$\underline{I}^{k-1}(\Omega)=\underline{I}^{k}(\Omega)$, we only need to
consider the case when they are not equal. In this case, the structure of
Algorithm 1 is such that
$\underline{I}^{k}(\Omega)\subsetneq\underline{I}^{k-1}(\Omega)$. Since
$\Omega$ is compact, $\underline{I}^{k}(\Omega)$ contains only a finite number
of intervals which will be considered using the bisection method for a given
$\varepsilon$. Then $\exists K\geq 0$ such that
$\underline{I}^{k}(\Omega)=\emptyset,\ \forall k\geq K$, meaning the algorithm
terminates in finite time.

To prove the inclusions, note that by Lemma 4,
$I_{r}(\Omega)\subseteq\underline{I}(\Omega)\subseteq I(\Omega)$. Also, for
any two sets $A\subseteq B\subseteq{}^{n}$, we know that
$\underline{I}(A)\subseteq\underline{I}(B)$ and $I_{r}(A)\subseteq I_{r}(B)$.
Therefore by applying Lemma 4 and induction, we can determine that
$I_{r}^{k}(\Omega)\subseteq\underline{I}^{k}(\Omega)\subseteq I^{k}(\Omega)$
for all $k\geq 0$.

Finally, to prove invariance of $\underline{I}^{\infty}(\Omega)$, note that by
Lemma 4,
$\underline{I}^{\infty}(\Omega)=\underline{I}(\underline{I}^{\infty}(\Omega))\subseteq
I(\underline{I}^{\infty}(\Omega))$. ∎

######  Remark 3 (An Outside-In Approach).

The method described in this paper is commonly known as an _outside-in_
method, since we start with a region of interest $\Omega$ and search for the
largest invariant set $\mathcal{X}=I^{\infty}(\Omega)$ which it contains. It
is also possible to use an _inside-out_ approach, which starts with a known
invariant set, and iteratively grows that set [10]. Our method can be easily
adapted for this case, as well. $\bullet$

To conclude this section, we state a result that has the potential to
significantly reduce the number of iterations required by Algorithm 2, hence,
accelerating convergence. Let $\\{\Omega_{i}\\}_{i=1}^{N}$ be any _ordered_
collection of sets such that $\Omega=\bigcup_{i=1}^{N}\Omega_{i}$. Define the
operator

$\displaystyle I_{i}(\Omega)\triangleq\bigcup_{j\neq
i}\Omega_{j}\cup\left(Q(\Omega)\cap\Omega_{i}\right),$

and let $I_{1:N}\triangleq I^{N}(\cdots(I^{1}(\Omega))$. We let the $I_{i}$
operator preserve the order of the constituent subsets by defining

$\displaystyle(I_{i}(\Omega))_{i}=Q(\Omega)\cap\Omega_{i}\quad\text{and}\quad(I_{i}(\Omega))_{j}=\Omega_{j},\
j\neq i.$

######  Theorem 2.

For a closed set $\Omega\subseteq{}^{n}$, $I_{1:N}$ satisfies

$\displaystyle I_{1:N}(\Omega)\subseteq I(\Omega),\text{ and }$
$\displaystyle\lim_{k\to\infty}(I_{1:N})^{k}(\Omega)=\lim_{k\to\infty}I^{k}(\Omega)=I^{\infty}(\Omega).$
(7)

###### Proof.

By definition, for any $i\neq j$,

$\displaystyle I_{i}(I_{j}(\Omega))$ $\displaystyle=\bigcup_{\ell\neq
i}I_{j}(\Omega)_{\ell}\cup\left(Q(I_{j}(\Omega))\cap I_{j}(\Omega)_{i}\right)$
$\displaystyle=\bigcup_{\ell\neq i,\ell\neq
j}\Omega_{\ell}\,\cup\left(Q(\Omega)\cap\Omega_{j}\right)\cup\left(Q(I_{j}(\Omega))\cap
I_{j}(\Omega)_{i}\right)$ $\displaystyle\subseteq\bigcup_{\ell\neq i,\ell\neq
j}\Omega_{\ell}\cup\left(Q(\Omega)\cap(\Omega_{i}\cup\Omega_{j})\right),$

since $I_{j}(\Omega)_{i}\subseteq\Omega_{i}$ and $Q(I_{j}(\Omega))\cap
I_{j}(\Omega)_{i}\subseteq Q(\Omega)\cap\Omega_{i}$. By applying this
statement recursively, we arrive at

$\displaystyle I_{1:N}(\Omega)\subseteq\bigcup_{i=1}^{N}\Omega_{i}\cap
Q(\Omega)=I(\Omega).$ (8)

In (7), since $I_{1:N}$ is monotonically decreasing and closed, the limit
exists. We will show by induction that for all $k\geq 0$,
$(I_{1:N})^{k}(\Omega)\supseteq I^{\infty}(\Omega)$. Consider a point $x\in
I^{\infty}(\Omega)$. We know $x\in Q(I^{\infty}(\Omega))\subseteq Q(\Omega)$.
Therefore, by the definition of $I_{1}$, $x\in I_{1}(\Omega)$, meaning
$I_{1}(\Omega)\supseteq I^{\infty}(\Omega)$. By repeating this reasoning for
$I_{2},\dots,I_{N}$, we can see that $I_{1:N}(\Omega)\supseteq
I^{\infty}(\Omega)$. For the step case, assume that
$(I_{1:N})^{k-1}(\Omega)\supseteq I^{\infty}(\Omega)$. Then by the same
argument as the base case, for any $x\in I^{\infty}(\Omega)$, $x\in
Q(I^{\infty}(\Omega))\subseteq Q((I_{1:N})^{k-1}(\Omega))$, implying
$(I_{1:N})^{k}(\Omega)\supseteq I^{\infty}(\Omega)$. Using this fact in
combination with (8), monotonicity of $I$ and $I_{1:N}$, and an induction
argument proves (7). ∎

Theorem 2 is useful because it allows us to independently consider individual
regions of the invariant set, rather than approximating the $I$ operator all
at once. Essentially, our procedure can focus on $I_{i}(\Omega)$ without
needing to compute all of $Q(\Omega)$, which is more expensive. Using the
$I_{i}$ operator often leads to a reduction in the total number of iterations
required. Algorithm 3 describes the modified procedure that takes advantage of
this fact. In the algorithm, $\Omega$ is updated whenever an interval is
determined to not be a part of the invariant set. The loop terminates if every
interval in the queue has been checked since $\Omega$ was last changed,
meaning every interval is contained in the invariant set. The function
$\operatorname{checked}$ tracks whether a given $[x]$ has been tested against
the current $\Omega$. It defaults to $0$, and is assigned a value of $1$ after
$[x]$ is processed. Note that $\operatorname{push\\_back}$ places an item in
the back of the queue.

Algorithm 3 Accelerated Approximation of $I^{\infty}(\Omega)$

1:$\Omega$, $\varepsilon$

2:$Q\leftarrow\\{\Omega\\}$, $N\leftarrow\emptyset$,
$\underline{I}\leftarrow\emptyset$, $\mathcal{E}\leftarrow\emptyset$,
$\mathcal{U}_{I}\leftarrow\emptyset$

3:while $\exists[x]\in Q$, $\operatorname{checked}([x],\Omega)=0$ do

4: $[x]\leftarrow\operatorname{pop\\_front}(Q)$

5: Compute $A$, $\Phi$, $s_{i}$, and $\Psi_{i}$ on $[x]$

6: if $\overline{P}([x])\cap\Omega=\emptyset$ then

7: $N\leftarrow N\cup[x]$

8: $\Omega\leftarrow\Omega\setminus[x]$

9: else if $\exists u\in\mathcal{U}\text{ s.t.
}\overline{P}_{u}([x])\subseteq\Omega$ then

10: $\operatorname{checked}([x],\Omega)\leftarrow 1$

11: $\operatorname{push\\_back}(Q,[x])$

12:
$\mathcal{U}_{I}\leftarrow\mathcal{U}_{I}\cup([x],S^{\dagger}(S\mathcal{U}([x])))$

13: else if $w([x])\leq\varepsilon$ then

14: $\mathcal{E}\leftarrow\mathcal{E}\cup[x]$

15: $\Omega\leftarrow\Omega\setminus[x]$

16: else

17: $(l,r)\leftarrow\operatorname{bisect}([x])$

18: $\operatorname{push\\_front}(Q,l)$

19: $\operatorname{push\\_front}(Q,r)$

20: end if

21:end while

22:$\underline{I}^{\infty}\leftarrow\bigcup_{[x]\in Q}[x]$

23:return $\underline{I}^{\infty}$, $\mathcal{U}_{I}$

######  Lemma 5.

For any finite union of compact intervals $\Omega$ and precision
$\varepsilon>0$, Algorithm 3 returns the same result as Algorithm 2.
Furthermore, the number of iterations required by Algorithm 3 is less than or
equal to the number required by Algorithm 2.

###### Proof.

The first statement can be proved by the same reasoning as Theorem 1. The
second statement arises from the inclusion $I_{1:N}(\Omega)\subseteq
I(\Omega)$ (cf. Theorem 2) and can also be seen by direct comparison of the
algorithms. ∎

##  V Examples and Comparisons

In this section, we demonstrate the effectiveness of our approach on a
numerical example, i.e., an inverted pendulum on a cart. We also compare our
approach to the method for switched systems in [9], where the input space is
sampled/gridded and considered as controlled modes.

As in [9], we consider an inverted pendulum on a cart, discretized using
forward Euler with a sampling time of $0.01\text{s}$. The dynamics are

$\displaystyle\dot{x}_{1}$ $\displaystyle=x_{2},$ $\displaystyle\dot{x}_{2}$
$\displaystyle=\frac{mgl}{J}\sin(x_{1})-\frac{b}{J}x_{2}+\frac{l}{J}\cos(x_{1})u,$

with parameters $m=0.2$ kg, $g=9.8$ $\text{m}/\text{s}^{2}$ , $l=0.3$ m,
$J=0.006$ $\text{kg}\cdot\text{m}^{2}$, and $b=0.1$
$\text{N}/\text{m}/\text{s}$. This system and its discretization are control
affine. We consider a region of interest
$\Omega=[-0.05,-0.05]\times[-0.01,0.01]$ and an input set
$\mathcal{U}=[-0.1,0.1]$.

Figure 1: Controlled invariant sets of the inverted pendulum system. Figure 2:
Union of invariance-enforcing inputs $\mathcal{U}([x])$ identified by Lemma 3.

Figure 1 shows the identified controlled invariant sets for our approaches,
i.e., using Algorithms 2 and 3, and that of [9], with $n_{u}=10$ and
$n_{u}=1000$ sampled inputs. All methods were run with a precision
$\varepsilon=0.001$. On the other hand, Figure 2 shows the union of all
invariance-enforcing control inputs $\mathcal{U}([x])$ identified by
Algorithms 2 and 3. Finally, Table I shows a comparison of computation times
with different parameters.

Method | $\varepsilon$ | Iterations | Time (s) | Volume
---|---|---|---|---
Algorithm 2 | $10^{-3}$ | 703 | 0.54 | 97.9%
Algorithm 3 | $10^{-3}$ | 618 | 0.63 | 97.9%
[9] ($n_{u}=10$) | $10^{-3}$ | 10729 | 0.12 | 59.8%
[9] ($n_{u}=1000$) | $10^{-3}$ | 485 | 0.59 | 97.9%
TABLE I: Computational comparison between Algorithm 2, Algorithm 3, and [9].
$n_{u}$ denotes the number of input samples taken uniformly across
$\mathcal{U}$. The volume is given in % of the original $\Omega$.

Evidently, our method is able to identify a larger CIS in fewer iterations
than the sampling and interval arithmetic based approach in [9], when the
number of samples is small. This is presumably due to the higher accuracy of
our polytopic approximations, and the fact that we consider the entire
continuous range of control inputs. Increasing the number of sampled inputs
results in a better approximation of the CIS, at the cost of some additional
computation time.

##  VI Conclusion

We proposed two methods for approximating controlled invariant sets of
nonlinear control-affine systems using an iterative refinement approach. We
used techniques from computational geometry involving translations of
polyhedra to allow us to efficiently compute continuous sets of feasible
control inputs, rather than using a sampling approach with switched dynamics.
We demonstrated the effectiveness of our method on a numerical example, which
showed improved accuracy over existing methods and led to faster convergence
in some cases. In the future, we will further explore the extension of our
approach to continuous time, as well as the control synthesis problem,
including some notions of optimality, while also investigating ways to improve
the accuracy and efficiency of our algorithms. We also will test our
approaches on a wide variety of nonlinear systems.

###  -A Proof of Proposition 2

We begin by stating two intermediate results which will be used to prove the
proposition. The first allows us to determine whether two polytopes intersect
by examining the hyperplanes defining each polytope.

######  Proposition 4.

Given two polytopes $\mathcal{P}$ and $\mathcal{Q}$,
$\mathcal{P}\cap\mathcal{Q}\neq\emptyset$ if and only if both of the following
statements are true

  1. 1.

$\mathcal{P}$ intersects every halfspace defining $\mathcal{Q}$, i.e.,
$\forall i\in\\{1,\dots,N_{\mathcal{Q}}\\},\ \exists p_{i}\in\mathcal{P}$ such
that $(H_{\mathcal{Q}})_{i}p_{i}\leq(b_{\mathcal{Q}})_{i}$.

  2. 2.

$\mathcal{Q}$ intersects every halfspace defining $\mathcal{P}$, i.e.,
$\forall i\in\\{1,\dots,N_{\mathcal{P}}\\},\ \exists q_{i}\in\mathcal{Q}$ such
that $(H_{\mathcal{P}})_{i}q_{i}\leq(b_{\mathcal{P}})_{i}$.

###### Proof.

Necessity is simple, since if $\mathcal{P}\cap\mathcal{Q}\neq\emptyset$, every
$v\in{\mathcal{P}\cap\mathcal{Q}}$ will satisfy the existence conditions in 1)
and 2).

To prove sufficiency, note that $\mathcal{P}\cap\mathcal{Q}=\emptyset$ if and
only if there exists a separating hyperplane, defined by some $h_{*}\in{}^{n}$
and $b_{*}\in\real$, such that $\forall v\in\mathcal{P},\ h^{\top}v\leq b$ and
$\forall v\in\mathcal{Q},\ h^{\top}v>b$. Conditions 1) and 2) preclude the
existence of this separating hyperplane, implying
$\mathcal{P}\cap\mathcal{Q}\neq\emptyset$. ∎

The second intermediate result tells us how to translate a polytope so that it
intersects a given halfspace.

######  Proposition 5.

Given a polytope $\mathcal{P}$ and halfspace $\mathcal{H}=\\{x:h^{\top}x\leq
b\\}$, the set of translations, i.e., of $\mathcal{P}$ that intersect
$\mathcal{H}$; i.e.
$\mathcal{O}(\mathcal{P},\mathcal{H})\triangleq\\{s\in{}^{n}:\mathcal{P}\oplus\\{s\\}\cap\mathcal{H}\neq\emptyset\\}$,
is given by

$\displaystyle\mathcal{O}(\mathcal{P},\mathcal{H})=\\{s\in{}^{n}:\
h^{\top}s\leq b-\alpha\\},$

where $\alpha=\min_{v\in V_{\mathcal{P}}}h^{\top}v$.

###### Proof.

The reasoning is similar to [13, Theorem 2.3], with $\min$ replacing $\max$
because intersection, rather than containment, is required. ∎

Proposition 2 follows from the combination of Proposition 4 with repeated
application of Proposition 5 to every halfspace defining both $\mathcal{P}$
and $\mathcal{Q}$ (with $-s$ replacing $s$ in the second part, as the
translation is applied to $\mathcal{P}$, not $\mathcal{Q}$).

## References

  * [1] F. Blanchini, “Set invariance in control,” _Automatica_ , vol. 35, no. 11, pp. 1747–1767, 1999.
  * [2] M. Fiacchini and M. Alamir, “Computing control invariant sets in high dimension is easy,” _arXiv preprint_ , 2018.
  * [3] M. Rungger and P. Tabuada, “Computing robust controlled invariant sets of linear systems,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 7, pp. 3665–3670, 2017.
  * [4] T. Anevlavis and P. Tabuada, “Computing controlled invariant sets in two moves,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 6248–6254.
  * [5] T. Anevlavis, Z. Liu, N. Ozay, and P. Tabuada, “An enhanced hierarchy for (robust) controlled invariance,” in _2021 American Control Conference (ACC)_ , 2021, pp. 4860–4865.
  * [6] M. Fiacchini, T. Alamo, and E. Camacho, “On the computation of convex robust control invariant sets for nonlinear systems,” _Automatica_ , vol. 46, no. 8, pp. 1334–1338, 2010.
  * [7] L. Schäfer, F. Gruber, and M. Althoff, “Scalable computation of robust control invariant sets of nonlinear systems,” _submitted to IEEE Transactions on Automatic Control. Available from https://mediatum.ub.tum.de/doc/1663416/document.pdf_ , 2022.
  * [8] S. Jang, N. Ozay, and J. L. Mathieu, “An invariant set construction method, applied to safe coordination of thermostatic loads,” _arXiv preprint_ , 2022\.
  * [9] Y. Li and J. Liu, “Invariance control synthesis for switched nonlinear systems: An interval analysis approach,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 7, pp. 2206–2211, 2018.
  * [10] J. Bravo, D. Limon, T. Alamo, and E. Camacho, “On the computation of invariant sets for constrained nonlinear systems: An interval arithmetic approach,” _Automatica_ , vol. 41, no. 9, pp. 1583–1589, 2005.
  * [11] L. Jaulin, M. Kieffer, O. Didrit, and E. Walter, “Applied interval analysis,” _ed: Springer, London_ , 2001.
  * [12] M. Khajenejad and S. Z. Yong, “Tight remainder-form decomposition functions with applications to constrained reachability and guaranteed state estimation,” _IEEE Transactions on Automatic Control_ , pp. 1–16, 2023.
  * [13] I. Kolmanovsky and E. Gilbert, “Theory and computation of disturbance invariant sets for discrete-time linear systems,” _Mathematical Problems in Engineering_ , vol. 4, pp. 317–367, 01 1998.
  * [14] D. Bertsekas, “Infinite time reachability of state-space regions by using feedback control,” _IEEE Transactions on Automatic Control_ , vol. 17, no. 5, pp. 604–613, 1972.
  * [15] M. Khajenejad, F. Shoaib, and S. Z. Yong, “Interval observer synthesis for locally Lipschitz nonlinear dynamical systems via mixed-monotone decompositions,” in _American Control Conference (ACC)_ , 2022, pp. 2970–2975.
  * [16] M. Khajenejad and S. Z. Yong, “Simultaneous input and state interval observers for nonlinear systems with full-rank direct feedthrough,” in _IEEE Conference on Decision and Control_ , 2020, pp. 5443–5448.
  * [17] B. Baker, S. Fortune, and S. Mahaney, “Polygon containment under translation,” _Journal of Algorithms_ , vol. 7, no. 4, pp. 532–548, 1986\.
  * [18] M. Baotic, “Polytopic computations in constrained optimal control,” _Automatika_ , vol. 50, pp. 119–134, 04 2009.