You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'We consider a distributed non cooperative control setting in which systems are interconnected via state constraints. Each of these systems is governed by an agent which is responsible for exchanging information with its neighbours and computing a feedback law using a nonlinear model predictive controller to avoid violations of constraints. For this setting we present an algorithm which generates a parallelizable hierarchy among the systems. Moreover, we show both feasibility and stability of the closed loop using only abstract properties of this algorithm. To this end, we utilize a trajectory based stability result which we extend to the distributed setting.'
address: |
    Faculty of Aerospace Engineering\
    University of the Federal Armed Forces\
    85577 Munich, Germany
author:
- Jürgen Pannek
title: Parallelizing a State Exchange Strategy for Noncooperative Distributed NMPC
---

nonlinear model predictive control ,stability ,parallel algorithm

Introduction
============

Distributed control problems can arise either naturally, i.e. by a set of coupled systems which shall be controlled, see, e.g., @DS2009, or if a large problem is decomposed into smaller, again coupled problems, see @RM2009 [Chapter 10] or @S2009 for an overview. In the latter case, the general idea is that smaller problems are solvable easier and faster which allows to even overcompensate the computational effort to coordinate these systems, cf. @RH2007 [Section 7]. In either case, one distinguishes between cooperative control which features a centralized objective, and non cooperative control where the objectives of the systems are independent from each other. Using a centralized objective there are several possibilities to divide the optimization problem into subproblems. If suitable conditions hold then similar performance of the distributed control obtained from these subproblems and of the centralized control can be shown, see, e.g., @RM2009 [Chapter 10] or @GR2010.

Throughout this work we focus on the non cooperative control setting of systems driven by independent dynamics and control objectives, but coupled by constraints. For each system we impose an agent which exchanges state information with its neighbours and uses its local objective to compute a local control which satisfies the coupling constraints. For the computing task we focus on feedback design via nonlinear model predictive controller (NMPC) which minimizes the distance of the current state to the desired equilibrium over a finite time horizon. To show asymptotic stability of an NMPC closed loop, one often imposes additional stabilizing terminal constraints and costs, see, e.g., @KG1988 or @ChAl1998 respectively. Since such terminal constraints may require long optimization horizons, we focus on the plain NMPC setting without those modifications. In the non distributed case, stability for such problems has been shown in @GPSW2010 whereas the distributed case is treated in @GW2010 using the algorithm of Richards and How [@RH2004; @RH2007].

Here, we first prove a stability idea outlined in @GW2010 using the trajectory based setting of @GP2011 [Chapter 7]. This proof allows us to reduce the horizon length in the distributed case while maintaining suboptimality estimates and stability like behavior of the closed loop. Secondly, since the computing time of the NMPC control law for each agent is not negligible, we present an algorithm which allows us to execute these computations in parallel using priority and deordering rules as well as a decision memory. From @RM2009 [Chapter 10] it is known that for the non cooperative control setting one can only expect to reach a Nash equilibrium. Although such a solution may be far from the optimal centralized solution, the closed loop solutions may still be stable and maintain the coupling constraints. For the proposed algorithm we present conditions under which feasibility of the closed loop is guaranteed and present necessary as well as sufficient conditions for asymptotic stability using only abstract properties of both the priority and the deordering rule. While here we focus on the plain NMPC case, we also outline how feasibility and stability results can be obtained using NMPC with terminal constraints or cost.

The paper is organized as follows: First, in Section \[Section:Setup and Preliminaries\] we formally define the problem under consideration for which we show different stability results for the distributed case in Section \[Section:Stability\]. In the central Section \[Section:The covering algorithm\], we present a covering algorithm which allows us to generate a hierarchy of agents and run the computations of each hierarchy level in parallel. Using this algorithm, we show necessary and sufficient conditions for feasibility and stability of the resulting closed loop and also how much parallelism can be achieved. Instead of a separated example section, we use an analytical example throughout the entire work to present the improvement of the stability result but also to illustrate the abstract functions used within the proposed algorithm in Section \[Section:The covering algorithm\]. Finally, we draw conclusions in Section \[Section:Conclusion\] and present ideas for future research based on the presented work.

Setup and Preliminaries {#Section:Setup and Preliminaries}
=======================

Throughout this work we consider a set of nonlinear discrete time systems $$\begin{aligned}
    \label{Setup and Preliminaries:system p}
    \xp(n + 1) = \fp(\xp(n), \up(n)), \qquad p \in \cP := \{ 1, \ldots ,P\}, n \in \N_0\end{aligned}$$ with $\xp (n) \in \Xp$ and $\up(n) \in \Up$ and $\N_0$ denoting the set of natural numbers including zero. Here, $\Xp$ and $\Up$, $p \in \cP$, are assumed to be arbitrary metric spaces denoting the state space and the set of admissible control values of the $p$-th system, respectively. The metrics to measure distances between two elements of $\Xp$ or of $\Up$ are denoted by $d_{\Xp}: \Xp \times \Xp \to \R_{\geq 0}$ and $d_{\Up}: \Up \times \Up \to \R_{\geq 0}$ where $\R_{\geq 0}$ denotes the positive reals including zero. In the following we denote the solution of a system $p$ of corresponding to the initial value $\xp(0) = \xpzero$ and the control sequence $\up(k) \in \Up$, $k = 0, 1, 2, \ldots$, by $\xpu(k, \xpzero)$.

In order to define our goal we say that a continuous function $\alpha: \R_{\geq 0} \rightarrow \R_{\geq 0}$ is of class $\cK_\infty$ if it satisfies $\alpha(0) = 0$, is strictly increasing and unbounded. A continuous function $\gamma: \R_{\geq 0}^P \to \R_{\geq 0}$ is called a class $\cK_\infty^P$ function if it satisfies $\gamma(0) = 0$, is strictly increasing in each component and is unbounded. A continuous function $\beta: \R_{\geq 0} \times \R_{\geq 0} \rightarrow \R_{\geq 0}$ is of class $\cKL$ if it is strictly decreasing in its second argument with $\lim_{t \rightarrow \infty} \beta(r, t) = 0$ for each $r > 0$ and satisfies $\beta(\cdot, t) \in \cK_\infty$ for each $t \geq 0$. Moreover, $\cB_r(x)$ denotes the open ball with center $x$ and radius $r$ and for arbitrary $x_1, x_2 \in \X$ we denote the distance from $x_1$ to $x_2$ by $\| x_1 \|_{x_2} = d_{\X}(x_1, x_2)$.

For the set of systems the overall system is given by $$\begin{aligned}
    \label{Setup and Preliminaries:system}
    x(n + 1) = f(x(n), u(n)), \qquad n \in \N_0\end{aligned}$$ with state $x(n) = ( x_1(n)^\top, \ldots, x_P(n)^\top)^\top \in \X = \X_1 \times \ldots \times \X_P$ and control $u(n) = (u_1(n)^\top, \ldots, u_P(n)^\top)^\top \in \U =\U_1 \times \ldots \times \U_P$. Now, our goal is to asymptotically stabilize system at a desired equilibrium point $\xref \in \X$, i.e. to fulfill the following:

\[Setup and Preliminaries:def:stability\] Let $\xref \in \X$ be an equilibrium for a system , i.e., there exists $u \in \U$ such that $f(\xref,u)=\xref$. Then we say that $\xref$ is [*locally asymptotically stable*]{} if for a given control sequence $(u(n))_{n \in \N_0}$ there exist $r>0$ and a function $\beta \in \cKL$ such that the inequality $$\label{Setup and Preliminaries:def:stability:eq1}
        \| x^u(n, x^0) \|_{\xref} \leq \beta( \| \xzero \|_{\xref}, n)$$ holds for all $\xzero \in \cB_r(\xref)$ and all $n\in\N_0$.

Additionally, the solution $x^u(\cdot, \xzero)$ shall satisfy state and control constraints. Throughout this work, we incorporate such constraints by considering suitable subsets of the overall state and control value space $\bX \subset \X$, $\bU \subset \U$ for system . As a result, systems are coupled via the constraint sets $\bX$ and $\bU$ although the respective dynamics are decoupled. The following example illustrates this setting and will be used throughout this paper.

\[Setup and Preliminaries:example\] Consider two cars attempting to cross a one lane brigde, i.e. one car has to wait, cf. Figure \[Setup and Preliminaries:fig:carexample\] for an illustration. Suppose the discrete time dynamics of the cars are given by $$\begin{aligned}
        \xp(n + 1) = \xp(n) + \up(n)
    \end{aligned}$$ with $\up \in \bUp = \{-1, 0, 1\}^2$ and $\xp \in \bZ^2$ for $p = 1, 2$. Since the cars shall not collide, we obtain the restriction $$\begin{aligned}
        \label{Setup and Preliminaries:example:collision constraint}
        ( x_{1,1}, x_{1,2} )^\top \not = (x_{2,1}, x_{2,2} )^\top.
    \end{aligned}$$ The one lane bridge additionally imposes the constraints $$\begin{aligned}
        \label{Setup and Preliminaries:example:blocking constraint}
        & x_{p,2} = 0 \text{ if } x_{p,1} = 0 \; \text{for $p = 1, 2$} \quad \text{and} \\
        \label{Setup and Preliminaries:example:passing constraint}
        & \left( \begin{array}{c} x_{1,1} + u_{1,1} \\ x_{1,2} + u_{1,2} \end{array} \right) \not = \left( \begin{array}{c} x_{2,1} \\ x_{2,2} \end{array} \right), \quad
        \left( \begin{array}{c} x_{1,1} \\ x_{1,2} \end{array} \right) \not = \left( \begin{array}{c} x_{2,1} + u_{2,1} \\ x_{2,2} + u_{2,2} \end{array} \right)
    \end{aligned}$$ which together form the set $\bX$. Hence, the local set of admissible moves may depend on which car is allowed to drive first, cf. Figures \[Setup and Preliminaries:fig:carexample0\] and \[Setup and Preliminaries:fig:carexample1\]. Note that is the only local constraint whereas — if they are considered – induces an algebraic and a neighbouring dynamic dependent coupling.

The purpose of this work is to show conditions under which stability of the overall systems can be guaranteed by using only local controllers. To this end, we impose an agent for each system $p \in \cP$ to compute a suitable control sequence $\up(\cdot) \in \Up^{\N_0} := \{ \up(k) \mid \up(k) \in \Up \forall k \in \N_0 \}$ and to exchange information with other agents in order to verify that the constraints $\bX \subset \X$, $\bU \subset \U$ are satisfied. Throughout this work each agent computes its control sequence via a nonlinear model predictive controller, a methodology which will be explained after Definition \[Setup and Preliminaries:set of admissible control sequences\], below. In order to achieve asymptotic stability of the overall system we develop a covering algorithm to coordinate all agents. The idea of this algorithm is the following: Since some subsystems impose constraints on each other, a priority rule is used to generate a hierarchy among the subsystems. As a result, agents which are on the same hierarchy level can compute their local optimal control in parallel while the hierarchy levels remain in serial. Additionally, a deordering rule is introduced to repeatedly verify if the hierarchy can be flattened, i.e. if more agents can work in parallel. For details on these rules we refer to Section \[Section:The covering algorithm\].

Since we want to compute local controls $\up$ we must define the local constraints for each single system $\fp$, $p \in \cP$. To this end, we “project” the constraint set $\bX$ to the state space of a subset of systems.

\[Setup and Preliminaries:def:partial state contraints\] For an index set $\cIp = \{ p_1, \ldots, p_m \} \subset \cP$ with $m \in \N$, $m \leq P$ and $p_i \not = p_j$ for all $i, j \in \{1, \ldots, m\}$ the *set of partial states* is defined as $\X_{\cIp} = \X_{p_1} \times \ldots \times \X_{p_m}$ and we denote elements of $\X_{\cIp}$ by $x_{\cIp} = (x_{p_1}, \ldots, x_{p_m})$. Accordingly, the *partial state constraint set* is defined by $$\begin{aligned}
        \bX_{\cIp} := \{ x_{\cIp} \in \X_{\cIp} \mid \text{there is $\tilde{x} \in \bX$ with $\tilde{x}_{p_i} = x$ for $i = 1, \ldots, m$} \}.
    \end{aligned}$$

In case of Example \[Setup and Preliminaries:example\], Definition \[Setup and Preliminaries:def:partial state contraints\] basically means that only those constraints induced by the neighbours contained in $\cIp$ have to be considered, i.e. if agent $p = 1$ ignores agent $p=2$, then only constraint has to be fulfilled. In the general case, this task can be accomplished by using information on neighbouring systems which are available to an agent and allow to generate a hierarchy among the agents. Here, we assume that this information can be exchanged repeatedly in between two time instants $n$ and $n + 1$. Throughout this work we consider changing network topologies, i.e. the sets of neighbours at time instants $n$ and $n + 1$ may differ, see Figure \[Setup and Preliminaries:fig:communication\] for an illustration.

(0.0,0.2)(4.5,4.2) (1.0,1.0) (4.0,1.0) (1.0,4.0) (4.0,4.0) (1.0,1.0)[$x_1$]{} (4.0,1.0)[$x_2$]{} (4.0,4.0)[$x_3$]{} (1.0,4.0)[$x_4$]{} (1.1,1.0)(3.9,1.0) (1.1,1.1)(3.9,3.9) (1.0,1.1)(1.0,3.9) (3.9,1.1)(1.1,3.9) (4.0,1.1)(4.0,3.9) (3.9,4.0)(1.1,4.0) (2.5,0.7)[Time instant $n$]{}

(0.0,0.2)(4.5,4.2) (1.0,1.0) (4.0,1.0) (1.0,4.0) (4.0,4.0) (1.0,1.0)[$x_1$]{} (4.0,1.0)[$x_2$]{} (4.0,4.0)[$x_3$]{} (1.0,4.0)[$x_4$]{} (1.1,1.0)(3.9,1.0) (1.0,1.1)(1.0,3.9) (4.0,1.1)(4.0,3.9) (3.9,4.0)(1.1,4.0) (2.5,0.7)[Time instant $n + 1$]{}

Additionally, we allow the case that even if neighbouring information of a system $q \in \cP \setminus \{ p \}$ is known to an agent $p \in \cP$, agent $p$ ignores that information if his hierarchy level is higher than the level of the neighbour. Consequently, the dependency graph which results from this hierarchy may differ from the communication graph as illustrated in Figure \[Setup and Preliminaries:fig:communication and dependency\].

(0.0,0.8)(4.5,4.2) (1.0,1.0) (4.0,1.0) (1.0,4.0) (4.0,4.0) (1.0,1.0)[$x_1$]{} (4.0,1.0)[$x_2$]{} (4.0,4.0)[$x_3$]{} (1.0,4.0)[$x_4$]{} (1.1,1.0)(3.9,1.0) (1.1,1.1)(3.9,3.9) (1.0,1.1)(1.0,3.9) (3.9,1.1)(1.1,3.9) (4.0,1.1)(4.0,3.9) (3.9,4.0)(1.1,4.0)

(0.0,0.8)(4.5,4.2) (1.0,1.0) (4.0,1.0) (1.0,4.0) (4.0,4.0) (1.0,1.0)[$x_1$]{} (4.0,1.0)[$x_2$]{} (4.0,4.0)[$x_3$]{} (1.0,4.0)[$x_4$]{} (1.1,1.0)(3.9,1.0) (1.1,1.1)(3.9,3.9) (1.0,1.1)(1.0,3.9)

Moreover, as sent information may be delayed or even lost, we want to allow for considering old information on neighbours and variable lengths of this information. Note that the latter may also allow agents to skip recomputations of controls. Introducing $N_q$ as the length and $n_q$ as the time instant at which neighbour $q$ has computed the state sequence $(x_q^{n_q}(0), \ldots, x_q^{n_q}(N_q))$, we define the exchanged neighbouring information as follows:

\[Setup and Preliminaries:neighbouring information\] Suppose that at time instant $n \in \N_0$ agent $p$ knows the state sequences $x_q^{n_q}(\cdot) = (x_q^{n_q}(0), \ldots, x_q^{n_q}(N_q))$, $N_q \in \N_0$, computed at time instant $n_q \leq n$ for a given *neighbouring index set* $\cIp(n)$, that is $q \in \cIp(n)$ with $p \not \in \cIp(n)$. We define the *neighbouring information* as $$\begin{aligned}
        \ip(n) = \{ (q, n_q, N_q, x_q^{n_q}(\cdot)) \mid q \in \cIp(n) \}
    \end{aligned}$$ being an element of the set $\bIp = 2^Q \mbox{ with } Q = ( \cP \setminus \{ p \} ) \times \N_0 \times \N_0 \times \X^{\N}$.

Knowing the states of neighbouring systems for a certain time period, we can define the index set used within the “projection” of the constraint set $\bX$.

\[Setup and Preliminaries:neighbouring prediction index set\] For a given time instant $n \in \N_0$ and an agent $p \in \cP$ with neighbouring information $\ip(n)$, we call the set of systems $q \in \cIp(n) \setminus \{p\}$ which are imposing constraints on system $p$ at time instant $n + k \in \N_0$, $k \geq 0$ *neighbouring prediction index set*. This set is given by $$\begin{aligned}
        \cIp(n, k) = \{ q \in \cIp(n) \setminus \{p\} \mid n + k \leq n_q + N_q \}.
    \end{aligned}$$

Similar to possible moves of the cars in Example \[Setup and Preliminaries:example\], we can use the partial state constraint set connected to neighbouring information available to an agent and define the set of admissible controls from which the control sequence $\up(\cdot)$ can be chosen, cf. Figures \[Setup and Preliminaries:fig:carexample0\], \[Setup and Preliminaries:fig:carexample1\].

\[Setup and Preliminaries:set of admissible control sequences\] Given a time instant $n \in \N_0$ and an agent $p \in \cP$ with initial value $\xpzero$ and neighbouring information $\ip(n)$, we define the *set of admissible control sequences* for system $p$ at time instant $n$ as $$\begin{aligned}
        \bUpad(n, \xpzero, \ip(n)) = \{ \up(\cdot) \in \Up^{\N_0} \mid & \mbox{ for all $k = 0, 1, \ldots$ we have $\up(k) \in \bUp$ and } \\
        & (\xpu(k, \xpzero), ( x_q^{n_q}(k + n - n_q) )_{\cIp(n, k)}) \in \bX_{\{p\} \cup \cIp(n, k)} \}.
    \end{aligned}$$

Using an NMPC algorithm is one possibility to compute a control from the set of admissible controls. In particular, the method tries to approximate a control sequence such that the functional $$\begin{aligned}
    \label{Setup and Preliminaries:cost functional infty}
    \Jpinfty(\xpzero, \up) = \sum\limits_{k = 0}^{\infty} \lp(\xpu(k, \xpzero), \up(k))\end{aligned}$$ is minimized over all admissible control sequences, that is sequences $\up(\cdot)$ with $\up(k) = \ups(0)$ for all $k \in \N_0$ with $\ups \in \bUpad(k, \xpu(k, \xpzero), \ip(k))$. Here, the function $\lp$ is a stage cost function penalizing both the distance of the state to the desired equilibrium and the used control. A popular choice for this function is $\lp(\xp, \up) = \| \xp \|_{\xpref} + \lambda \| \up \|_{\upref}$ with weighting parameter $\lambda > 0$.

Computing a control minimizing is, in general, computational intractable. To circumvent this issue the NMPC algorithm uses the truncated cost functional $$\begin{aligned}
    \label{Setup and Preliminaries:cost functional p}
    \JpNp(\xpzero, \up) = \sum\limits_{k = 0}^{\Np - 1} \lp(\xpu(k, \xpzero), \up(k))\end{aligned}$$ with finite horizon of length $\Np$ and initial value $\xpzero$. Hence, a finite minimizing control sequence $\ups \in \bUpNpad(n, \xpzero, \ip(n))$ is computed with $$\begin{aligned}
    \bUpNpad(n, \xpzero, \ip(n)) = \{ \up(\cdot) \in \UpNp \mid & \mbox{ for all $k = 0, \ldots, \Np$ we have $\up(k) \in \bUp$ and } \\
    & (\xpu(k, \xpzero), ( x_q^{n_q}(k + n - n_q) )_{\cIp(n, k)}) \in \bX_{\{p\} \cup \cIp(n, k)} \}.\end{aligned}$$ In the following we assume that a minimizing control sequence exists and denote the corresponding optimal value function by $$\begin{aligned}
    \VpNp(\xp(n), \ip(n)) = \min_{\up \in \bUpNpad(n, \xp(n), \ip(n))} \JpNp(\xp(n), \up)\end{aligned}$$ where the minimizing control sequence is given by $$\begin{aligned}
    \ups = \argmin_{\up \in \bUpNpad(n, \xp(n), \ip(n))} \JpNp(\xp(n), \up).\end{aligned}$$ Here, the $\argmin$ operator is used in the following sense: given a map $a:\U \to \R$, a nonempty subset $\widetilde{\U} \subseteq \U$ and a value $\us \in \widetilde{\U}$ we write $\us = \argmin_{u \in \widetilde{\U}} a(u)$ if and only if $a(\us) = \min_{u \in \widetilde{\U}} a(u)$ holds. Note that we do not require uniqueness of the minimizer $\us$. In case of uniqueness the $\argmin$ operator can be understood as an assignment, otherwise it is just a convenient way of writing “$\us$ minimizes $a(u)$”.

Having obtained a minimizing sequence $\ups(\cdot)$, only the first element $\ups(0)$ of the control sequence is implemented. Then the entire problem is shifted forward in time by one time instant and both a new initial value and neighbouring information need to be obtained. Applying this method iteratively results in a feedback law which assigns the first element of the minimizing control sequence $\ups(\cdot)$ to the current state of the $p$-th system $\xp(n)$ and the neighbouring information $\ip(n)$ of the corresponding agent, i.e. a map $$\begin{aligned}
    \label{Setup and Preliminaries:eq:feedback}
    \mupNp: (\xp(n), \ip(n)) \mapsto \ups(0).\end{aligned}$$ Accordingly, the closed loop solution of the $p$-th system is given by $$\begin{aligned}
    \label{Setup and Preliminaries:eq:closed loop solution p}
    \xp(n + 1) = f(\xp(n), \mupNp(\xp(n), \ip(n))) \quad \text{with} \quad \xp(0) = \xpzero.\end{aligned}$$

Using this setting, we first show conditions which guarantee asymptotic stability of the closed loop for local controllers.

Stability {#Section:Stability}
=========

While commonly endpoint constraints or a Lyapunov function type endpoint weight are used to ensure stability of the closed loop, see, e.g., the articles of @KG1988, @ChAl1998, @JH2005 and @Graichen2010, we consider the plain NMPC version without these modifications. In order to guarantee stability in this case, we use the “relaxed” version of the dynamic programming principle, cf. @LR2006. In particular, one can show asymptotic stability of in a trajectory based setting using a relaxed Lyapunov condition, see @GP2011 [Proposition 7.6]. Note that this stability result requires a centralized setting and the horizons to satisfy $N_p = N$ for all $p \in \cP$. Hence, for the overall system we denote the combined stage costs by $\l(x(n), u(n))$, the finite and infinite cost functional by $\JN(\xzero, u)$, $\Jinfty(\xzero, u)$ and the corresponding combined value functions by $\VN(x(n))$, $\Vinfty(x(n))$ which allows us to apply the stability result of @GP2011 [Proposition 7.6]:

\[Stability:proposition:online alpha aposteriori\] Consider a feedback law $\muN: \bX \rightarrow \bU$ and the closed loop trajectory $x(\cdot)$ of with control $u = \muN$ and initial values $x(0) \in \bX$ to be given. If the optimal value function $\VN:\bX \rightarrow \R_{\geq 0}$ satisfies $$\begin{aligned}
        \label{Stability:proposition:online alpha aposteriori:eq1}
        \VN(x(n)) \geq \VN(f(x(n), \muN(x(n))) + \alpha \l(x(n), \muN(x(n))) 
    \end{aligned}$$ for some $\alpha \in (0, 1]$ and all $n \in \N_0$, then $$\begin{aligned}
        \label{Stability:proposition:online alpha aposteriori:eq2}
        \alpha \Vinfty(x(n)) \leq \alpha \Jinfty(x(n), \muN) \leq \VN(x(n)) \leq \Vinfty(x(n)) 
    \end{aligned}$$ holds for all $n \in \N_0$.

If, in addition, there exist $\alpha_1,\alpha_2,\alpha_3 \in \cK_\infty$ such that $$\begin{aligned}
        \label{Stability:proposition:online alpha aposteriori:eq3}
        \alpha_1(\| x \|_{\xref}) \leq \VN(x) \leq \alpha_2(\| x \|_{\xref}) \quad \mbox{ and } \quad \l(x, u) \ge \alpha_3(\| x \|_{\xref})
    \end{aligned}$$ holds for all $x(n) \in \bX$ with $n \in \N_0$, then there exists a function $\beta \in \cKL$ which only depends on $\alpha_1, \alpha_2, \alpha_3$ and $\alpha$ such that the inequality $$\begin{aligned}
        \label{Stability:proposition:online alpha aposteriori:eq4}
        \| x(n) \|_{\xref} \leq \beta(\| x(0) \|_{\xref},n)
    \end{aligned}$$ holds for all $n \in \N_0$, i.e., $x$ behaves like a trajectory of an asymptotically stable system.

The key assumption in Proposition \[Stability:proposition:online alpha aposteriori\] is the relaxed Lyapunov–inequality in which $\alpha$ can be interpreted as a lower bound for the rate of convergence. From the literature, it is well–known that this condition is satisfied for sufficiently long horizons $N$, cf. @JH2005, @GMTT2005 or @AB1995, and that a suitable $N$ may be computed via methods described in @GP2011 [Chapter 7] or @G2010.

Now we consider a distributed setting of Proposition \[Stability:proposition:online alpha aposteriori\] using compositions to combine of the set of systems . The idea of such compositions is to introduce a weighting among the subsystems which in our further analysis will allow for increases of costs along the closed loop for some subsystems.

\[Stability:proposition:online alpha aposteriori distributed\] Consider feedback laws $\mupN: \bXp \times \bIp \rightarrow \bUp$ and closed loop trajectories $\xp(\cdot)$ of with initial values $\xp(0) \in \bXp$ to be given. If the optimal value functions $\VpN:\bXp \rightarrow \R_{\geq 0}$ satisfy $$\begin{aligned}
        \label{Stability:proposition:online alpha aposteriori distributed:eq1}
        \VpN(\xp(n)) \geq \VpN(\fp(\xp(n), \mupN(\xp(n), \ip(n)))) + \alpha \lp(\xp(n), \mupN(\xp(n), \ip(n))) 
    \end{aligned}$$ for some $\alpha \in (0, 1]$ and all $n \in \N_0$, then for any weighting function $\gamma: \R^P \to \R_{\geq 0}$, $\gamma(x)=\gamma^\top x$, $\gamma_i \in \R_{> 0}$ we have that holds for all $n \in \N_0$ with $$\begin{aligned}
        \VN(x) := \gamma( ( V_1^N(x_1), \ldots, V_P^N(x_p))^\top ) \quad \mbox{and} \quad \l(x, u) := \gamma( ( \l_1(x_1, u_1), \ldots, \l_P(x_P, u_P))^\top ).
    \end{aligned}$$

If, in addition, for every $p \in \cP$ there exist $\alpha_1^p,\alpha_2^p,\alpha_3^p \in \cK_\infty$ such that $$\begin{aligned}
        \label{Stability:proposition:online alpha aposteriori distributed:eq2}
        \alpha_1^p(\| \xp \|_{\xpref}) \leq \VpN(x) \leq \alpha_2^p(\| \xp \|_{\xpref}) \quad \mbox{ and } \quad \lp(\xp, \up) \ge \alpha_3^p(\| \xp \|_{\xpref})
    \end{aligned}$$ holds for all $\xp(n) \in \bX$ with $n \in \N_0$, then there exists a function $\beta \in \cKL$ which only depends on $\gamma$, $\alpha$ and all $\alpha_1^p, \alpha_2^p, \alpha_3^p$, $p \in \cP$, such that holds for all $n \in \N_0$.

Defining the abbreviations $V_\cP^N(x(n)) := ( V_1^N(x_1(n)), \ldots, V_P^N(x_P(n)))^\top$ and $\l_\cP(x(n), \muN(x(n), \i_\cP(n))) := ( \l_1(x_1(n), \mu_1^N(x_1(n), \i_1(n))), \ldots, \l_P(x_P(n), \mu_P^N(x_P(n), \i_P(n))) )^\top$ we combine all inequalities for $p \in \cP$ and obtain $$\begin{aligned}
        \label{Stability:proposition:online alpha aposteriori distributed:proof:eq1}
        \gamma( V_\cP^N(x(n)) ) \geq \gamma ( V_\cP^N(x(n + 1))) + \alpha \gamma ( \l_\cP(x(n), \muN(x(n), \i_\cP(n))) ) .
    \end{aligned}$$ using linearity of $\gamma$. Now we use the definition of $\VN$ and $\l$ which gives us . Hence, follows directly from Proposition \[Stability:proposition:online alpha aposteriori\]. Similarly, follows by definition of $\VN$ and $\l$ which together with $\alpha_i(r) := \gamma ( (\alpha_i^1(r), \ldots, \alpha_i^P(r))^\top )$, $i = 1, 2, 3$, and again Proposition \[Stability:proposition:online alpha aposteriori\] shows the assertion.

Certainly, condition would be desireable since it guarantees a decrease in $\VpN$ for each $p \in \cP$. In practice, however, one would usually expect $\VpN$ to decrease for some $p \in \cP$ while it increases for others as shown in the following example:

\[Stability:example\] Consider the setting of Example \[Setup and Preliminaries:example\] where we suppose that each agent $p = 1, 2$ is optimizing using its running costs $\lp(\xp, \up) = \| \xp - \xpref \|_2^2$ with $\xref_1 = ( -2, 0)^\top$ and $\xref_2 = (2, 0)^\top$ and complete neighbouring information for initial conditions $\xzero_{1} = (1, 0)^\top$, $\xzero_{2}=(-1, 0)^\top$.\
Due to the constraints – one car has to wait before entering the bridge, cf. Figure \[Setup and Preliminaries:fig:carexample2\], and even has to move aside as shown in Figure \[Stability:fig:carexampleoptimal1\]. Without loss of generality we assume that system $p = 2$ moves aside.

Although the optimal control for agent $p=2$ for any $N \geq 2$ is identical to the global optimal control, cf. Figures \[Stability:fig:carexampleoptimal2\] and \[Stability:fig:carexampleoptimal3\], we obtain $\VN_2(x_2(0), \i_2(0)) \leq \VN_2(x_2(1), \i_2(1))$ for $N = 2$ and $N = 3$. Hence, we cannot guarantee to hold for these $N$ although the closed loop is stable. For larger values of $N$, however, we obtain $$\begin{aligned}
        \VN_2(x_2(0), \i_2(0)) & = \begin{cases} 37 & \mbox{if } N = 4 \\ 41 & \mbox{if } N = 5 \\ 42 & \mbox{if } N \geq 6 \end{cases}
        &\quad \text{and} \quad 
        \l_2(x_2(0), \muN_2(x_2(0),\i_2(0))) & = 9, \displaybreak[0] \\
        \VN_2(x_2(1), \i_2(1)) & = \begin{cases} 32 & \mbox{if } N = 4 \\ 33 & \mbox{if } N \geq 5 \end{cases}
        &\quad \text{and} \quad 
        \l_2(x_2(1), \muN_2(x_2(1),\i_2(1))) & = 9,
    \end{aligned}$$ $$\begin{aligned}
        \left( \VN_2(x_2(n), \i_2(n)) \right)_{n=2,\ldots,5, N \geq 4} & = ( 24, 10, 5, 1 )\quad \text{and} \\
        \left( \l_2(x_2(n), \muN_2(x_2(n),\i_2(n))) \right)_{n=2,\ldots,5, N \geq 4} & = ( 10, 9, 4, 1 )
    \end{aligned}$$ and $\VN_2(x_2(n), \i_2(n)) = \l_2(x_2(n), \muN_2(x_2(n),\i_2(n))) = 0$ if $N \geq 4$ and $n \geq 6$. Accordingly, the largest values $\alpha$ such that holds are $\alpha = 5/9$ if $N = 4$, $\alpha = 8/9$ if $N = 5$ and $\alpha = 1$ if $N \geq 6$. Hence, we can use Proposition \[Stability:proposition:online alpha aposteriori distributed\] to conclude asymptotic stability if $N \geq 4$.

In an indeep analysis, @GW2010 [Theorem 5.3] have shown conditions such that for the serial case using the algorithm of Richards and How [@RH2004; @RH2007] inequalities and hold. Note that although the setting within the articles of @RH2004 [@RH2007] is for one based on linear dynamics and secondly explicitely includes perturbations in the models, this algorithm can also be used in a nonlinear setting, cf. @GW2010 [Proposition 3.2].

Taking a closer look at the proof of Proposition \[Stability:proposition:online alpha aposteriori distributed\] we see that in fact conditions are only required to guarantee to hold. Note that while condition requires a decrease in $\VpN$ for each $p \in \cP$, in it suffices that $\VpN$, $p \in \cP$ is decreasing under a map $\gamma$. Moreover, we only require $\gamma \in \cK_\infty^P$ in the remainder of the proof of Proposition \[Stability:proposition:online alpha aposteriori distributed\] to guarantee $\alpha_i \in \cK_\infty$, $i=1, 2, 3$. Accordingly, we obtain the following more general result:

\[Stability:proposition:online alpha aposteriori distributed2\] Consider feedback laws $\mupN: \bXp \times \bIp \rightarrow \bUp$ and closed loop trajectories $\xp(\cdot)$ of with initial values $\xp(0) \in \bXp$ to be given. If the optimal value functions $\VpN:\bXp \rightarrow \R_{\geq 0}$ satisfy for some $\alpha \in (0, 1]$, $\gamma \in \cK_\infty^P$ and all $n \in \N_0$, then holds for all $n \in \N_0$ with $\VN$ and $\l$ defined as in Proposition \[Stability:proposition:online alpha aposteriori distributed\].

If, in addition, for every $p \in \cP$ there exist $\alpha_1^p,\alpha_2^p,\alpha_3^p \in \cK_\infty$ such that holds for all $\xp(n) \in \bX$ with $n \in \N_0$, then there exists a function $\beta \in \cKL$ which only depends on $\gamma$, $\alpha$ and all $\alpha_1^p, \alpha_2^p, \alpha_3^p$, $p \in \cP$, such that holds for all $n \in \N_0$.

Follows directly from the proof of Proposition \[Stability:proposition:online alpha aposteriori distributed\].

The conclusion that can be drawn from Proposition \[Stability:proposition:online alpha aposteriori distributed2\] is that the weighting function $\gamma$ may allow us to partially violate condition . Since is typically fulfilled if the horizon $\Np$ is large enough, a good choice of $\gamma$ may reduce the horizon length $\Np$ as we will see in the following example:

\[Stability:example2\] Consider Example \[Stability:example\] and suppose $\gamma$ to be the 1–norm, then we obtain for $N = 2$ $$\begin{aligned}
        \left( \sum\limits_{p = 1}^2 \VpN(\xp(n), \ip(n)) \right)_{n=0, \ldots, 5} = ( 31, 24, 20, 13, 5, 1 ) \\
        \left( \sum\limits_{p = 1}^2 \lp(\xp(n), \mupN(\xp(n),\ip(n))) \right)_{n=0, \ldots, 5} = ( 18, 13, 11, 9, 4, 1 )
    \end{aligned}$$ and $\sum_{p = 1}^2 \VpN(\xp(n), \ip(n)) = \sum_{p = 1}^2 \lp(\xp(n), \mupN(\xp(n),\ip(n))) = 0$ for $n \geq 6$. Hence, holds with $\alpha = 4/13$ and we obtain asymptotic stability of the closed loop by Proposition \[Stability:proposition:online alpha aposteriori distributed2\]. Since $\alpha > 0$ holds for all $N \geq 2$ this example illustrates the advantage of considering condition instead of .

As outlined before Proposition \[Stability:proposition:online alpha aposteriori distributed2\], under certain conditions the algorithm of @RH2004 [@RH2007] can be applied to generate solutions such that and hold. However, the nature of this algorithm is serial, that is while one agent $p \in \cP$ is computing its control, all other agents $q \in \cP \setminus \{ p \}$ have to wait until agent $p$ finished computing. Hence, if the number of systems $P$ is large, such an algorithm may cause rather long waiting times, a feature which may be unwanted if fast sampling is used. Still, as noted in @RH2007 [Section 7], due to its decentralized nature the dimension of each problem is significantly smaller and hence the algorithm reduces the numerical effort compared to a centralized solution considerably.\
Apart from the serial nature, the algorithm of Richards and How requires accessibility to the full neighbouring information, i.e. a full communication graph. Additionally, an agent $p \in \cP$ always uses the latest available neighbouring information to compute a minimizing control $\ups$ which results in a full dependency graph. While the latter condition on the dependency graph may be relaxed easily, it is a complex task to obtain a parallel algorithm and to relax the requirement of a full communication graph.

The covering algorithm {#Section:The covering algorithm}
======================

In this section we provide a covering algorithm which is a modification of the Algorithm of @RH2004 [@RH2007] and allows us to run the agents $p \in \cP$ in parallel if they are independent from one another. Unfortunately, working in a parallel distributed setting omits the use of standard techniques from optimization such as first and second order information of the cost functional and the constraints for the interlink between systems to search for optimal controls.

To circumvent this deficiency we introduce abstract maps $\Pi, \Theta: 2^\cP \to 2^\cP$ which denote priority and deordering rules, see @H1989 and @Ba1998. The aim of this section is to show how much parallelism can be expected using the algorithm we propose next and the basic properties of $\Pi$, $\Theta$ being a permutation and a self concatenation mapping respectively.\
The structural layout of the algorithm we present now is closely related to the NMPC algorithm outlined in Section \[Section:Setup and Preliminaries\]:

\[The covering algorithm:alg:abstract\] Set lists $\cP_1: = ( 1, \ldots, P )$ and $\cP_p := \emptyset$ for $p = 2, \ldots, P$, $n := 0$ and $\ip(n) := \emptyset$ for $p = 1, \ldots, P$.

1.  Obtain new measurements $\xp(n)$ for $p \in \cP$.

2.  *(Decision memory and deordering rule)* For $i$ from $2$ to $P$ do

    1.  For $j$ from $1$ to $\sharp \cP_{i}$ do

        1.  Set $\cI_{p_j}(n) := \Theta(\cI_{p_j}(n)) \subsetneq \cI_{p_j}(n)$

        2.  If $\cI_{p_j}(n) = \emptyset$, then remove $p_j$ from $\cP_{i}$ and set $\cP_{1} := (\cP_{1}, p_j)$\
            Else: If $\tilde{m} = \min_{k \in \cP_{m}, p_k \in \cI_{p_j}(n)} m < i$ holds, then remove $p_j$ from $\cP_{i}$ and set $\cP_{\tilde{m}} := (\cP_{\tilde{m}}, p_j)$

3.  Compute a control $\ups(\cdot)$ minimizing or with $\xpzero = \xp(n)$ and send information to all agents $q \in \{ q \in \cP \mid q \in \cP_j, p \in \cP_i \mbox{ and } j \geq i \}$ for $p \in \cP$ in parallel

4.  *(Priority rule)* For $i$ from $1$ to $P$ do

    1.  If $\sharp \cP_{i} \in \{0, 1\}$, goto Step 3.\
        Else: Sort index list by setting $\cP_{i} := \Pi(\cP_{i})$

    2.  For $j$ from $2$ to $\sharp \cP_{i}$ do

        1.  If system $p_{j}$ violates constraints imposed by systems $p_{k}$, $k < j$, then set $\cP_{i+1} := (\cP_{i+1} , j )$ and $\cI_{j}(n) := \cI_{j}(n) \cup \{ p_{k} \in \cP_{i} \setminus \cP_{i+1} \mid \text{$p_{k}$, $k < j$, induces constraints violated by system $p_{j}$}\}$ and set $\cP_{i} := \cP_{i} \setminus \cP_{i+1}$

    3.  Compute a control $\ups(\cdot, \ip(n))$ minimizing or for all $p \in \cP_{i+1}$ in parallel and send information to all agents $q \in \{ q \in \cP \mid q \in \cP_j, j \geq i \}$

5.  Implement $\mupNp(\xp(n), \ip(n)) := \ups(0)$, set $n := n + 1$ and goto Step 1.

The general idea of the algorithm is to first generate priority lists $\cP_i$ of the systems according to the rule $\Pi$ and according to their interconnection with other systems, cf. Step 2c, – just as the right-before-left rule in street traffic or the search direction in optimization methods. Secondly, these lists are used to remember earlier decisions which avoids generating periodic behaviour. This part of the algorithm, contained in Step 2a, is inspired by Bland’s rule and the lexicographic ordering method used in the simplex algorithm to cope with degeneracy. Last, the deordering rule $\Theta$ which is used together with the memory in Step 2a offers a possibility to break up earlier decisions. Proceeding this way avoids blockages and reduces both the number of priority lists and thereby the numerical effort to compute the control sequences.

We like to mention that Algorithm \[The covering algorithm:alg:abstract\] can be extended to an iterative computation of the controls $\ups$, $p \in \cP$. To this end only a few steps within the optimization method used to solve the problems of Steps 2b and 2c(iii) are performed. Additionally a second loop containing Steps 2b and 2c is introduced which is terminated if some stopping criterion like the suboptimality based criterion given in @GP2010 is satisfied. Note that the algorithm also allows us to stop agents during such an iterative computation, i.e. if is satisfied for some $\alpha \geq \overline{\alpha} \in (0, 1)$. Since we allowed for using old and even outdated information in Definition \[Setup and Preliminaries:neighbouring information\], the algorithm even allows to block any computations of some agents for a certain period depending on the length of an agents prediction without compromising feasibility.

Given Algorithm \[The covering algorithm:alg:abstract\], we first consider the question whether a feasible feedback $\mupNp$ can be computed via Algorithm \[The covering algorithm:alg:abstract\]:

\[The covering algorithm:thm:feasibility\] Assume a feasible initial value $x_0 \in \bX$ for system to be given. Suppose that for all $p \in \cP$ and all $n \in \N_0$ we have that the sets of admissible controls $\bUpad(n, \xp(n), \ip(n))$ in case of cost functional or $\bUpNpad(n, \xp(n), \ip(n))$ in case of cost functional in Steps 2b and 2c(iii) are not empty, then the closed loop solutions satisfy $x(n) = ( x_1(n)^\top, \ldots, x_P(n)^\top )^\top \in \bX$.

Using $x_0 \in \bX$ and $\bUpad(0, \xp(0), \ip(0)) \not = \emptyset$ for all $p \in \cP$ in case of cost functional or $\bUpNpad(0, \xp(0), \ip(0)) \not = \emptyset$ for all $p \in \cP$ in case of cost functional , we obtain from Steps 2b and 2c(iii) that optimal controls $\ups(\cdot, \ip(0))$ exist for all $p \in \cP$. Hence, by definition of the closed loop in and Step 3 we obtain that $x(1) = ( x_1(1)^\top, \ldots, x_P(1)^\top )^\top \in \bX$ holds. Applying the same argumentation inductively for all $n \in \N_0$ the assertion follows.

Before showing results for Algorithm \[The covering algorithm:alg:abstract\] together with general priority and deordering rules $\Pi$, $\Theta$, we like to illustrate both rules using the example outlined in Section \[Section:Stability\]. The idea of the priority rule is straight forward. In fact, we have already used it in Example \[Stability:example\] to solve the blockage in the very first step:

Again consider Example \[Stability:example\]. Due to the constraint sets $\bX$, $\bU$ and the dynamics of the systems $\fp$, one of the agents $p$ has to move aside first to let the system of the other agent pass by before it can proceed towards its desired equilibrium. Putting priority of agent $p = 1$ into a mathematical form, we see that $\Pi$ can be implemented as a lexicographic ordering, that is a list $\cL$ is mapped to its minimal permutation with respect to the dictionary ordering $<^d$ induced by the total orderings $\{ <_1, \ldots, <_m \}$ where $m$ is the length of the list $\cL$ and $<_i$, $i = 1, \ldots m$ is the usual ordering $<$ of the natural numbers $\N$.

Apart from the lexicographic ordering, also other heuristics like the greedy heuristic might be used. It is not clear how the priority rule should be chosen in a nonlinear setting, and throughout this work we will not focus on this question but instead concentrate on general properties of Algorithm \[The covering algorithm:alg:abstract\].\
The idea of the deordering rule $\Theta$ is more involved as it may interfere with the idea of keeping track of earlier decisions. The purpose of this rule is to reduce the number of the priority lists since Step 2c of Algorithm \[The covering algorithm:alg:abstract\] is a serial call for all lists $\cP_i$. Accordingly, agents $p \in \cP_{i+1}$ always have to wait until all agents $p \in \cP_i$ have finished computing, a fact we wish to avoid. Note that this serial nature is independent from the parallel computation of control sequences $\ups$, $p \in \cP_i$. Using the deordering rule $\Theta$ allows us to “test” whether a system $p \in \cP_i$ still interferes with all systems $p \in \cP_k$, $k < i$, or if it can be inserted into a different priority list $\cP_k$, $k < i$, causing the number of lists and hence the number of non parallel steps to shrink. Yet even if system $p$ cannot be inserted in a different priority list, applying the deordering rule might still result in reducing the size of the neighbouring index set $\cIp(n)$. If this is the case, then the number of constraints of system $p$ is reduced which in turn reduces the numerical effort to compute the control sequence $\ups$.

Consider once more Example \[Stability:example\] with $\Theta(\cP) = \emptyset$. Applying Algorithm \[The covering algorithm:alg:abstract\] we obtain that $\us_2$ depends on the solution of system $p = 1$ for $n \in \{ 0, 1\}$ only whereas for all $n \geq 2$ both problems can be solved in parallel.

Turning towards the central point of this section, we now analyze how much parallelism is possible even if we do not know the exact sorting and testing operators $\Pi, \Theta$. Based on conditions on the priority lists $\cP_i$ our first result shows in which case all agents can compute their controls independently from each other:

\[The covering algorithm:lem:independence\] Suppose that for given systems , maps $\Pi, \Theta: 2^\cP \to 2^\cP$ and $n \in \N_0$ we have that $\cP_2 = \emptyset$ holds in Step 2c(i) of Algorithm \[The covering algorithm:alg:abstract\]. Then every agent $p \in \cP$ can compute its control sequence independently of all other agents $q \in \cP \setminus \{ p \}$.

Since $\cP_2 = \emptyset$ Step 2c(ii) of Algorithm \[The covering algorithm:alg:abstract\] guarantees that there are no systems $p_1, p_2 \in \cP_1$, $p_1 \not = p_2$, such that $p_1$ induces a constraint on $p_2$ which is violated by $p_2$, i.e. $\cIp(n) = \emptyset$ for all $p \in \cP$. Hence, for each agent $p \in \cP$ the set of admissible controls simplifies to $$\begin{aligned}
        \bUpad(n, \xpzero, \ip(n)) = \{ \up(\cdot) \in \Up^{\N_0} \mid & \mbox{ $\up(k) \in \bUp$ and $\xpu(k, \xpzero) \in \bXp$ for all $k \in \N_0$} \}
    \end{aligned}$$ if cost functional or $$\begin{aligned}
        \bUpNpad(n, \xpzero, \ip(n)) = \{ \up(\cdot) \in \Up^{\Np} \mid & \mbox{ $\up(k) \in \bUp$ and $\xpu(k, \xpzero) \in \bXp$} \\
        & \mbox{for all $k \in \{0, \ldots, \Np\}$} \}
    \end{aligned}$$ if cost functional is considered with $\xpzero = \xp(n)$ showing the assertion.

Using the self-concatenation property of the map $\Theta$, we can also show that under certain conditions the priority lists show dependency of agents:

\[The covering algorithm:lem:dependence\] Consider systems , $P \geq 2$ to be given. Suppose that applying Algorithm \[The covering algorithm:alg:abstract\] for given maps $\Pi, \Theta: 2^\cP \to 2^\cP$ we have that $\cP_i \not = \emptyset$ with $i \geq 2$ holds for some $n \geq \overline{n}$ and all $\overline{n} \in \N_0$. Then for each system $p \in \cP_i$ there exists at least one system $q \in \cP_j$, $j < i$ such that $q \in \cIp(n)$. Moreover, in case cost functional is used, we have $$\begin{aligned}
        \ups = \argmin_{\up \in \bUpad(n, \xp(n), \emptyset)} \Jpinfty(\xp(n), \up) \not \in \bUpad(n, \xp(n), \ip(n)) \subsetneq \bUpad(n, \xp(n), \emptyset)
    \end{aligned}$$ and in case of cost functional we have $$\begin{aligned}
        \ups = \argmin_{\up \in \bUpNpad(n, \xp(n), \emptyset)} \JpNp(\xp(n), \up) \not \in \bUpad(n, \xp(n), \ip(n)) \subsetneq \bUpNpad(n, \xp(n), \emptyset).
    \end{aligned}$$

Suppose that $\cP_i \not = \emptyset$ with $i \geq 2$ holds for some $n \geq \overline{n}$ and all $\overline{n} \in \N_0$ and fix $p \in \cP_i$ arbitrarily. Suppose furthermore that there exists no $q \in \cP_j$, $j < i$ such that $q \in \cIp(n)$ holds. Then, by the deordering rule $\Theta$ and Step 2a(i) we obtain that there exists $\overline{n} \in \N_0$ such that $\cP_i = \emptyset$ for all $n \geq \overline{n}$ contradicting our assumption. Hence, since $p \in \cP_i$ was chosen arbitrarily, we obtain that for each $p \in \cP_i$ there exists a system $q \in \cP_j$, $j < i$ such that $q \in \cIp(n)$ holds.\
Now, due to Step 2c(ii) and the fact that there exists a system $q \in \cIp(n)$ imposing constraints on system $p$ which are violated if $q \not \in \cIp(n)$ the assertion for both cost functionals and follows.

Now we can use Lemma \[The covering algorithm:lem:dependence\] to answer the question under which conditions asymptotic stability can be shown. In particular, we first prove a necessary condition for asymptotic stability of .

\[The covering algorithm:thm:no beta\] Consider systems , $P \geq 2$ to be given. Suppose that applying Algorithm \[The covering algorithm:alg:abstract\] for all maps $\Pi, \Theta: 2^\cP \to 2^\cP$ we have that $\cP_i \not = \emptyset$, $i \geq 2$ holds for some $n \geq \overline{n}$ and all $\overline{n} \in \N_0$ with $\cIp(n, 1) \not = \emptyset$ for some $p \in \cP_i$. Then there exists no function $\beta \in \cKL$ such that holds for all $n \in \N_0$.

Fix maps $\Pi, \Theta: 2^\cP \to 2^\cP$. Then Lemma \[The covering algorithm:lem:dependence\] states that for each system $p \in \cP_i$ there exists a system $q \in \cP_j$, $j < i$ such that $q \in \cIp(n)$. If for any $p \in \cP$ and any $n \in \N_0$ we have that $\bUpad(n, \xp(n), \ip(n)) = \emptyset$ or $\bUpNpad(n, \xp(n), \ip(n)) = \emptyset$ in case if cost functional or are used, respectively, we are done since no admissible solution exists. Otherwise, we obtain ${\ups}^1(\cdot) \not = {\ups}^2(\cdot)$ with $$\begin{aligned}
        {\ups}^1(\cdot) & = \argmin_{\up \in \bUpad(n, \xp(n), \ip(n))} \Jpinfty(\xp(n), \up), \quad {\ups}^2(\cdot) & = \argmin_{\up \in \bUpad(n, \xp(n), \emptyset)} \Jpinfty(\xp(n), \up)
    \end{aligned}$$ in case of cost functional and with $$\begin{aligned}
        {\ups}^1(\cdot) & = \argmin_{\up \in \bUpNpad(n, \xp(n), \ip(n))} \JpNp(\xp(n), \up), \quad {\ups}^2(\cdot) & = \argmin_{\up \in \bUpNpad(n, \xp(n), \emptyset)} \JpNp(\xp(n), \up)
    \end{aligned}$$ in case of cost functional .\
Hence, due to the fact that $\xp^{{\ups}^2}(k, x(n))$ for some $k$ violates a constraint imposed by system $q$ which is not violated by $\xp^{{\ups}^1}(k, x(n))$, we obtain that the open loop trajectories $\xp^{{\ups}^1}(\cdot, x(n))$ and $\xp^{{\ups}^2}(\cdot, x(n))$ differ. Using $\cIp(n, 1) \not = \emptyset$, we can conclude that there exists a $\delta_1 > 0$ such that $d_\X( \xp^{{\ups}^1}(1, \xp(n)), \xp^{{\ups}^2}(1, \xp(n)) ) > \delta_1$ holds. Since we always implement the first element of each optimal admissible control, we have that $d_\X ( \fp(\xp(n), {\ups}^1(0)), \fp(\xp(n), {\ups}^2(0)) ) > \delta_1$ holds. Now we have to consider two cases: If $\xp(n + 1) = \xpref$, then we can use the fact that the deviation $d_\X( \xp^{{\ups}^1}(1, \xp(\tilde{n})), \xp^{{\ups}^2}(1, \xp(\tilde{n})) ) > \delta_1$ will occur again for some $\tilde{n} > n$ due to the assumptions of the theorem. If $\xp(n + 1) \not = \xpref$, we immediately obtain the existence of a $\delta_2 > 0$ such that $\| \xp(n + 1) \|_{\xpref} > \delta_2$ holds. In either case, we obtain that there exists a time index $\tilde{n} > n$ such that $\| \xp(\tilde{n}) \|_{\xpref} > \delta = \min(\delta_1/2, \delta_2)$ holds.\
Now suppose there exists a function $\beta \in \cKL$ such that holds for all $n \in \N_0$. Due to the $\cL$-property $\beta$ in its second argument, we have that for each $\varepsilon > 0$ there exists a $\hat{n} \in \N_0$ such that $\| x(n) \|_{\xref} < \varepsilon$ for all $n \geq \hat{n}$. Now we choose $\varepsilon < \delta$ and $\hat{n} \in \N_0$ accordingly. Since Lemma \[The covering algorithm:lem:dependence\] holds for all $\overline{n} \in \N_0$, we can conclude that for $\tilde{n} > n \geq \overline{n} = \hat{n}$ the inequality $\| x(\tilde{n}) \|_{\xref} \geq \| \xp(\tilde{n}) \|_{\xpref} > \delta  > \varepsilon$ holds. This contradicts the existence of a function $\beta \in \cKL$ such that holds for all $n \in \N_0$.\
Last, since the maps $\Pi$ and $\Theta$ were chosen arbitrarily, the argumentation holds for all choices of $\Pi$ and $\Theta$ which completes the proof.

Condition $\cIp(n, 1) \not = \emptyset$ in Theorem \[The covering algorithm:thm:no beta\] is required since from $q \in \cIp(n)$ we can only conclude that $\xp^{{\ups}^1}(k_n, \xp(n))$ and $\xp^{{\ups}^2}(k_n, \xp(n))$ differ for some $k_n \geq 0$. According to the NMPC algorithm, only the first control element is implemented and we may face the situation that again $\xp^{{\ups}^1}(k_{n+1}, \xp(n + 1))$ and $\xp^{{\ups}^2}(k_{n+1}, \xp(n + 1))$ differ for some $k_{n+1} \geq k_n$. Now if $k_n > 0$ holds for all $n \in \N_0$, then system $p$ may be asymptotically stable.

Turning from necessary to sufficient conditions we like to stress that the converse of Theorem \[The covering algorithm:thm:no beta\] does not hold, not even in the special case that the conditions of Lemma \[The covering algorithm:lem:independence\] hold for all $n \geq \overline{n}$ with $\overline{n} \in \N_0$. This conclusion is due to the fact that even if $\cP_2 = \emptyset$ we can only guarantee that a control which minimizes for all systems $p \in \cP$ can be computed without having to consider any other system $q \in \cP \setminus \{ p \}$, but not whether all systems are actually stable.

\[The covering algorithm:thm:stability\] Suppose that for given maps $\Pi, \Theta: 2^\cP \to 2^\cP$ we have that for a given initial value $x_0 \in \bX$ the set of admissible controls $\bUpNpad(n, \xp(n), \ip(n))$ is not empty for all $p \in \cP$ and all $n \in \N_0$. Suppose furthermore that there exist $\alpha_1^p, \alpha_2^p, \alpha_3^p \in \cK_\infty$, $\gamma \in \cK_\infty$ and $\alpha > 0$ such that inequalities and hold for all $n \in \N_0$. Then there exists a function $\beta \in \cKL$ which only depends on $\alpha$, $\gamma$ and all $\alpha_1^p, \alpha_2^p, \alpha_3^p$, $p \in \cP$, such that holds for all $n \in \N_0$.

Moreover, there exists an $\overline{n} \in \N_0$ such that for each $n \geq \overline{n}$ we either have that $\cP_i \not = \emptyset$, $i \geq 2$ holds with $\cIp(n, 1) = \emptyset$ for all $p \in \cP_i$ or $\cP_2 = \emptyset$.

Using $x_0 \in \X$, $\bUpNpad(n, \xp(n), \ip(n)) \not = \empty$ for all $p \in \cP$ and all $n \in \N_0$ and Theorem \[The covering algorithm:thm:feasibility\] we obtain that the closed loop solution $x(n) = ( x_1(n)^\top, \ldots, x_P(n)^\top )^\top$ exists for all $n \in \N_0$ and satisfies $x(n) \in \bX$ for all $n \in \N_0$. Now, since inequalities and hold for all $n \in \N_0$, the existence of $\beta \in \cKL$ follows directly from Proposition \[Stability:proposition:online alpha aposteriori distributed2\]. To show the existence of $\overline{n} \in \N_0$ such that for $n \geq \overline{n}$ we either have that $\cP_2 = \emptyset$ or $\cP_i \not = \emptyset$, $i \geq 2$ holds with $\cIp(n, 1) = \emptyset$ for all $p \in \cP_i$, suppose that $\cP_i \not = \emptyset$, $i \geq 2$ holds for some $n \geq \overline{n}$ and all $\overline{n} \in \N_0$ with $\cIp(n, 1) \not = \emptyset$ for some $p \in \cP_i$. Then, using Theorem \[The covering algorithm:thm:no beta\] and the existence of $\beta \in \cKL$ we obtain a contradiction showing the assertion.

While the stability result of Theorem \[The covering algorithm:thm:stability\] is given for the NMPC case without stabilizing terminal constraints or terminal costs, the only critical component in the proof of this theorem is the condition that $\bUpNpad(n, \xp(n), \ip(n)) \not = \emptyset$ which guarantees that the closed loop solution $x(\cdot) = ( x_1(\cdot)^\top, \ldots, x_P(\cdot)^\top )^\top$ exists and satisfies the state constraints. Hence, if instead of the existence conditions of $\alpha_1^p, \alpha_2^p, \alpha_3^p \in \cK_\infty$ and $\alpha > 0$ such that inequalities and hold we impose other stability conditions – e.g., the terminal constraint condition given in @KG1988 or the terminal costs from @ChAl1998 – then the same proof can be used to guarantee asymptotic stability of the closed loop.

Conclusion {#Section:Conclusion}
==========

We presented a generalized stability result for NMPC controllers without stabilizing terminal constraints or terminal costs. Moreover, we described an algorithm which allows us to generate a hierarchy of such controllers in a distributed non cooperative setting. Using only abstract priority and testing maps, we have shown necessary as well as sufficient conditions for stability of the closed loop.

Future research concerning the algorithm will certainly deal with the question how the priority and testing maps should be chosen to minimize the number of priority lists or to maximize the number of controllers that can be run in parallel. From the stability side an indeep analysis is required to apriori guarantee condition . The availability of such a condition would then allow us to apriori guarantee Algorithm \[The covering algorithm:alg:abstract\] to asymptotically stabilize the system. One idea in this direction is outlined in @GW2010 [Section 7] and suggests the use of ISS small gain theorems to treat this problem.

[20]{} natexlab\#1[\#1]{}url \#1[`#1`]{}urlprefix

Alamir, M., Bornard, G., 1995. Stability of a truncated infinite constrained receding horizon scheme: the general discrete nonlinear case. Automatica 31 (9), 1353–1356.

Bäckström, C., 1998. Computational aspects of reordering plans. Journal of Artificial Intelligence Research 9, 99–137.

Chen, H., Allgöwer, F., 1999. Nonlinear model predictive control schemes with guaranteed stability. In: Nonlinear Model Based Process Control. Kluwer Academic Publishers, Dodrecht, pp. 465–494.

Dold, J., Stursberg, O., 2009. [Distributed Predictive Control of Communicating and Platooning Vehicles]{}. In: [Proceedings of the 48th IEEE Conference on Decision and Control held jointly with the 28th Chinese Control Conference CDC/CCC 2009]{}. pp. 561 –566.

Giselsson, P., 2010. [Adaptive Nonlinear Model Predictive Control with Suboptimality and Stability Guarantees]{}. In: [Proceedings of the 49th Conference on Decision and Control]{}. Atlanta, GA, pp. 3644–3649.

Giselsson, P., Rantzer, A., 2010. [Distributed Model Predictive Control with Suboptimality and Stability Guarantees]{}. In: [Proceedings of the 49th Conference on Decision and Control]{}. Atlanta, GA, USA.

Graichen, K., Kugi, A., nov. 2010. Stability and incremental improvement of suboptimal mpc without terminal constraints. Automatic Control, IEEE Transactions on 55 (11), 2576 –2580.

Grimm, G., Messina, M., Tuna, S., Teel, A., 2005. Model predictive control: for want of a local control [L]{}yapunov function, all is not lost. IEEE Trans. Automat. Control 50 (5), 546–558.

Grüne, L., Pannek, J., 2010. Analysis of unconstrained [N]{}[M]{}[P]{}[C]{} schemes with incomplete optimization. In: Proceedings of the 8th IFAC Symposium on Nonlinear Control Systems – NOLCOS 2010. Bologna, Italy, pp. 238–243.

Grüne, L., Pannek, J., 2011. Nonlinear Model Predictive Control: Theory and Algorithms, 1st Edition. Communications and Control Engineering. Springer.

Grüne, L., Pannek, J., Seehafer, M., Worthmann, K., 2010. Analysis of unconstrained nonlinear [M]{}[P]{}[C]{} schemes with varying control horizon. SIAM J. Control Optim. 48 (8), 4938–4962.

Grüne, L., Worthmann, K., 2011. [A distributed NMPC scheme without stabilizing terminal constraints]{}. In: Johansson, R., Rantzer, A. (Eds.), Distributed Decision Making and Control. Springer, 259–285.

Haupt, R., 1989. A survey of priority rule-based scheduling. Vol. 11. Springer Berlin / Heidelberg.

Jadbabaie, A., Hauser, J., 2005. On the stability of receding horizon control with a general terminal cost. IEEE Trans. Automat. Control 50 (5), 674–678.

Keerthi, S., Gilbert, E., 1988. Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: stability and moving-horizon approximations. J. Optim. Theory Appl. 57 (2), 265–293.

Lincoln, B., Rantzer, A., 2006. Relaxing dynamic programming. IEEE Trans. Automat. Control 51 (8), 1249–1260.

Rawlings, J. B., Mayne, D. Q., 2009. Model Predictive Control: Theory and Design. Nob Hill Publishing, Madison.

Richards, A., How, J., 2004. [A decentralized algorithm for robust constrained model predictive control]{}. In: Proceedings of the American Control Conference 2004. Boston, Massachusetts, pp. 4261–4266.

Richards, A., How, J., 2007. [Robust distributed model predictive control]{}. International Journal of Control 80 (9), 1517–1531.

Scattolini, R., 2009. [Architectures for distributed and hierarchical Model Predictive Control - A review]{}. Journal of Process Control 19 (5), 723–731.