# A Shortest-Path Lyapunov Approach for Forward Decision Processes

Authors: Julio B. Clempner
Journal: International Journal of Computer Games Technology
 (2009)

---

## Abstract

In previous work, attention was restricted to tracking the net using a backward method that knows the target point beforehand (Bellmans's equation), this work tracks the state-space in a forward direction,
and a natural form of termination is ensured by an equilibrium pointp∗(M(p∗)=S<∞andp∗•=∅). We consider dynamical systems governed by ordinary difference equations described by Petri nets. The
trajectory over the net is calculated forward using a discrete Lyapunov-like function, considered as a distance function. Because a Lyapunov-like function is a solution to a difference equation, it is constructed to respect
the constraints imposed by the system (a Euclidean metric does not consider these factors). As a result, we prove natural generalizations of the standard outcomes for the deterministic shortest-path problem and
shortest-path game theory.


---

## Body

## 1. Introduction

The shortest-path problem (see [1–3]) plays a fundamental role
in Petri nets theory, since it can be used to model processes. The analysis of
these models can show useful information about the process. For example,
deadlocks, equilibrium points, and so forth can be identified by computational
analysis.While it is possible to analyze such processes using
the existing classical theory through the Bellman's equation with the cost
criterion ([4–15]), much of this theory has few disadvantages.
Bellman's equation is expressed as a sum over the state of a trajectory needs
to be solved backwards in time from the equilibrium point (target point). It
results in an optimal function when it is governed
by Bellman's principle, producing the shortest path needed to reach a known
equilibrium point. Notice that the necessity to know the equilibrium point
beforehand when applying the equation is a significant constrain, given that,
in many practical situations, the state space of a Petri net is too large for
an easy identification of the equilibrium point.Moreover, algorithms using Bellman's equation usually
solve the problem in two phases [16]: preprocessing and search. In the preprocessing
phase, the distance is usually calculated between each state and the
equilibrium points (final states) of the problem, in a backward direction.
Then, in the search phase, these results are employed to calculate the distance
between each state and the equilibrium points, leading the search process to a
forward search.Tracking the state space in a forward direction allows
the decision maker to avoid invalid states that occur in the space generated by
a backward search. In most cases, the forward search gives the impression to be
more useful than the backward search. The explanation is that in the backward
direction, when the case of incomplete final states arises, invalid states
appear causing problems.Shortest-path problem [17, 18] can be classified by two
key categories [19]:
(a) the single-source shortest-path problem where the goal is to find the
shortest path from a given node to a target node (e.g., the algorithms of Dijkstra
and Bellman-Ford); and (b) the all-pairs shortest-path problem is a similar
problem in which the objective is to determine the shortest path between every
pair of nodes in the net (e.g., the algorithms of Floyd-Warshall and Johnson).We are concerned about the first case. However, we
consider dynamical systems governed by difference equations described by Petri
nets. The trajectory over the net is calculated using a discrete Lyapunov-like
function. A Lyapunov-like function is considered as a distance function
denoting the length from the source place to the equilibrium point. This work
is concerned with the analysis of the decision process where a natural form of
termination is ensured by an equilibrium point.Lyapunov-like functions can be used as forward
trajectory-tracking functions. Each applied optimal action produces a monotonic
progress towards an equilibrium point. Because it is a solution to the
difference equation, naturally it will lead the
system from the source place to the equilibrium point.It is important to note that there exist areas of
research using Petri nets as modeling tool where the use of a Lyapunov-like
function is inherent. For instance, the “Entropy” function is a
specific Lyapunov-like function used in Information Theory as a measure of the
information disorder. The “free Gibbs energy function” is a
Lyapunov-like function used in molecular biology for calculating the energy
change in a metabolic network.This paper introduces a modeling paradigm for shortest-path
decision process representation in Petri nets theory. The main point of this
paper is its ability to represent the characteristics related only with the
global system behavior, and those characteristics related with the
trajectory-tracking behavior.Within the global system behavior properties, we show
notions of stability. In this sense, we call equilibrium point to the place in
a Petri net that its marking is bounded and it is the last place in the net
(sink).In the trajectory-tracking behavior properties
framework, we define the trajectory function as a Lyapunov-like function. By an
appropriate selection of the Lyapunov-like function, it is possible to optimize
the trajectory. By optimizing the trajectory, we understand that it is the
minimum trajectory-tracking value (in a certain sense). In addition, we use the
notions of stability in the sense of Lyapunov to characterize the stability
properties of the Petri net. The core idea of our approach uses a nonnegative
trajectory function that converges in decreasing form to a (set of) final
decision states. It is important to point out that the value of the trajectory
function associated with the Petri net implicitly determines a set of policies,
not just a single policy (in case of having several decisions states that could
be reached). We call “optimum point” the best choice selected from a
number of possible final decision places that may be reached (to select the
optimum point, the decision process chooses the strategy that optimizes the trajectory-tracking
value).As a result, we show that the global system behavior
properties and the trajectory-tracking behavior properties of equilibrium,
stability, and optimum-point conditions meet under certain restrictions: if the
Petri net is finite, then we have that a final decision place is an equilibrium
point.The paper is structured in the following manner. The
next section discusses the motivation of the work. Section3 presents the
formulation of the decision model, and all the structural assumptions are introduced
there, giving a detailed analysis of the equilibrium, stability, and
optimum-point conditions for the global system behavior properties and the
trajectory tracking behavior parts of the Petri net. Section 4 presents the
properties of the model. Finally, in Section 5 some concluding remarks are
outlined.


## 2. Motivation

In this paper, we consider dynamical systems in which
the time variable changes discretely, and the system is governed by ordinary
difference equations. Let us consider systems of first-order difference
equations given by(1)sn+1=f(sn,an),sn0=s0,n∈ℕ+n0, where si with i∈ℕ are the state variable of the system, s0 is the initial state, ai and i∈ℕ are the action of the system, ℕ+n0={n0,n0+1,…,n0+k,…},n0≥0.
The system is specified by the state transition function f,
which is always assumed as a one-to-one function for any fixed a and n∈ℕ,
continuous in all its arguments.Lyapunov defined a scalar functionL,
called a Lyapunov-like function, inspired by a classical energy function, which
has four important properties that are sufficient for establishing the domain
of attraction of a stable equilibrium point: (a) ∃s∗ such that L(s∗)=0;
(b) L(s)>0 for all s≠s∗;
(c) L(s)→∞ when s→∞;
and (d) ΔL=L(si+1)−L(si)<0 for all i,si≠s∗.
The condition (a) requires the equilibrium point to have zero potential by
means of a translation to the origin, (b) means that the Lyapunov-like function
to be semipositive defined, (c) means that there is no s∗ reachable from some s,
and (d) means that the Lyapunov-like function has a minimum at the equilibrium
point.The main idea of Lyapunov is attained in the following
interpretation: given an isolated physical system, if the change of the energyE for every possible state s is negative, with the exception of the
equilibrium point s∗,
then the energy will decrease until it finally reaches the minimum at s∗.
Intuitively, this concept of stability means that a system perturbed from its
equilibrium point will always return to it.A system is stable [20, 21] if for a given set of initial states the state of the
system ensures (i) to reach a given set of states and stay there perpetually or,
(ii) to go to a given set of states infinitely often. The conventional notions
of stability in the sense of Lyapunov and asymptotic stability can be used to
characterize the stability properties of discrete event systems. An important
advantage of the Lyapunov approach is that it does not require
high-computational complexity but the difficulty lies in specifying the
Lyapunov-like function for a given problem.At this point, it is important to note that the
Lyapunov-like functionL is not unique, however the energy function of
a system is only one of its kind. A system whose energy E decreases on the average, but not necessarily
at each instance, is stable but E is not a Lyapunov-like function.Lyapunov-like functions [22] can be used as
trajectory-tracking functions and optimal cost-to-target functions. As a result
of calculating a Lyapunov-like function, a discrete vector field can be built for
tracking the actions over the net. Each applied optimal action produces a
monotonic progress (of the optimal cost-to-target value) toward an equilibrium
point. In this sense, if the function decreases with each action taken, then it
approaches an infimum/minimum (that converges
asymptotically or reaches a constant).From what we have stated before, we can deduce the
following geometric interpretation of distance [22]: (a) L(s) is a measure of the distance from the starting
state s0 to any state s in the state space (this is straightforward
from the fact that ∃s∗ such that L(s∗)=0 and L(s)>0 for all s≠s∗); and (b) the distance from the stating state s0 to any state sn in the state space decreases, when n→∞.
It is because L(si+1)−L(si)<0 for all i,si≠s∗.A Lyapunov-like function can be considered as a
distance function denoting the length from the initial state to the equilibrium
point. It is important to note that the Lyapunov-like function is constructed
to respect the constraints imposed by the difference equation of the system. In
contrast, a Euclidean metric does not take into account these factors. For that
reason, the Lyapunov-like function offers a better understanding of the concept
of the distance required to converge to an equilibrium point in a discrete dynamical
system.By applying the computed actions, a kind of discrete
vector field can be imagined over the search graph. Each applied optimal action
yields a reduction in the optimal cost-to-target value, until the equilibrium
point is reached. Then, the cost-to-target values can be considered as a
discrete Lyapunov function.In our case, an optimal discrete problem, the
cost-to-target values are calculated using a discrete Lyapunov-like function.
Every time a discrete vector field of possible actions is calculated over the
decision process. Each applied optimal action (selected via some “criteria”)
decreases the optimal value, ensuring that the optimal course of action is
followed and establishing a preference relation. In this sense, the criteria
change the asymptotic behavior of the Lyapunov-like function by an optimal
trajectory-tracking value.Usually, the criterion in optimization problems is
related with the choice of whether to minimize or maximize the optimal action.
If the problem is related with energy transformations, as is classically the
case in control theory, then the criterion of minimization is applied. However,
if the dilemma involves a reward, typical in game theory, then maximization is
considered. In this work, we will arbitrary consider the criterion of
minimization.The Lyapunov-like function can be employed as a
trajectory-tracking function through the use of an operator, which represents
the criterion that selects the optimal action that forces the function to
decrease and approaches an infimum/minimum. It forces the function to make a
monotonic progress toward the equilibrium point. The Lyapunov-like function can
be defined, for example, as(2)L∗(sn+1)=mina∗∈AL(f(sn,an∗)) which means
that the optimal action is chosen to reach the infimum/minimum. The function L∗ works as a guide leading the system optimally
from its initial state to the equilibrium point.Example 1.
To illustrate the shortest-path
problem, let us consider a grid world (see Figure1). At each time step, an
agent is able to select an action among a finite set A of actions, for example, A={Up,Down,Left,Right}.
A transition model specifies how the world changes when an action is executed.
An “equilibrium point” s∗ is a natural final state of the system.
Therefore, the shortest-path problem is a search through the state space for an
optimal path to the equilibrium point s∗,
using a deterministic transition model. The value of a state s is a number V(s) that intuitively speaking expresses the
desirability of state s.
For instance, let us consider the state-value function V being equal to the min function [23] as a specific Lyapunov-like function able to lead an
agent to an equilibrium point in a grid world.Example 2.
The relative entropy or
Kullback-Leibler [24, 25] distance between
two probability distributions qij|k1 and qij|k2 is defined as(3)𝒱(q1,q2)=∑i=1N∑j=1Nqij|k1logqij|k1qij|k2.In the above definition, we use
the convention (based on continuity arguments) that 0log(0/qij|k2)=0 and qij|k1log(qij|k1/0)=∞.
The relative entropy is always nonnegative and is zero if and only if qij|k1=qij|k2. 𝒱(q1,q2) is a distance-like function between
distributions since it is not symmetric and does not satisfy the triangle
inequality.Figure 1
An illustrative example of
finding the shortest path in a grid world.Example 3.
Glycolysis pathway (see Figure2)
is well known and described [11, 26, 27]. It is a ten-step catabolic pathway that makes use of
eleven different enzymes. The outcome are the conversion of glucose in two
molecules of pyruvate with concurrent net production of 2 ATPs. Glycolysis
process can be divided in two stages: (1) the conversion of glucose to
glyceraldehyde 3-phosphate with a required input of 2 ATPs, (2) the conversion
of glyceraldehyde 3-phosphate to pyruvate with a net output of 4 ATPs.
Glycolysis can be informally explained  from an energetic perspective as follows. The
initial amount of glucose may be represented as a ball at the top of an
irregular hill. Every time the ball bounces, the hill represents a reaction
state in the breakdown of the sugar process. Each bounce of the ball
corresponds to a change in free energy level. This energy change is modeled by
the Gibbs energy function which is a Lyapunov-like function. It is important to
note that bounces are irregular (reaching lower and higher energy levels) and
determined by the environment conditions. The final state (pyruvate) is
represented by the bottom of the hill where the ball reaches a steady state
(not bounces).
Let us explain the Petri net dynamics of the system
model as follows. Continuing with the ball and hill explanation, let us suppose
that the ball, representing the product pyruvate, is at the bottom of the hill.
And let us suppose that there is no net force able to move the ball either up
or down the hill. That means that the reactions (forward and backward) are
evenly balanced. Therefore, the substances and products are in equilibrium, and
no net dynamics will take place. That is, “the metabolic network system
is in equilibrium.”Figure 2
Glycolysis and pentose-phosphate pathways model.


## 3. Formulation

We introduce the concept of decision process Petri
nets (DPPNs) by locally randomizing the possible choices, for each individual
place of the Petri net [23, 28].
Definition 1.
A decision process Petri net is
a 7-tupleDDPN={P,Q,F,W,M0,π,U},
where
(i)
P={p0,p1,p2,…,pm} is a finite set of places,(ii)
Q={q1,q2,…,qn} is a finite set of transitions,(iii)
F⊆I∪O is a flow relation, where I⊆(P×Q) and O⊆(Q×P) such that P∩Q=∅ and P∪Q≠∅,(iv)
W:  F→ℕ+1 is a weight function,(v)
M0: P→ℕ is the initial marking,(vi)
π: I→ℝ+ is a routing policy representing the
probability of choosing a particular transition, such that for  each p∈P,∑qj:(p,qj)∈Iπ((p,qj))=1,(vii)
U: P→ℝ+ is a trajectory-tracking function.We adopt the standard rules about representing nets as
directed graphs, namely, places are represented as circles, transitions as
rectangles, the flow relation by arcs, and markings are shown by placing tokens
within circles [29].
As usual, we will denote z•={y|(z,y)∈F} and •z={y|(y,z)∈F}, for all z∈I∪O. A source place is a place p0∈P such that •p0=∅ (there are no incoming arcs into place p0). A sink place is a place pf∈P such pf•=∅ (there are no outgoing arcs from pf). A net system is a pair Σ=(N,M0) comprising a finite net N=(P,Q,F) and an initial marking M0.
A transition q∈Q is enabled at a marking M, denoted by M[q〉, if for every p∈•q,
we have that M(p)≥1.
Such a transition can be executed, leading to a marking M′ defined by M′=M−•q+q•.
We denote this by M[q〉M′ or M[〉M′.
The set of reachable markings of Σ is the smallest (with respect to set
inclusion) set [M0〉 containing M0 and such that if M∈[M0〉 and M[〉M′,
then M′∈[M0〉.The previous behavior of theDPPN is described
as follows. When a token reach a place, it is reserved for the firing of a
given transition according to the routing policy determined by U.
A transition q must fire as soon as all the places p1∈P contain enough tokens reserved for transition q.
Once the transition fires, it consumes the corresponding tokens and immediately
produces an amount of tokens in each subsequent place p2∈P.
When π(ι)=0 for ι∈I means that there are no outgoing arcs in the
place-transitions Petri net (i.e., p∈ι is a sink).In Figure2, we have represented partial routing
policies π that generate a transition from state p1 to state p2,
where p1,p2∈P as follows.Case 1.
The probability thatq1 generates a transition from state p1 to p2 is 1/3. But, because q1 transition to state p2 has two arcs, the probability to generate a
transition from state p1 to p2 is increased to 2/3.Case 2.
We set by convention for the
probability thatq1 generates a transition from state p1 to p2 is 1/3 (1/6 plus 1/6). However, because q1 transition to state p2 has only one arc, the probability to generate
a transition from state p1 to p2 is decreased to 1/6.Case 3.
Finally, we have the trivial case when
there exists only one arc fromp1 to q1 and from q1 to p2.It is important to note that, by definition, the
trajectory-tracking functionU is employed only for establishing a trajectory
tracking, working in a different execution level of that of the
place-transitions Petri net. The trajectory-tracking function U in no way change the place-transitions Petri
net evolution or performance.Uk(⋅) denotes the trajectory-tracking value at place pi∈P at time k and let Uk=[Uk(⋅),…,Uk(⋅)]T denote the trajectory-tracking state of DDPN at time k.FN:F→ℝ+ is the number of arcs from place p to transition q (the number of arcs from transition q to place p).Consider an arbitrarypi∈P and for each fixed transition qj∈Q that forms an output arc (qj,pi)∈O,
we look at all theprevious places ph of the place pi denoted by the list (set) •pηij={ph:h∈ηij},
where ηij={h:(ph,qj)∈I,(qj,pi)∈O},
that materializes all the input arcs (ph,qj)∈I and forms the sum(4)∑h∈ηijΨ(ph,qj,pi)Uk(ph), where Ψ(ph,qj,pi)=π(ph,qj)∗(FN(qj,pi)/FN(ph,qj)) and the index sequence j is the set κ={j:qj∈(ph,qj)∩(qj,pi) & ph running over the set •pηij}.
Remark 1.
•pηij denote the previous places to pi for a fixed transition qj∈Q.Continuing with all theqj's, we form the vector indexed by the sequence j identified by (j0,j1,…,jf) as follows:(5)[∑h∈ηij0Ψ(ph,qj0,pi)Uk(ph),∑h∈ηij1Ψ(ph,qj1,pi)Uk(ph),…,∑h∈ηijfΨ(ph,qjf,pi)Uk(ph)].Intuitively,
vector (5) represents all the possible trajectories through the transitions qjs to a place pi for a fixed i,
where j is represented by the sequence (j1,j2,…,jf) and f=#(κ).Then, formally we define the trajectory-tracking
functionU as follows.
Definition 2.
The
trajectory-tracking functionU with respect a decision process Petri net DDPN={P,Q,F,W,M0,π,U} is represented by the
following equation(6)Ukqj(pi)={Uk(p0)ifi=0,k=0,L(α)ifi>0,k=0,i≥0,k>0,where(7)α=[∑h∈ηij0Ψ(ph,qj0,pi)Ukqj0(ph),∑h∈ηij1Ψ(ph,qj1,pi)Ukqj1(ph),…,∑h∈ηijfΨ(ph,qjf,pi)Ukqjf(ph)],the function L:D⊆ℝ+n→ℝ+ is a Lyapunov-like function which optimizes
the trajectory-tracking value through all possible transitions (i.e., through
all the possible trajectories defined by the different qjs),D is the decision set formed by the j's; 0≤j≤f,
of all those possible transitions (qjpi)∈O, Ψ(ph,qj,pi)=π(ph,qj)∗(FN(qj,pi)/FN(ph,qj)),ηij is the index sequence of the list of previous
places to pi through transition qj,ph(h∈ηij) is a specific previous place of pi through transition qj.Example 4.
OR-Path (see Figure3). Define the Lyapunov-like function L in terms of the Entropy H(pi)=−pilnpi as L=mini=1,…,|α|(−αilnαi):
(i)
Uk=0(p0)=0.2,(ii)
Uk=0qa(p1)=L[Ψ(p0,qa,p1)Uk=0qa(p0)]=minH[1∗0.2]=H[0.2]=0.321,(iii)
Uk=0qb(p2)=L[Ψ(p1,qb,p2)Uk=0qb(p1),Ψ(p1,qc,p2)Uk=0qb(p1)]=minH[1/3∗0.321,2/3∗0.321]=min[0.239,0.329]=0.239.Figure 3
(Left): routing policy case 1. (Right): routing policy case 2.Example 5.
AND-Path  (see Figure4). Define
the Lyapunov-like function L in terms of the Entropy H(pi)=−pilnpi as L=mini=1,…,|α|(−αilnαi):
(i)
Uk=0(p0)=0.2,(ii)
Uk=0qa(p1)=L[Ψ(p0,qa,p1)Uk=0qa(p0)]=minH[1∗0.2]=H[0.2]=0.321,(iii)
Uk=0qb(p2)=L[Ψ(p0,qb,p2)Uk=0qb(p0)]=minH[1∗0.2]=H[0.2]=0.321,(iv)
Uk=0qc(p3)=L[Ψ(p1,qc,p3)Uk=0qc(p1)+Ψ(p2,qc,p3)Uk=0qc(p2)]=minH[1∗0.321+1∗0.321]=H[0.642]=0.284.Figure 4
OR-Path Example.Figure 5
AND-path example.From the previous definition, we have the following
remark.Remark 2.
(i) Note that the Lyapunov-like functionL guarantees that the optimal course of action
is followed (taking into account all the possible paths defined). In addition,
the function  L establishes a preference relation because, by
definition, L is asymptotic; this condition gives to the
decision maker the opportunity to select a path that optimizes the
trajectory-tracking value.
(ii) The iteration overk for U is as follows:
(1)
fori=0 and k=0 the trajectory-tracking value is U0(p0) at place p0 and for the rest of the places pi the trajectory-tracking value is 0;(2)
fori≥0 and k>0 the trajectory-tracking value is Ukqj(pi) at each place pi,
and is computed by taking into account the
trajectory-tracking value of the previous places ph for k and k−1 (when needed).Property 1.
The continues
functionU(⋅) satisfies the following properties:
(1)
∃pΔ∈P such that
(a)
if
there exists an infinite sequence{pi}i=1∞∈P with pn→n→∞pΔ such that 0≤⋯<U(pn)<U(pn−1)⋯<U(p1),
then U(pΔ) is the infimum, that is, U(pΔ)=0;(b)
if
there exists a finite sequencep1,…,pn∈P with p1,…,pn→pΔ such that C=U(pn)<U(pn−1)⋯<U(p1),
then U(pΔ) is the min imum, that is, U(pΔ)=C,
where C∈ℝ, (pΔ=pn);(2)
U(p)>0 or U(p)>C,
where C∈ℝ,  for all p∈P such that p≠pΔ;(3)
for allpi,pi−1∈P such that pi−1≤Upi then ΔU=U(pi)−U(pi−1)<0.From the previous property, we have the following
remark.Remark 3.
In property 1 point 3, we state thatΔU=U(pi)−U(pi−1)<0 for determining the asymptotic condition of
the Lyapunov-like function. However, it is easy to show that such property is
convenient for deterministic systems. In Markov decision process, systems
are necessary to include probabilistic decreasing
asymptotic conditions to guarantee the asymptotic condition of the
Lyapunov-like function.Property 2.
The
trajectory-tracking functionU:P→ℝ+ is a Lyapunov-like function.Proof.
Proof comes straightforward from the previous
definitions.Remark 4.
From Properties1 and 2, we have the following:
(i)
U(pΔ)=0 or U(pΔ)=C means that a final state is reached. Without
lost generality, we can say that U(pΔ)=0 by means of a translation to the origin.(ii)
In Property1, we determine that the
Lyapunov-like function U(p) approaches to a infimum/minimum when p is large thanks to property (d) of the
definition the Lyapunov-like function (see motivation).(iii)
Property1, point 3 is equivalent to the
following statement: ∃{εi},εi>0 such that |U(pi)−U(pi−1)|>εi,
for all pi,pi−1∈P such that pi−1≤Upi.


### Explanation.

Intuitively, a Lyapunov-like function can be considered as trajectory-tracking
function and optimal cost function. In our case, an optimal discrete problem,
the cost-to-target values are calculated using a discrete Lyapunov-like
function. Every time a discrete vector field of possible transitions is
calculated over the decision process. Each applied optimal transition (selected
via some “criterion,” e.g.,min(⋅)) decreases the optimal value, ensuring that
the optimal course of action is followed and establishing a preference
relation. In this sense, the criterion changes the asymptotic behavior of the
Lyapunov-like function by an optimal trajectory-tracking value. It is important
to note that the process finished when the equilibrium point is reached. This
point determines a significant difference with Bellman's equation.Example 6 (Conc-Path (see Figure2)).
Biochemical pathway of the free energy profile of the
glycolysis and pentose-phosphate. The following was adapted from Biochemistry
Lehninger et al. [26] and
Campbell and Farrel [30]. The free
energy changes were calculated using the steady-state metabolite concentrations
in RBC's and the equation U=RTln([Products]/[Reactants]). U=0 was set arbitrarily at the end of the pathway
after the pyruvate kinase step. The overall reaction for the pathway is shown
in Figure 1. Because L:D⊆ℝn→ℝ+,
we will use the function mini=1,…,|α|(αi∈D) to select the proper element of the vector α∈D:
(i)
Uk=0(Glucose)=17.17 kcal/mol;(ii)
Uk=0qa(G6P)=L[Ψ(Glucose,qa,G6P)∗Uk=0qa(Glucose)]=G[Ψ(p0,qa,p1)Uk=0qa(p0)]=9.17 kcal/mol.
A decision is taken andqb is selected instead of qk based in the environment condition modeled via
the routing policy (1/3, 2/3).
(i)
Uk=0qb(F6P)=L[Ψ(G6P,qb,F6P)∗Uk=0qb(G6P)]=G[2/3∗Uk=0qb(p1)]=8.98 kcal/mol.(ii)
Uk=0qc(FBP)=L[Ψ(F6P,qc,FBP)∗Uk=0qc(F6P)]=G[Ψ(p2,qc,p3)∗Uk=0qc(p2)]=3.90 kcal/mol.(iii)
Uk=0qd(DHP)=L[Ψ(FBP,qd,DHP)∗Uk=0qd(FBP)]=G[Ψ(p3,qd,p4)∗Uk=0qd(p3)]=3.71 kcal/mol.
The Conc-Path is calculated atp5.
(i)
Uk=0qd(GAP)={L[Ψ(FBP,qd,GAP)∗Uk=0qd(FBP)]L[Ψ(DHP,qe,GAP)∗Uk=0qe(DHP)]={G[Ψ(p3,qd,p5)∗Uk=0qd(p3)]G[Ψ(p4,qe,p5)∗Uk=0qe(p4)]=4.00kcal/mole.(ii)
Uk=0qf(BPG)=L[Ψ(GAP,qf,BPG)∗Uk=0qf(GAP)]=G[Ψ(p5,qf,p6)∗Uk=0qf(p5)]=3.71 kcal/mol.(iii)
Uk=0qg(3PG)=L[Ψ(BPG,qg,3PG)∗Uk=0qg(BPG)]=G[Ψ(p6,qg,p7)∗Uk=0qg(p6)]=4.10 kcal/mol.(iv)
Uk=0qh(2PG)=L[Ψ(3PG,qh,2PG)∗Uk=0qh(3PG)]=G[Ψ(p7,qh,p8)∗Uk=0qh(p7)]=4.20 kcal/mol.(v)
Uk=0qi(PEP)=L[Ψ(2PG,qi,PEP)∗Uk=0qi(2PG)]=G[Ψ(p8,qi,p9)∗Uk=0qi(p8)]=4.00 kcal/mol.(vi)
Uk=0qj(Pyruvate)=L[Ψ(PEP,qj,Pyruvate)∗Uk=0qj(PEP)]=G[Ψ(p9,qj,p10)∗Uk=0qj(p9)]=0 kcal/mol.(vii)
Uk=0qj(Pyruvate)=0was set arbitrarily at the end of the
pathway, that is, after the pyruvate kinase step.Remark 5.
We are using[] to denote the OR-Path, ∑ to denote the AND-Path, and {| to denote the Conc-Path.


## Explanation.

Intuitively, a Lyapunov-like function can be considered as trajectory-tracking
function and optimal cost function. In our case, an optimal discrete problem,
the cost-to-target values are calculated using a discrete Lyapunov-like
function. Every time a discrete vector field of possible transitions is
calculated over the decision process. Each applied optimal transition (selected
via some “criterion,” e.g.,min(⋅)) decreases the optimal value, ensuring that
the optimal course of action is followed and establishing a preference
relation. In this sense, the criterion changes the asymptotic behavior of the
Lyapunov-like function by an optimal trajectory-tracking value. It is important
to note that the process finished when the equilibrium point is reached. This
point determines a significant difference with Bellman's equation.Example 6 (Conc-Path (see Figure2)).
Biochemical pathway of the free energy profile of the
glycolysis and pentose-phosphate. The following was adapted from Biochemistry
Lehninger et al. [26] and
Campbell and Farrel [30]. The free
energy changes were calculated using the steady-state metabolite concentrations
in RBC's and the equation U=RTln([Products]/[Reactants]). U=0 was set arbitrarily at the end of the pathway
after the pyruvate kinase step. The overall reaction for the pathway is shown
in Figure 1. Because L:D⊆ℝn→ℝ+,
we will use the function mini=1,…,|α|(αi∈D) to select the proper element of the vector α∈D:
(i)
Uk=0(Glucose)=17.17 kcal/mol;(ii)
Uk=0qa(G6P)=L[Ψ(Glucose,qa,G6P)∗Uk=0qa(Glucose)]=G[Ψ(p0,qa,p1)Uk=0qa(p0)]=9.17 kcal/mol.
A decision is taken andqb is selected instead of qk based in the environment condition modeled via
the routing policy (1/3, 2/3).
(i)
Uk=0qb(F6P)=L[Ψ(G6P,qb,F6P)∗Uk=0qb(G6P)]=G[2/3∗Uk=0qb(p1)]=8.98 kcal/mol.(ii)
Uk=0qc(FBP)=L[Ψ(F6P,qc,FBP)∗Uk=0qc(F6P)]=G[Ψ(p2,qc,p3)∗Uk=0qc(p2)]=3.90 kcal/mol.(iii)
Uk=0qd(DHP)=L[Ψ(FBP,qd,DHP)∗Uk=0qd(FBP)]=G[Ψ(p3,qd,p4)∗Uk=0qd(p3)]=3.71 kcal/mol.
The Conc-Path is calculated atp5.
(i)
Uk=0qd(GAP)={L[Ψ(FBP,qd,GAP)∗Uk=0qd(FBP)]L[Ψ(DHP,qe,GAP)∗Uk=0qe(DHP)]={G[Ψ(p3,qd,p5)∗Uk=0qd(p3)]G[Ψ(p4,qe,p5)∗Uk=0qe(p4)]=4.00kcal/mole.(ii)
Uk=0qf(BPG)=L[Ψ(GAP,qf,BPG)∗Uk=0qf(GAP)]=G[Ψ(p5,qf,p6)∗Uk=0qf(p5)]=3.71 kcal/mol.(iii)
Uk=0qg(3PG)=L[Ψ(BPG,qg,3PG)∗Uk=0qg(BPG)]=G[Ψ(p6,qg,p7)∗Uk=0qg(p6)]=4.10 kcal/mol.(iv)
Uk=0qh(2PG)=L[Ψ(3PG,qh,2PG)∗Uk=0qh(3PG)]=G[Ψ(p7,qh,p8)∗Uk=0qh(p7)]=4.20 kcal/mol.(v)
Uk=0qi(PEP)=L[Ψ(2PG,qi,PEP)∗Uk=0qi(2PG)]=G[Ψ(p8,qi,p9)∗Uk=0qi(p8)]=4.00 kcal/mol.(vi)
Uk=0qj(Pyruvate)=L[Ψ(PEP,qj,Pyruvate)∗Uk=0qj(PEP)]=G[Ψ(p9,qj,p10)∗Uk=0qj(p9)]=0 kcal/mol.(vii)
Uk=0qj(Pyruvate)=0was set arbitrarily at the end of the
pathway, that is, after the pyruvate kinase step.Remark 5.
We are using[] to denote the OR-Path, ∑ to denote the AND-Path, and {| to denote the Conc-Path.


## 4. Properties of the Model

We will identify the global system properties of the
DPPN as those properties related with the PN.Theorem 1.
The
decision process Petri netDDPN={P,Q,F,W,M0,π,U} is bounded by a place p∗ of the system.Proof.
Let us
suppose that the DPPN is not finite. Thenp∗ is never reached. Therefore, it is possible to
evolve in time n and to reduce the trajectory function value
over p∗.
However, the Lyapunov-like trajectory function converges to zero when n→∞ (or reached a minimum), that is, Un=0 or Un=C.Theorem 2.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net bounded by a
place p∗.
Then, a Lyapunov-like trajectory function can be constructed if and only if p∗ is reachable from s0.Proof.
(⇒) If U is a Lyapunov-like function then by the
previous theorem p∗ is reachable.
(⇐) By induction, let us construct the optimal
inverse path from p∗ to p0.
At each discrete time n∈ℕ in descending order (n is the maximum place index) the place of a system pn is observed and a transition qk∈Q leading to pn−1 is chosen. We choose the trajectory function U as the best choice set of states. We continue
this process until p0 is reached. Then, the trajectory function U is a Lyapunov-like function.


### Notation.

Letℕ={0,1,2,…}, ℕ+n0={n0,n0+1,…,n0+k,…}, n0≥0, ℝ=(−∞,∞) and ℝ+=[0,∞).Let us consider systems of first ordinary difference
equations given by(8)x(n+1)=ψ[n,x(n)]x(n0)=x0forn∈ℕ+n0, where x(n)∈ℝd and ψ:ℕ+n0×ℝd→ℝd is continuous in x(n).
Definition 3.
Then-vector valued function ϕ(n,n0,x0) is a solution of (8) if ϕ(n0,n0,x0)=x0 and ϕ(n+1,n0,x0)=ψ(n,ϕ(n,n0,x0)) for all n∈ℕ+n0.Definition 4.
The system (8) is said
to be (see [20, 21]) practically stable if, given (λ,A) with 0<λ<A,
it holds that(9)|x0|<λ⇒|x(n,n0,x0)|<A,∀n∈ℕ+n0,n0≥0.Definition 5.
The system (8) is said to be (see [20, 21]) uniformly practically stable, if it is practically
stable for every n0≥0.Definition 6.
A continuous functionα:[0,∞)→[0,∞) belongs to class 𝒦 if it is strictly increasing and α(0)=0.Let us consider [21] the vector function v(n,x(n)), v:ℕ+n0×ℝd→ℝ+p and  let
us define the variation of v relative to (8) by(10)Δv=v(n+1,x(n+1))−v(n,x(n)).Then, we have the following results [20, 21, 31, 32].
Theorem 3.
Letv:ℕ+n0×ℝn→ℝ+ be a continuous function in x,
such that for β,α∈𝒦,
it holds that β(|x|)≤v(n,x(n))≤α(|x|) and Δv(n,x(n))≤w(n,v(n,x(n))) holds for   n∈ℕ+n0, x(n)∈ℝn,
where w:ℕ+n0×ℝ+→ℝ is a continuous function in the second
argument. Suppose that γ(n,u)≡u+w(n,u) is nondecreasing in u, 0<λ<A are given and
finally that α(λ)<β(A) is satisfied. Then, the stability properties
of(11)u(n+1)=γ(n,u(n)),u(n0)=u0≥0imply the corresponding stability
properties of the system (8).Proof.
The
stability properties are preserved for the
following.
(1) Practically stable. Let us suppose thatu(n+1) is practically stable for (α(λ),β(A)) then, we have that u0<α(λ)⇒|u(n,n0,u0)|<β(A) for n≥n0,
where u(n,n0,u0) is the solution of (11). Let |x0|<λ, we claim that |x(n,n0,x0)|<A for n≥n0.
If not, there would exist n1≥n0 and a solution x(n,n0,x0) such that |x(n1)|≥A and |x(n)|<A for n0≤n<n1.
Choose u0=v(n0,x0),
then v(n,x(n))≤u(n) for all n≥n0.
(If not v(n,x(n))≤u(n) and v(n+1,x(n+1))>u(n+1)⇒γ(n,u(n))=u(n+1)<v(n+1,x(n+1))=Δv(n,x0)+v(n,x(n))≤w(n,v(n))+v(n,x(n))=γ(n,v(n))−v(n,x(n))+v(n,x(n))≤γ(n,u(n)) which is a
contradiction). Hence we get that β(A)≤β(|x(n1)|)≤v(n1,x(n1))≤u(n1,n0,u0)<β(A) (where the last inequality is because the
condition |x0|<λ⇒v(n0,x0)<α(λ)), which cannot hold therefore, system (8) is
practically stable.
(2) Stable. Suppose that system (11) is stable,
that is, for all ε>0∃ξ=ξ(ε,n0)>0 such that if u0<ξ⇒|u(n,n0,u0)|<β(ε) for n≥n0. Now, since v is a continuous function in x, there exists a δ=δ(ε,n0)>0 such that if |x0|<δ⇒|v(n0,x0)|<ξ then setting v(n0,x0) equal to u0 by the comparison principle (which was
implicitly proved in point 1) implies that v(n,x(n))≤u(n) for all n≥n0.
Taking δ equal to the one given from the continuity of v, |x(n,n0,x0)|<ε for n≥n0.
If not, there would exist n1≥n0 such that |x(n1)|≥ε and |x(n)|<ε for n0≤n<n1 but then(12)β(ε)≤β(x(n1))≤v(n1,x(n1))≤u(n1,n0,u0)<β(ε)which cannot hold therefore, we
must have that |x(n,n0,x0)|<ε for n≥n0 as desired.
(3) Asymptotically stable. We know that system (8)
is stable, the fact that it is asymptotically stable follows thanks
to(13)0≤limn→∞β(|xn|)≤limn→∞v(n,x(n))≤limn→∞u(n)=0⇒limn→∞|xn|=0.
(4) Uniformly stable. Assume that the
comparison system is uniformly stable, meaning that∃ξ=ξ(ε)>0 (independent of n) such that u0<ξ⇒|u(n,n0,u0)|<β(ε) for n≥n0 and let δ>0 independent of n such that |x0|<δ⇒|x(n,n0,x0)|<ε,   for n≥n0. Since v is a decreasing function there exists  aαϵ𝒦 such that v(n,x(n))≤α(|xn|). Then, choosing δ=α−1(ξ) works (if |x0|<δ=α−1(ξ)⇒v(n0,x0)=|v(n0,x0)|≤α(|x0|)<ξ) and choosing u0=v(n0,x0) we arrive to the inequality(14)β(|x(n)|)≤v(n,x(n))≤u(n,n0,u0)<β(ε).But δ is independent of n.
Therefore, the system (8) is uniformly stable.We will extend
the last theorem to the case of several Lyapunov functions. Let us consider a
vector Lyapunov functionv(n,x(n)), v:ℕ+n0×ℝd→ℝ+p and let us define the variation of v relative to (8). Then, we have the following
theorem.
Theorem 4.
Letv:ℕ+n0×ℝd→ℝ+p be a continuous function in x,
define the function v0(n,x(n))=∑i=1pvi(n,x(n)) such that it satisfies the
estimates:(15)β(|x|)≤v0(n,x(n))≤α(|x|)forα,β∈𝒦,Δv(n,x(n))≤w(n,v(n,x(n)))for n∈ℕ+n0, x(n)∈ℝd, where w:ℕ+n0×ℝ+p→ℝp is a continuous function in the second
argument. Assume that γ(n,u)≜u+w(n,u) is nondecreasing in u, 0<λ<J are given and α(λ)<β(A) is satisfied. Then, the practical stability
properties of(16)u(n+1)=γ(n,u(n)),u(n0)=u0≥0implies the corresponding
practical stability properties of system (8).Proof.
(1) Let us suppose thatu(n+1) is practically stable for (α(λ),β(A)). Then we have that ∑i=1pu0i<α(λ)⇒∑i=1pui(n,n0,u0)<β(A), for n≥n0,
where ui(n,n0,u0) is the vector solution of (16). Let |x0|<λ,
we claim that |x(n,n0,x0)|<A for n≥n0.
If not, there would exist n1≥n0 and a solution x(n,n0,x0) such that |x(n1)|≥A and |x(n)|<A for n0≤n<n1.
Choose u0=v(n0,x0),
then v(n,x(n))≤u(n,n0,u0) for all n≥n0.
Therefore we have that β(A)≤β(|x(n1)|)≤v0(n1,x(n1))≤∑i=1pui(n1,n0,u0)<β(A) which cannot hold. As a result, system (8) is
practically stable.
(2) From the continuity ofv with respect to the second argument, it is
always possible to make v0(n0,x0)<∑i=1pu0i<α(λ)⇒v0(n,x(n))≤∑i=1pui(n,n0,u0)<β(A).
We want to prove that |x(n,n0,x0)|<A for n≥n0. If it is not true, there exists an n1≥n0 and a solution x(n,n0,x0) such that |x(n1)|≥A and |x(n)|<A for n0≤n<n1. Then, we have that β(A)≤β(|x(n1)|)≤v0(n1,x(n1))≤∑i=1pui(n1,n0,u0)<β(A)!, which proves our claim.Remark 6.
If in the point 1 of the proof it is not true thatv(n,x(n))≤e(n,n0,e0) and v(n+1,x(n+1))>e(n+1,n0,e0),
then we have that γ(n,e(n))=e(n+1,n0,e0)<v(n+1,x(n+1))=Δv(n,x0)+v(n,x(n))≤w(n,v(n))+v(n,x(n))=γ(n,v(n))−v(n,x(n))+v(n,x(n))=γ(n,v(n))≤γ(n,e(n))   which is a contradiction.Then, we have the following result [21].
Corollary 1.
From
Theorem5, the following hold.
(1)
Ifw(n,e)≡0,
the uniform practical stability of (8) which implies structural stability [21, 33] is
obtained.(2)
Ifw(n,e)=−c(e),
for c∈𝒦,
the uniform practical asymptotic stability of (8) [21] is
obtained.Example 7.
The
diamond is the stable form of carbon at extremely high pressures while the
graphite is the stable form at normal atmospheric pressures. Regardless of
that, diamonds appear stable at normal temperatures and pressures, but, in
fact, are very slowly converting to graphite. Heat increases the rate of this
transformation, but at normal temperatures the diamond is uniformly practically
stable.For Petri nets, we have the following results of
stability [31].
Proposition 1.
LetPN be a Petri net. Therefore, PN is uniform practical stable if there exists a Φ strictly positive m vector such that(17)Δv=uTAΦ≤0.Moreover, N is uniform practical asymptotic stability if
the following equation holds:(18)Δv=uTAΦ≤−c(e),forc∈𝒦.Proof.
Let us choose as our candidate
Lyapunov functionv(M)=MTΦ with Φ and m vector to be chosen. It is simple to verify
that v satisfies all the conditions of Theorem 3.
Therefore, the uniform practical asymptotic stability is obtained if there
exists a strictly positive vector Φ such that equation (17) holds.Proposition 2.
LetPN be a Petri net. Therefore, PN is uniformly practically stable if there
exists a Φ strictly positive m vector such that(19)Δv=uTAΦ≤0⟺AΦ≤0.Proof.
⇒) Since uTAΦ≤0 holds, therefore for every u we have that AΦ≤0.
⇐) This came from the fact that u is positive.Remark 7.
The if-and-only-if relationship of
(19) exists from the fact that u is positive.Example 8.
The biochemical pathway of the
glycolysis (Figure1). The incidence matrix is as follows:(20)[−110000000000−110000000000−110000000000−111000000000−110000000000−110000000000−110000000000−110000000000−110000000000−11]. Choosing  Φ=[1,1,1,1,1/2,1/2,1/2,1/2,1/2,1/2,1/2], Φ>0, we obtain that  AΦ=[0,0,0,−1/2,0,0,0,0,0,0]   concluding stability.Definition 7.
An equilibrium point with
respect to a decision process Petri netDDPN={P,Q,F,W,M0,π,U} is a place p∗∈P such that Ml(p∗)=S<∞,
for all l≥k,
and p∗ is a sink.Theorem 5.
The decision process Petri netDDPN={P,Q,F,W,M0,π,U} is uniformly practically stable iff there
exists a Φ strictly positive m vector such that Δv=uTAΦ≤0.Proof.
⇒) It follows directly from Propositions 1 and 2.
⇐) Let us suppose by contradiction that uTAΦ>0 with Φ fixed. From M′=M+uTA we have that M′Φ=MΦ+uTAΦ>MΦ.
Then, it is possible to construct an increasing sequence MΦ<M′Φ<⋯<MnΦ<⋯ which grows up without bound. Therefore, the DDPN is not uniformly practically stable.Remark 8.
It is important to underline that
the only places where the DPPN will be allowed to get blocked are those which
correspond to equilibrium points.We will identify the trajectory-tracking properties of
the DPPN as those properties related with the trajectory-tracking value at each
place of the PN. In this sense, we will relate an optimum point the best
possible performance choice. Formally we will introduce the following
definition [23].
Definition 8.
A final decision pointpf∈P with respect to a decision process Petri net DDPN={P,Q,F,W,M0,π,U} is a place p∈P where the infimum is asymptotically approached
(or the minimum is attained), that is, U(p)=0 or U(p)=C.Definition 9.
An optimum pointpΔ∈P with respect to a decision process Petri net DDPN={P,Q,F,W,M0,π,U} is a final decision point pf∈P where the best choice is selected “according
to some criteria.”Property 3.
Every decision process Petri netDDPN={P,Q,F,W,M0,π,U} has a final decision point.Remark 9.
In case that∃p1,…,pn∈P,
such that U(p1)=⋯=U(pn)=0,
then p1,…,pn are optimum points.Remark 10.
The monotonicity ofU guarantees that it is possible to make the
search starting from the decision points.Then, we can conclude the following
theorem.Theorem 6.
LetDDPN={P,Q,F,W,M0,π,U} be a finite decision process Petri net and let (p0,p1,…,pn) be a realized trajectory which converges to pΔ such that ∃ϵi:|Ui+1−Ui|>ϵi(withϵi>0).
Let ϵ=min{ϵi}, then the optimum decision point pΔ is reached in a time step bounded by O(U0/ϵ).Proof.
Let us
suppose thatpΔ is never reached, then, pΔ is not a sink (the last place) in the decision
process Petri net. So, it is possible to find some output transition to pΔ.
Therefore, it is possible to reduce the trajectory function value over pΔ by at least ϵ.
As a result, it is possible to obtain a lower value than C (that is a contradiction).Theorem 7.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net. Then, U converges to an optimum (final) decision point pΔ(pf).Proof.
We have to show thatU converges to an optimum (final) decision point pΔ(pf). By the previous theorem, the optimum decision
point pΔ is reached in a time step bounded by O(U0/ϵ),
therefore U converges to pΔ.Proposition 3.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net and let pΔ∈P be an optimum point. Then U(pΔ)≤U(p),
for all p∈P such that p≤UpΔ.Proof.
We have thatU(pΔ) is equal to the minimum or the infimum.
Therefore, U(pΔ)≤U(p) for all p∈P such that p≤UpΔ.Theorem 8.
The decision process Petri netDDPN={P,Q,F,W,M0,π,U} is uniformly practically stable iff U(pi+1)−U(pi)≤0.Proof.
(⇒) Let us choose v=Id(U(pi)),
then Δv=U(pi+1)−U(pi)≤0.
Then by the autonomous version of Theorem 4 and Corollary 1 the DPPN is stable.
(⇐) We want to show that the DPPN is practically
stable, that is, given 0<λ<A,
we must show that |U(pi)|<A.
We know that U(p0)<λ and since U is nondecreasing, we have that |U(pi)|<|U(p0)|<λ<A.Theorem 9.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net. If p∗∈P is an equilibrium point, then it is a final
decision point.
Proof.
Let us suppose thatp∗ is an equilibrium point, we want to show that
its trajectory-tracking value has asymptotically approached an infimum (or
reached a minimum). Since p∗ is an equilibrium point, by definition, it is
bounded and it is a sink, for example, its marking can not be modified. But,
this implies that the routing policy attached to the transition(s) that follows p∗ is 0 (in case there is such a transition(s),
i.e., worst case). Therefore, its trajectory-tracking value can not be modified
and since the value is a decreasing function of pi,
an infimum or a minimum is attained. Then, p∗ is a final decision point.Theorem 10.
LetDDPN={P,Q,F,W,M0,π,U} be a finite and nonblocking decision process
Petri net (unless p∈P is an equilibrium point). If pf∈P is a final decision point, then it is an
equilibrium point.
Proof.
Ifpf is a final decision point, since the DDPN is finite, there exists a k such that Uk(pf)=C.
Let us suppose that pf is not an equilibrium point.
Case 1.
Then, it is not bounded. So, it is possible to
increment the marks ofpf in the net. Therefore, it is possible to
modify its trajectory-tracking value. As a result, it is possible to obtain a lower
value than C.
Case 2.
Then, it is not bounded and it is not a sink.
So, it is possible to fire some output transition topf in such a way that its marking is modified.
Therefore, it is possible to modify the trajectory-tracking value over pf.
As a result, it is possible to obtain a lower trajectory-tracking value than C.Corollary 2.
LetDDPN={P,Q,F,W,M0,π,U} be a finite and nonblocking decision process
Petri net (unless p∈P is an equilibrium point). Then, an optimum
point pΔ∈P is an equilibrium point.Proof.
From
the previous theorem, we know that a final decision point is an equilibrium
point and since in particularpΔ is
final decision point, then it is an equilibrium point.


## Notation.

Letℕ={0,1,2,…}, ℕ+n0={n0,n0+1,…,n0+k,…}, n0≥0, ℝ=(−∞,∞) and ℝ+=[0,∞).Let us consider systems of first ordinary difference
equations given by(8)x(n+1)=ψ[n,x(n)]x(n0)=x0forn∈ℕ+n0, where x(n)∈ℝd and ψ:ℕ+n0×ℝd→ℝd is continuous in x(n).
Definition 3.
Then-vector valued function ϕ(n,n0,x0) is a solution of (8) if ϕ(n0,n0,x0)=x0 and ϕ(n+1,n0,x0)=ψ(n,ϕ(n,n0,x0)) for all n∈ℕ+n0.Definition 4.
The system (8) is said
to be (see [20, 21]) practically stable if, given (λ,A) with 0<λ<A,
it holds that(9)|x0|<λ⇒|x(n,n0,x0)|<A,∀n∈ℕ+n0,n0≥0.Definition 5.
The system (8) is said to be (see [20, 21]) uniformly practically stable, if it is practically
stable for every n0≥0.Definition 6.
A continuous functionα:[0,∞)→[0,∞) belongs to class 𝒦 if it is strictly increasing and α(0)=0.Let us consider [21] the vector function v(n,x(n)), v:ℕ+n0×ℝd→ℝ+p and  let
us define the variation of v relative to (8) by(10)Δv=v(n+1,x(n+1))−v(n,x(n)).Then, we have the following results [20, 21, 31, 32].
Theorem 3.
Letv:ℕ+n0×ℝn→ℝ+ be a continuous function in x,
such that for β,α∈𝒦,
it holds that β(|x|)≤v(n,x(n))≤α(|x|) and Δv(n,x(n))≤w(n,v(n,x(n))) holds for   n∈ℕ+n0, x(n)∈ℝn,
where w:ℕ+n0×ℝ+→ℝ is a continuous function in the second
argument. Suppose that γ(n,u)≡u+w(n,u) is nondecreasing in u, 0<λ<A are given and
finally that α(λ)<β(A) is satisfied. Then, the stability properties
of(11)u(n+1)=γ(n,u(n)),u(n0)=u0≥0imply the corresponding stability
properties of the system (8).Proof.
The
stability properties are preserved for the
following.
(1) Practically stable. Let us suppose thatu(n+1) is practically stable for (α(λ),β(A)) then, we have that u0<α(λ)⇒|u(n,n0,u0)|<β(A) for n≥n0,
where u(n,n0,u0) is the solution of (11). Let |x0|<λ, we claim that |x(n,n0,x0)|<A for n≥n0.
If not, there would exist n1≥n0 and a solution x(n,n0,x0) such that |x(n1)|≥A and |x(n)|<A for n0≤n<n1.
Choose u0=v(n0,x0),
then v(n,x(n))≤u(n) for all n≥n0.
(If not v(n,x(n))≤u(n) and v(n+1,x(n+1))>u(n+1)⇒γ(n,u(n))=u(n+1)<v(n+1,x(n+1))=Δv(n,x0)+v(n,x(n))≤w(n,v(n))+v(n,x(n))=γ(n,v(n))−v(n,x(n))+v(n,x(n))≤γ(n,u(n)) which is a
contradiction). Hence we get that β(A)≤β(|x(n1)|)≤v(n1,x(n1))≤u(n1,n0,u0)<β(A) (where the last inequality is because the
condition |x0|<λ⇒v(n0,x0)<α(λ)), which cannot hold therefore, system (8) is
practically stable.
(2) Stable. Suppose that system (11) is stable,
that is, for all ε>0∃ξ=ξ(ε,n0)>0 such that if u0<ξ⇒|u(n,n0,u0)|<β(ε) for n≥n0. Now, since v is a continuous function in x, there exists a δ=δ(ε,n0)>0 such that if |x0|<δ⇒|v(n0,x0)|<ξ then setting v(n0,x0) equal to u0 by the comparison principle (which was
implicitly proved in point 1) implies that v(n,x(n))≤u(n) for all n≥n0.
Taking δ equal to the one given from the continuity of v, |x(n,n0,x0)|<ε for n≥n0.
If not, there would exist n1≥n0 such that |x(n1)|≥ε and |x(n)|<ε for n0≤n<n1 but then(12)β(ε)≤β(x(n1))≤v(n1,x(n1))≤u(n1,n0,u0)<β(ε)which cannot hold therefore, we
must have that |x(n,n0,x0)|<ε for n≥n0 as desired.
(3) Asymptotically stable. We know that system (8)
is stable, the fact that it is asymptotically stable follows thanks
to(13)0≤limn→∞β(|xn|)≤limn→∞v(n,x(n))≤limn→∞u(n)=0⇒limn→∞|xn|=0.
(4) Uniformly stable. Assume that the
comparison system is uniformly stable, meaning that∃ξ=ξ(ε)>0 (independent of n) such that u0<ξ⇒|u(n,n0,u0)|<β(ε) for n≥n0 and let δ>0 independent of n such that |x0|<δ⇒|x(n,n0,x0)|<ε,   for n≥n0. Since v is a decreasing function there exists  aαϵ𝒦 such that v(n,x(n))≤α(|xn|). Then, choosing δ=α−1(ξ) works (if |x0|<δ=α−1(ξ)⇒v(n0,x0)=|v(n0,x0)|≤α(|x0|)<ξ) and choosing u0=v(n0,x0) we arrive to the inequality(14)β(|x(n)|)≤v(n,x(n))≤u(n,n0,u0)<β(ε).But δ is independent of n.
Therefore, the system (8) is uniformly stable.We will extend
the last theorem to the case of several Lyapunov functions. Let us consider a
vector Lyapunov functionv(n,x(n)), v:ℕ+n0×ℝd→ℝ+p and let us define the variation of v relative to (8). Then, we have the following
theorem.
Theorem 4.
Letv:ℕ+n0×ℝd→ℝ+p be a continuous function in x,
define the function v0(n,x(n))=∑i=1pvi(n,x(n)) such that it satisfies the
estimates:(15)β(|x|)≤v0(n,x(n))≤α(|x|)forα,β∈𝒦,Δv(n,x(n))≤w(n,v(n,x(n)))for n∈ℕ+n0, x(n)∈ℝd, where w:ℕ+n0×ℝ+p→ℝp is a continuous function in the second
argument. Assume that γ(n,u)≜u+w(n,u) is nondecreasing in u, 0<λ<J are given and α(λ)<β(A) is satisfied. Then, the practical stability
properties of(16)u(n+1)=γ(n,u(n)),u(n0)=u0≥0implies the corresponding
practical stability properties of system (8).Proof.
(1) Let us suppose thatu(n+1) is practically stable for (α(λ),β(A)). Then we have that ∑i=1pu0i<α(λ)⇒∑i=1pui(n,n0,u0)<β(A), for n≥n0,
where ui(n,n0,u0) is the vector solution of (16). Let |x0|<λ,
we claim that |x(n,n0,x0)|<A for n≥n0.
If not, there would exist n1≥n0 and a solution x(n,n0,x0) such that |x(n1)|≥A and |x(n)|<A for n0≤n<n1.
Choose u0=v(n0,x0),
then v(n,x(n))≤u(n,n0,u0) for all n≥n0.
Therefore we have that β(A)≤β(|x(n1)|)≤v0(n1,x(n1))≤∑i=1pui(n1,n0,u0)<β(A) which cannot hold. As a result, system (8) is
practically stable.
(2) From the continuity ofv with respect to the second argument, it is
always possible to make v0(n0,x0)<∑i=1pu0i<α(λ)⇒v0(n,x(n))≤∑i=1pui(n,n0,u0)<β(A).
We want to prove that |x(n,n0,x0)|<A for n≥n0. If it is not true, there exists an n1≥n0 and a solution x(n,n0,x0) such that |x(n1)|≥A and |x(n)|<A for n0≤n<n1. Then, we have that β(A)≤β(|x(n1)|)≤v0(n1,x(n1))≤∑i=1pui(n1,n0,u0)<β(A)!, which proves our claim.Remark 6.
If in the point 1 of the proof it is not true thatv(n,x(n))≤e(n,n0,e0) and v(n+1,x(n+1))>e(n+1,n0,e0),
then we have that γ(n,e(n))=e(n+1,n0,e0)<v(n+1,x(n+1))=Δv(n,x0)+v(n,x(n))≤w(n,v(n))+v(n,x(n))=γ(n,v(n))−v(n,x(n))+v(n,x(n))=γ(n,v(n))≤γ(n,e(n))   which is a contradiction.Then, we have the following result [21].
Corollary 1.
From
Theorem5, the following hold.
(1)
Ifw(n,e)≡0,
the uniform practical stability of (8) which implies structural stability [21, 33] is
obtained.(2)
Ifw(n,e)=−c(e),
for c∈𝒦,
the uniform practical asymptotic stability of (8) [21] is
obtained.Example 7.
The
diamond is the stable form of carbon at extremely high pressures while the
graphite is the stable form at normal atmospheric pressures. Regardless of
that, diamonds appear stable at normal temperatures and pressures, but, in
fact, are very slowly converting to graphite. Heat increases the rate of this
transformation, but at normal temperatures the diamond is uniformly practically
stable.For Petri nets, we have the following results of
stability [31].
Proposition 1.
LetPN be a Petri net. Therefore, PN is uniform practical stable if there exists a Φ strictly positive m vector such that(17)Δv=uTAΦ≤0.Moreover, N is uniform practical asymptotic stability if
the following equation holds:(18)Δv=uTAΦ≤−c(e),forc∈𝒦.Proof.
Let us choose as our candidate
Lyapunov functionv(M)=MTΦ with Φ and m vector to be chosen. It is simple to verify
that v satisfies all the conditions of Theorem 3.
Therefore, the uniform practical asymptotic stability is obtained if there
exists a strictly positive vector Φ such that equation (17) holds.Proposition 2.
LetPN be a Petri net. Therefore, PN is uniformly practically stable if there
exists a Φ strictly positive m vector such that(19)Δv=uTAΦ≤0⟺AΦ≤0.Proof.
⇒) Since uTAΦ≤0 holds, therefore for every u we have that AΦ≤0.
⇐) This came from the fact that u is positive.Remark 7.
The if-and-only-if relationship of
(19) exists from the fact that u is positive.Example 8.
The biochemical pathway of the
glycolysis (Figure1). The incidence matrix is as follows:(20)[−110000000000−110000000000−110000000000−111000000000−110000000000−110000000000−110000000000−110000000000−110000000000−11]. Choosing  Φ=[1,1,1,1,1/2,1/2,1/2,1/2,1/2,1/2,1/2], Φ>0, we obtain that  AΦ=[0,0,0,−1/2,0,0,0,0,0,0]   concluding stability.Definition 7.
An equilibrium point with
respect to a decision process Petri netDDPN={P,Q,F,W,M0,π,U} is a place p∗∈P such that Ml(p∗)=S<∞,
for all l≥k,
and p∗ is a sink.Theorem 5.
The decision process Petri netDDPN={P,Q,F,W,M0,π,U} is uniformly practically stable iff there
exists a Φ strictly positive m vector such that Δv=uTAΦ≤0.Proof.
⇒) It follows directly from Propositions 1 and 2.
⇐) Let us suppose by contradiction that uTAΦ>0 with Φ fixed. From M′=M+uTA we have that M′Φ=MΦ+uTAΦ>MΦ.
Then, it is possible to construct an increasing sequence MΦ<M′Φ<⋯<MnΦ<⋯ which grows up without bound. Therefore, the DDPN is not uniformly practically stable.Remark 8.
It is important to underline that
the only places where the DPPN will be allowed to get blocked are those which
correspond to equilibrium points.We will identify the trajectory-tracking properties of
the DPPN as those properties related with the trajectory-tracking value at each
place of the PN. In this sense, we will relate an optimum point the best
possible performance choice. Formally we will introduce the following
definition [23].
Definition 8.
A final decision pointpf∈P with respect to a decision process Petri net DDPN={P,Q,F,W,M0,π,U} is a place p∈P where the infimum is asymptotically approached
(or the minimum is attained), that is, U(p)=0 or U(p)=C.Definition 9.
An optimum pointpΔ∈P with respect to a decision process Petri net DDPN={P,Q,F,W,M0,π,U} is a final decision point pf∈P where the best choice is selected “according
to some criteria.”Property 3.
Every decision process Petri netDDPN={P,Q,F,W,M0,π,U} has a final decision point.Remark 9.
In case that∃p1,…,pn∈P,
such that U(p1)=⋯=U(pn)=0,
then p1,…,pn are optimum points.Remark 10.
The monotonicity ofU guarantees that it is possible to make the
search starting from the decision points.Then, we can conclude the following
theorem.Theorem 6.
LetDDPN={P,Q,F,W,M0,π,U} be a finite decision process Petri net and let (p0,p1,…,pn) be a realized trajectory which converges to pΔ such that ∃ϵi:|Ui+1−Ui|>ϵi(withϵi>0).
Let ϵ=min{ϵi}, then the optimum decision point pΔ is reached in a time step bounded by O(U0/ϵ).Proof.
Let us
suppose thatpΔ is never reached, then, pΔ is not a sink (the last place) in the decision
process Petri net. So, it is possible to find some output transition to pΔ.
Therefore, it is possible to reduce the trajectory function value over pΔ by at least ϵ.
As a result, it is possible to obtain a lower value than C (that is a contradiction).Theorem 7.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net. Then, U converges to an optimum (final) decision point pΔ(pf).Proof.
We have to show thatU converges to an optimum (final) decision point pΔ(pf). By the previous theorem, the optimum decision
point pΔ is reached in a time step bounded by O(U0/ϵ),
therefore U converges to pΔ.Proposition 3.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net and let pΔ∈P be an optimum point. Then U(pΔ)≤U(p),
for all p∈P such that p≤UpΔ.Proof.
We have thatU(pΔ) is equal to the minimum or the infimum.
Therefore, U(pΔ)≤U(p) for all p∈P such that p≤UpΔ.Theorem 8.
The decision process Petri netDDPN={P,Q,F,W,M0,π,U} is uniformly practically stable iff U(pi+1)−U(pi)≤0.Proof.
(⇒) Let us choose v=Id(U(pi)),
then Δv=U(pi+1)−U(pi)≤0.
Then by the autonomous version of Theorem 4 and Corollary 1 the DPPN is stable.
(⇐) We want to show that the DPPN is practically
stable, that is, given 0<λ<A,
we must show that |U(pi)|<A.
We know that U(p0)<λ and since U is nondecreasing, we have that |U(pi)|<|U(p0)|<λ<A.Theorem 9.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net. If p∗∈P is an equilibrium point, then it is a final
decision point.
Proof.
Let us suppose thatp∗ is an equilibrium point, we want to show that
its trajectory-tracking value has asymptotically approached an infimum (or
reached a minimum). Since p∗ is an equilibrium point, by definition, it is
bounded and it is a sink, for example, its marking can not be modified. But,
this implies that the routing policy attached to the transition(s) that follows p∗ is 0 (in case there is such a transition(s),
i.e., worst case). Therefore, its trajectory-tracking value can not be modified
and since the value is a decreasing function of pi,
an infimum or a minimum is attained. Then, p∗ is a final decision point.Theorem 10.
LetDDPN={P,Q,F,W,M0,π,U} be a finite and nonblocking decision process
Petri net (unless p∈P is an equilibrium point). If pf∈P is a final decision point, then it is an
equilibrium point.
Proof.
Ifpf is a final decision point, since the DDPN is finite, there exists a k such that Uk(pf)=C.
Let us suppose that pf is not an equilibrium point.
Case 1.
Then, it is not bounded. So, it is possible to
increment the marks ofpf in the net. Therefore, it is possible to
modify its trajectory-tracking value. As a result, it is possible to obtain a lower
value than C.
Case 2.
Then, it is not bounded and it is not a sink.
So, it is possible to fire some output transition topf in such a way that its marking is modified.
Therefore, it is possible to modify the trajectory-tracking value over pf.
As a result, it is possible to obtain a lower trajectory-tracking value than C.Corollary 2.
LetDDPN={P,Q,F,W,M0,π,U} be a finite and nonblocking decision process
Petri net (unless p∈P is an equilibrium point). Then, an optimum
point pΔ∈P is an equilibrium point.Proof.
From
the previous theorem, we know that a final decision point is an equilibrium
point and since in particularpΔ is
final decision point, then it is an equilibrium point.


## 5. Completeness

Theorem 11.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net and let (p0,p1,…,pn) be a realized trajectory which converges to p∗ such that ∃ϵi:|Ui+1−Ui|>ϵi(withϵi>0).
Let ϵ=min{ϵi}, then an optimum point p∗ is reached in a time step bounded by O(U0/ϵ).Proof.
Let us
suppose thatp∗ is never reached, then p∗ is not the last place in the decision process
Petri net. So, it is possible to find some output transition to p∗.
Therefore, it is possible to reduce the trajectory function value over p∗ by at least ϵ.
As a result, it is possible to obtain a lower value than C (that is a contradiction).Remark 11.
The complexity timeO(U0/ϵ) differs with that of the Dijkstra's algorithm.Remark 12.
Each path inDDPN corresponds to a trajectory
of/in a given system. The trajectory-tracking
function value of U at the source place (U0mon) divided by ϵ=min{ϵi} equals the length of the shortest-path. Then,
the infimum is equivalent to the infimum length over all paths in DDPN.Theorem 12.
LetDDPN={P,Q,F,W,M0,π,U} be a decision process Petri net. Then, U converges to a point p∗.Proof.
We have to show thatU converges to a point p∗. By the previous theorem, the optimum point p∗ is reached in a time step bounded by O(U0/ϵ),
therefore U converges to p∗.Proposition 4.
The
finite and nonblocking (unlessp∈P is an equilibrium point) condition over the DDPN can not be relaxed.Proof.
(1) Let us suppose that theDDPN is not finite, that is, p is in a cycle, then the Lyapunov-like function
converges when k→∞,
to zero, that is, L(p)=0 but the DPPN has no final place therefore, it
is not an equilibrium point.
(2) Let us suppose that theDDPN blocks at some place (not an equilibrium point) p∈P.
Then, the Lyapunov-like function has a minimum at place p, lets say L(p)=C but p is not an equilibrium point, because it is not
necessary to have a sink in the net.


## 6. Conclusions

In this work, a formal framework for shortest-path
decision process problem representation has been presented. Whereas in previous
work, attention was restricted to tracking the net using a utility function Bellman's
equation, this work uses a Lyapunov-like function. In this sense, we are
changing the traditional cost function by a trajectory-tracking function which
is also an optimal cost-to-target function for tracking the net. This makes a
significant difference in the conceptualization of the problem domain. The
Lyapunov method introduces a new equilibrium and stability concept in decision
process.



---

*Source: 162450-2009-01-15.xml*