Luis M Torres
email: luis.torres@epn.edu.ec

Annegret K Wagler
email: wagler@isima.fr

The dynamics of deterministic systems -A survey

We present a model for the dynamics of discrete deterministic systems, based on an extension of the Petri net framework. Our model relies on the definition of a priority relation between conflicting transitions, which is encoded in a compact manner by orienting the edges of a transition conflict graph. The benefit is that this allows the use of a successor oracle for the study of dynamic processes from a global point of view, independent from a particular initial state and the (complete) construction of the reachability graph. We provide a characterization, in terms of a local consistency condition, of those deterministic systems whose dynamic behavior can be encoded using our approach and consider the problem of recognizing when an orientation of the transition conflict graph is valid for this purpose . Finally, we address the problem of gaining the information that allows to provide an appropriate priority relation gouverning the dynamic behavior of the studied system and dicuss some further implications and generalizations of the studied approach.

Introduction

Petri nets constitute a well-established framework for modeling complex dynamic systems. Their broad application range includes the design of asynchronous hardware circuits [START_REF] Yakovlev | Modelling, analysis and synthesis of asynchronous control circuits using Petri nets[END_REF], the analysis of production and workflow systems [START_REF] Adam | Modeling and analysis of workflows using Petri nets[END_REF], the analysis and control of batch processes [START_REF] Gu | A survey of Petri net applications in batch processes[END_REF], the design of distributed algorithms for networks of agents [START_REF] Reisig | Elements of distributed algorithms: modeling and analysis with Petri nets[END_REF], and the modeling and simulation of biological networks [START_REF] Hardy | Modeling and simulation of molecular biology systems using Petri nets: modeling goals of various approaches[END_REF][START_REF] Heiner | Petri nets for systems and synthetic biology[END_REF][START_REF] Marwan | Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks[END_REF], to cite only some prominent examples.

Petri nets also turned out to be a flexible modeling framework that has been extended in various ways for dealing with different applications. For instance, colored and high-level Petri nets have been widely used for protocol specification in communication networks [START_REF] Billington | Application of Petri Nets to Communication Networks[END_REF][START_REF] Jensen | Coloured Petri nets: basic concepts, analysis methods and practical use[END_REF]. Stochastic Petri nets are used in cases where uncertainty is attached to input data, to describe external noise generated by the environment, as well as noise that might be intrinsic to a system [START_REF] Marsan | Modelling with generalized stochastic Petri nets[END_REF][START_REF] Balbo | Introducation to stochastic Petri nets[END_REF]. Hybrid Petri nets allow to model systems were both continuous and discrete processes coexist [START_REF] David | Discrete, Continuous, and Hybrid Petri Nets[END_REF], and the inclusion of additional features required for modeling certain biological networks has led to the definition of Hybrid Functional Petri nets [START_REF] Matsuno | Biopathways representation and simulation on hybrid functional Petri net[END_REF]. In this paper we consider another possible extension that aims at representing systems whose dynamic behavior exhibits deterministic features.

More formally, a network G = (P, T, A, w) reflects the involved components (like network elements, technical components, biological entities etc.) by places p ∈ P and their interactions (like transformations, causal dependencies, chemical reactions etc.) by transitions t ∈ T , linked by weighted directed arcs. Each place p ∈ P can be marked with an integral number of tokens defining a system state x ∈ Z P + , and dynamic processes are represented by sequences of state changes, starting from an initial state x 0 and performed by consecutively switching or firing enabled transitions (see Section 2 for more details).

Usually, the dynamic behavior is the result of several conflicting as well as concurrent ongoing dynamic processes. A Petri net is a pair (G, x 0 ) consisting of a network G together with an initial state x 0 , and its state space X (x 0 ) is understood as the set of all further system states which can be reached from x 0 by switching or firing sequences of transitions, see e.g. [START_REF] Reisig | Petri nets: an introduction[END_REF] for more information. In this framework, describing the dynamics of a system might be done by model animation, i.e., by simulating the flow of tokens inside the network as transitions are switched [START_REF] Heiner | Schwarick: Snoopy -a unifying Petri net tool[END_REF]. Given a network G and an initial state x 0 ∈ X , some central problems that are usually studied in this context are:

-Reachability: Determine whether the system may eventually reach one of a set of target states after a finite sequence of transition switches. -Boundedness: Determine if there are sequences of transition switches that lead to the accumulation of an unlimited number of tokens at some place of the network. -Existence of deadlocks: Determine whether the system can reach a state at which no transitions are enabled. -Liveness: Determine whether no sequence of transition switches can put the system into a state where some transition is permanently disabled.

The problems mentioned above are in general hard from a computational complexity point of view. For instance, reachability was proven to require exponential space [START_REF] Lipton | The reachability problem requires exponential space[END_REF] and decidability of this problem could only be established some years later [START_REF] Mayr | An algorithm for the general Petri net reachability problem[END_REF][START_REF] Mayr | An algorithm for the general Petri net reachability problem[END_REF].

Partial versus global point of view on a system. Dynamic processes can be encoded as directed paths in a state digraph G where nodes represent states and there is a directed arc between two states x, x ′ if x ′ can be obtained from x by switching a single transition. It is common practice to use the term reachability or marking graph to refer to the subgraph G(x 0 ) of G induced by the set X (x 0 ) of nodes corresponding to those states that can be reached from the initial state x 0 of the network. Considering G(x 0 ) allows only a partial view on the studied system which is, e.g., suitable for a technical system performing exactly one process. However, already a failure of one or several components of such a system can change the initial state, and a more global view is required to coherently model both the normal and the mal function of the system, and to detect the faulty element(s) by an according failure analysis.

Similarly, the study of biological systems by performing experiments can be seen as putting the system in a particular initial state and observing the evolution of the system in terms of resulting sequences of state changes. Due to the intrinsic complexity of biological systems, the dynamic behavior of such systems can rarely be understood by performing a single experiment. In general, several experiments starting from different initial states are required and need to be coherently interpreted in a single model.

To study dynamic systems and processes therein from a more global point of view (independent from a particular initial state), we therefore suggest to consider the state digraph G on the potential state space X of the system, i.e., on the set of all theoretically possible states.

Non-deterministic versus deterministic systems. While studying dynamic processes, a particular situation occurs when so-called dynamic conflicts are present at states, in which two transitions are enabled, but switching one disables the other. In this case, model animation does not allow definite conclusions about any system properties, as mentioned in [START_REF] Heiner | Petri nets for systems and synthetic biology[END_REF]. The reason is that the occurrence of dynamic conflicts is understood as alternative (branching) system behavior, where a decision between these alternatives is taken non-deterministically.

However, there are examples of systems that show a deterministic behavior despite the existence of dynamic conflicts. We call a dynamic system deterministic if any state x ∈ X has a unique successor state succ(x). For technical systems, a deterministic behavior is often crucial in order to guarantee the reliability of the performed processes. In addition, also some biological systems are deterministic, as stimulating them in a certain way triggers always the same response (see e.g. the light-induced sporulation of Physarum polycephalum plasmodia or the phototaxis of halobacterial cells described in [START_REF] Marwan | The sequence of regulatory events in the sporulation control network of physarum polycephalum analysed by time-resolved somatic complementation of mutants[END_REF][START_REF] Marwan | Theory of time-resolved somatic complementation and its use for the analysis of the sporulation control network of physarum polycephalum[END_REF][START_REF] Marwan | Reconstructing the regulatory network controlling commitment and sporulation in physarum polycephalum based on hierarchical Petri net modeling and simulation[END_REF]). Petri nets, as originally defined, can be used to model such systems only in some trivial cases.

A compact encoding for deterministic systems. Our aim is to overcome the above mentioned difficulties by presenting a way to model deterministic systems from a global point of view (independent from a particular initial state), and to predict the systems behavior for all possible system states (whithout generating explicitely the state digraph). For that, we define a successor function succ : X → X which returns succ(x) for every x ∈ X . An explicit encoding of succ, for instance pointwise, is about of the same size as the state digraph G, and hence at least exponential in the size of G. Here we propose a more compact way of representing the dynamics of a deterministic system, by encoding the global dynamic behavior of the system through a local selection criterion that chooses among all currently enabled transitions the one which switches to the successor state succ(x).

In the next section, we formally provide all definitions and concepts needed for Petri nets as models for deterministic systems. Our model relies on the defi-nition of a priority relation between conflicting transitions, which is encoded in a compact manner by orienting the edges of a transition conflict graph. This is subject of Section 3, where the transition conflict graph is introduced together with suitable orientations of its edges in order to impose priorities among transitions as a selection criterion. This leads to a compact encoding of both a successor and a predecessor oracle. We also provide a characterization of the deterministic systems that can be encoded by our model. The issue of recognizing and characterizing such suitable orientations of the transition conflict graph is addressed in Section 4, while Section 5 is devoted to the problem of finding such orientations. We finally summarize all proposed concepts and their benefits and discuss some further implications and generalizations of the studied approach.

Petri nets with a deterministic behavior

In this section, we will formally provide all definitions and concepts needed for Petri nets as models for systems with a deterministic behavior.

Recall that a network G = (P, T, A, w) is used to encode the structure of the underlying system, where the set P of places represents the system's components, the set T of transitions stands for their interactions, and the weighted directed arcs (p, t) or (t, p) ∈ A exclusively connect places and transitions. A network G = (P, T, A, w) can also be represented by its incidence matrix M := (m pt ) ∈ Z P ×T where each row corresponds to a place p ∈ P and each column to a transition t ∈ T . We have

m pt :=    -w pt if p ∈ P -(t), +w tp if p ∈ P + (t), 0 otherwise,
where P -(t) := {p ∈ P : (p, t) ∈ A} , denotes the set of pre-places of t ∈ T and P + (t) := {p ∈ P : (t, p) ∈ A} the set of its post-places. Some places B ⊆ P may have bounded capacities, which are given by the positive integral vector u ∈ Z B + . Each place p ∈ P can be marked with an integral number x p of (at most u p ) tokens, and any marking defines a state of the system that can be represented as an integral nonnegative vector x ∈ Z P + . The potential state space of a capacitated network (G, u) is the set of all theoretically possible states X := x ∈ Z P + : x p ≤ u p , ∀p ∈ B . It is at least exponential in |P | and is finite if B = P holds.

Dynamic processes are described as sequences x 1 , . . . , x k of consecutive system states 3 , where state x i+1 is obtained from x i by switching or firing a (single) transition t ∈ T . Thereby, t consumes w pt tokens from each pre-place p ∈ P -(t) and produces w tp new tokens on each post-place p ∈ P + (t). A transition t ∈ T is enabled at a state x ∈ X if switching t yields a valid successor state x + M •t ∈ X , where M •t is the column of M associated with t, and disabled otherwise. Thus, t ∈ T is enabled in x ∈ X if E1 x pw pt ≥ 0 for all p ∈ P -(t) and E2 x p + w tp ≤ u p for all p ∈ P + (t) ∩ B.

Remark 1. An extended Petri net (P, T, (A ∪ A R ∪ A I ), w) is a Petri net which has, besides the (standard) arcs in A, two additional sets of so-called controlarcs: the set of read-arcs A R ⊂ P ×T and the set of inhibitor-arcs A I ⊂ P ×T . In such a Petri net, switching of transitions is also controlled by read-and inhibitorarcs: a transition t ∈ T is enabled at x ∈ X if E1 and E2 are satisfied and it additionally holds that E3 x p ≥ w pt for all p with (p, t) ∈ A R , and E4 x p < w tp for all p with (p, t) ∈ A I .

Note that also in an extended Petri net, switching of an enabled transition t at x yields x + M •t as succesor state since control-arcs do not affect the marking.

In general, it is possible that more than one transition is enabled in a state x ∈ X ; we denote by T (x) the set of all such transitions. Conversely,

X(t) := x ∈ X : x p ≥ w pt , ∀p ∈ P -(t); x p ≤ u p -w tp , ∀p ∈ P + (t) ∩ B
denotes the set of states at which transition t is enabled.

Recall that the state digraph of a system is defined by G := (X , A) where nodes represent potential states and a node x has an outgoing arc (x, x ′ ) ∈ A if and only if x ′ = x + M •t for some t ∈ T (x), i.e., if x ′ can be obtained from x by switching a single transition. We call x ∈ X a branching state if there are at least two transitions in T (x). The existence of a branching state implies either an alternative or a concurrent behavior of the system.

An alternative behavior occurs when at least two transitions t, t ′ ∈ T (x) are in dynamic conflict, i.e., if they cannot switch simultaneously as for some place p ∈ P , we have

x p -w pt -w pt ′ < 0, or x p + w tp + w t ′ p > u p , thus, if x+M •t +M •t ′ /
∈ X holds. While animating the model, either t or t ′ has to be selected at x. In the case of concurrency, on the contrary, no two transitions from T (x) are in a dynamic conflict. All transitions in T (x) could be switched simultaneously, resulting in the valid state

x ′ = x + t∈T (x) M •t ∈ X .
In this case, G contains paths for all possible interleaving sequences between x and x ′ , corresponding to all possible permutations of the transitions in T (x).

Petri nets are an adequate model for simulating the dynamic behavior of deterministic systems, only if no branching states are present. Otherwise, a mechanism has to be specified that allows to decide "which is the right path to choose" in the state digraph. This includes in particular a way of resolving dynamic conflicts.

We call a Petri net deterministic if each state x ∈ X has a unique successor succ(x) ∈ X . The dynamic behavior of a deterministic system can be specified in the form of a successor-oracle which returns, for every state x ∈ X , the value of succ(x). Our goal is to propose a compact implementation for this oracle. Hereby, we restrict our attention to systems where the successor-oracle can be expressed via a transition selection function trans : X → T , which assigns to every state x ∈ X a unique transition trans(x) ∈ T (x) that must be switched in order to reach state succ(x). Not all deterministic systems can be modeled in this way, see the discussion in Section 6, and even if it is possible, an explicit (i.e., pointwise) encoding of trans is extensive as it requires an amount of space proportional to the size of the state digraph G, which, as pointed out in the previous section, is at least exponential in the number of places of the network.

In [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF], it was proposed to use priorities between the transitions of the network as additional activation rules to determine which transition from T (x) has to be selected as trans(x) in order to reach succ(x). Our contribution consists in providing a compact scheme for encoding trans based on such priorities.

Remark 2. The priority relations proposed in [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF] shall reflect the relative reaction rates of the (chemical) reactions represented by the transitions of the network with the idea that faster reactions have higher priorities and are taken. On the model side, priorities can be seen as a discrete extreme case of firing rates of transitions defined by probability distributions, where exactly one transition in T (x) (namely, the highest-priority transition trans(x)) has probability 1, and all other transitions in T (x) have probability 0.

As we show in the next section, if a deterministic system S = (G, u, succ) satisfies a quite natural consistency condition, then there exists a digraph D := (T, A) on the set of transitions with the following properties:

for every x ∈ X , the set T (x) induces a subgraph having a unique sink t(x) -and t(x) = trans(x) is the required transition to switch from x to succ(x).

Observe that this graph has a size of O(|T |

2 ), which is polynomial in the size of G. Indeed, the arcs of D can be interpreted as priority relations between pairs of transitions, with trans(x) being the transition with highest priority among all transitions in T (x).

Encoding valid priority relations

As observed in the previous section, one key issue for modeling the dynamic behavior of a deterministic system is the specification of a mechanism for the (unambiguous) resolution of dynamic conflicts between enabled transitions.

Definition 1. Given a capacitated network G = (P, T, A, w) with u ∈ Z B + , its transition conflict graph is an undirected graph K (G,u) = (T, E) having as nodes the transitions from G, where two transitions t, t ′ are joined by an edge if and only if there exists at least one state where both are enabled, i.e.,

tt ′ ∈ E ⇔ X(t) ∩ X(t ′ ) = ∅.
As long as there is no risk of confusion, we will simply write K instead of K (G,u) . It follows straightforwardly from this definition that, for every state x ∈ X , the set T (x) of enabled transitions induces a clique in K, i.e., a set of mutually adjacent nodes. Remark 3. The converse is not necessarily true, as it is shown in [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF]. However, as the sets X(t) are boxes, it is straightforward to prove that at least the inclusionwise maximal cliques in K are associated with states of the system.

The transition conflict graph K can be constructed in O(|P | |T |

2 ) time using a straightforward algorithm to check for box intersections X(t)∩X(t ′ ). The next lemma from [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF] provides a more efficient way of its computation.

Lemma 1. Consider a capacitated network (G, u), with G = (P, T, A, w), u ∈ Z B + and X(t) = ∅ ∀t ∈ T . Then t, t ′ ∈ T are in conflict if and only if

w pt ≤ u p -w t ′ p ∀p ∈ P -(t) ∩ P + (t ′ ) ∩ B and w pt ′ ≤ u p -w tp ∀p ∈ P -(t ′ ) ∩ P + (t) ∩ B holds.
Observe that, in the particular case where we have capacities u = 1l, it follows as a corollary from the last lemma that two transitions t, t ′ ∈ T are in conflict if and only if

P -(t) ∩ P + (t ′ ) ∩ B = ∅ and P -(t ′ ) ∩ P + (t) ∩ B = ∅. (1)
The following example illustrates the previous results.

Example 1. Consider the capacitated network (G, 1l), with G = (P ∪ T, A, 1l), from Figure 1(a). Checking the pre-and post-places for all transitions in T yields:

t i P -(t i ) P + (t i ) t 1 {2} {1} t 2 {2} {3} t 3 {2} {5} t 4 {5} {1, 4} t 5 {2, 5} {3}
According to [START_REF] Acharya | Hypergraphs with cyclomatic number zero, triangulated hypergraphs and an inequality[END_REF], all pairs of transitions are in conflict, except (t 3 , t 4 ) and (t 3 , t 5 ), and we obtain the transition conflict graph shown in Figure 1(b).

As stated in the introduction, our main purpose is to encode the dynamics of a given deterministic system S = (G, u, trans) in a compact way, by introducing enough priority relations among transitions, as to be able to determine trans(x) for every x ∈ X . We have observed that the set of enabled transitions at each state corresponds to a clique in the transition conflict graph K, and hence K is a plausible candidate for a framework where these priorities could be embedded. This idea motivates the following definition. As for the unoriented transition conflict graph, we will write in the following D instead of D (G,u) whenever there is no risk of confusion. Observe that the existence of a valid orientation implicitly imposes a further requirement on the nature of a dynamic system. Namely, if two states x, x * ∈ X have the same set T (x) = T (x * ) of enabled transitions, then both induce the same subgraph of D and, therefore, trans(x) = trans(x * ) must hold. Moreover, if a transition t is enabled at two states x, x ′ ∈ X and t is the highest-priority transition at x, then either t is also the highest-priority transition at x ′ or trans(x ′ ) ∈ T (x). The next result from [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF] shows that this condition is also sufficient for the existence of a valid orientation. Theorem 1. A system S = (G, u, trans) has a valid orientation if and only if the following consistency condition holds for any pair of states x and x ′ : if trans(x) ∈ T (x) ∩ T (x ′ ) then either trans(x ′ ) = trans(x) or trans(x ′ ) ∈ T (x ′ ) \ T (x).

As illustrated in Algorithm 1, a valid orientation completely encodes the dynamic behavior of a deterministic system, since it can be used to obtain an implicit implementation of the successor-oracle. Given a state x ∈ X , all we need to do in order to find its successor is to determine the highest-priority transition trans(x) at x. This can be accomplished by searching for the unique sink in the subgraph of D induced by the set T (x) of enabled transitions. (If no transitions are enabled at x, the algorithm just returns the same current state x as successor.)

A predecessor of x is a state y ∈ X with succ(y) = x. For that, we must have x = y + M •trans(y) . Since there are at most |T | candidates for the transition trans(y), it follows that the set pred(x) of all possible predecessors of x has cardinality not larger than |T | and can be constructed calling the successor oracle at most |T | times, as shown in Algorithm 2. Here, first a set cand(x) of Algorithm 2: An implementation for a predecessor-oracle.

Input: (G, u, D), x ∈ X Output: succ(x) 3: Construct the set T (x) of enabled transitions if T (x) = ∅
Computing successors and sets of predecessors is a key operation within simulation algorithms to study the dynamic behavior of a system and in particular to address the different questions described in the previous section. To the best of our knowledge, currently no solution algorithm for these problems is known, which does not rely on storing explicit descriptions of the state digraph or some equivalent structure to compute succ(x) at every state x, which strongly limits the size of the networks that can be considered, due to the high memory requirements. Moreover, in certain application areas such as systems biology, the explicit values of succ(x) can only be determined by carrying out expensive and time-consuming wet lab experiments. Having, however, a valid orientation it is possible to determine or predict succ(x) for each state x ∈ X .

Recognizing and characterizing valid orientations

Another issue of interest concerns the recognition of valid orientations: Given a capacitated network (G, u), and an orientation D of the edges in the transition conflict graph, determine whether D induces a valid dynamic behavior on G, in the sense that for every state x ∈ X , the corresponding clique in D has a unique sink. Observe that a clique cannot have more than one sink, and that every clique without a sink contains a directed cycle. Hence, if D is acyclic then every clique of the graph has a unique sink, and we immediately obtain:

Observation 1 Every acyclic orientation of K is valid.

On the other hand, the next example shows that there are deterministic systems for which the valid orientation encoding the dynamic behavior contains directed cycles.

Example 2. Figure 2 depicts a network (G, 1l) with w = 1l together with a valid orientation D of the transition conflict graph that contains a directed cycle C = (t 1 , t 2 , t 3 ). Table 1 lists all branching states of the system and the corresponding sets of enabled transitions. It is straightforward to check that each of these sets induces a clique in D with a unique sink t(x). A capacitated network and a valid orientation for its transition conflict graph which contains a directed cycle C = (t1, t2, t3). All arc weights and capacities of the places are assumed to be equal to one.

Table 1. All branching states of the system from Figure 2.

x1 x2 x3 x4 T (x) t(x) 1 1 0 0 {t1, t2} t2 0 1 1 0 {t2, t3} t3 1 0 1 0 {t1, t3} t1 1 1 1 0 {t1, t2, t3, t4} t4
The fact that one has to check, for each clique Q in K, if there is a corresponding state x ∈ X with T (x) = Q makes the recognition of valid orientations hard in general, as there might be up to 2 |T | cliques. In the following we describe a special class of orientations for which this recognition problem can be solved efficiently.

In [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF], it is shown that two different dynamic systems might share the same transition conflict graph. This motivated the definition of the following equivalence relation between capacitated networks

(G, u) ∼ K (G ′ , u ′ ) ⇔ K (G,u) ∼ = K (G ′ ,u ′ ) ,
where ∼ = stands for graph isomorphism. An orientation is strongly valid if it is valid for all networks of some equivalence class of ∼ K . Acyclic orientations are one specific example of strongly valid orientations. In general, any orientation where every clique has a unique sink is (trivially) strongly valid. Moreover, the converse is also true, as it follows from a result in [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF] that each equivalence class contains a network with the property that every clique in K is associated to a state. This fact makes strongly valid orientations easy to recognize.

Theorem 2. An orientation D of the transition conflict graph of a capacitated network (G, u) is strongly valid if and only if it does not contain any directed cycle of length 3.

In this context, one is tempted to wonder whether it is possible to gain more insights on (strongly) valid orientations by exploring structural properties of K. In [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF], it is shown that for any undirected graph H, there is a network G having H as its transition conflict graph. Thus, in general, neither K nor D can admit particular graph-theoretical properties. Studying the problem however from a hypergraph-theoretical point of view as done in [START_REF] Torres | Analyzing the dynamics of deterministic systems from a hypergraph theoretical point of view[END_REF], opens the possibility of characterizing valid orientations further.

A hypergraph is a generalization of a graph in which it is possible to connect any number of nodes. Formally, a hypergraph is a pair H = (V, E) where V is a set of elements, called nodes or vertices, and E is a family of non-empty subsets of V , called hyperedges. We further use two other combinatorial structures related to hypergraphs. The dual H * of H is a hypergraph whose nodes and hyperedges are interchanged, so that the nodes are given by all E i ∈ E and there is one hyperedge V v = {E j |v ∈ E j } for each v ∈ V . The intersection graph G(H) of H is a graph whose nodes represent the hyperedges of H, and two nodes are joined by an edge if and only if the corresponding hyperedges intersect.

Recall that, by definition, for every state x ∈ X , the set T (x) of enabled transitions induces a clique in K, whereas the converse is not necessarily true (but at least the inclusion-wise maximal cliques in K are associated with states of the system), see Remark 2.

The equivalence relation on X , where x ∼ x ′ iff T (x) = T (x ′ ), partitions the state space into r ≤ 2 |T | equivalence classes X 1 , . . . , X r of states that share the same sets of enabled transitions. Let xi ∈ X i with 1 ≤ i ≤ r be (arbitrarily chosen) representative elements for each of these classes, and define the transition hypergraph H T = (T, E T ) of G to be the hypergraph on the set T of transitions, whose family E T of hyperedges is given by E T = T (x i ) : 1 ≤ i ≤ r . Thus, the size of H T is exponential in the number of transitions of the network, but it is always finite, as there are at most 2 |T | different subsets of T .

The state hypergraph of G is the dual hypergraph H X of H T and has X = x1 , . . . , xr as node set, where its family of hyperedges is determined by E X = X(t) ∩ X : t ∈ T . Directly from the definition of H X we deduce: Lemma 2. The intersection graph G(H X ) of the state hypergraph H X is exactly the transition conflict graph K.

A hypergraph H = (V, E) has the Helly property if, for any family E ′ ⊆ E of pairwise intersecting hyperedges, there exists a node v ∈ V contained in all hyperedges from E ′ . A well-known result in hypergraph theory [START_REF] Berge | A generalisation of Gilmore's theorem[END_REF] states that H has the Helly property if and only if the inclusion-wise maximal hyperedges of its dual hypergraph H * are precisely the inclusion-wise maximal cliques of the intersection graph G(H) of H [START_REF] Berge | A generalisation of Gilmore's theorem[END_REF]. This implies:

Lemma 3. H X satisfies the Helly property.

A direct consequence from Lemma 3 and the preceding observations is obtained in [START_REF] Torres | Analyzing the dynamics of deterministic systems from a hypergraph theoretical point of view[END_REF]:

Theorem 3. The inclusion-wise maximal hyperedges from E T are exactly the inclusion-wise maximal cliques of K. Thus, for every inclusion-wise maximal clique

Q there is some state xi ∈ X , 1 ≤ i ≤ r, satisfying T (x i ) = Q.
We next show that K has an interesting property, provided that H T and H X belong to certain classes of hypergraphs. A cycle of length k in a hypergraph [START_REF] Acharya | Hypergraphs with cyclomatic number zero, triangulated hypergraphs and an inequality[END_REF], a hypergraph H is acyclic if and only if H is conformal (i.e., its dual H * has the Helly property) and for every cycle of length at least 3 in H, some edge of H contains at least 3 nodes of the cycle. On the other hand, a hypergraph H * = (V * , E * ) is called arboreal if there exists a tree T * on the node set V * such that every hyperedge of H * induces a subtree in T * . Due to structural characterizations in [START_REF] Duchet | Propriété de Helly et problèmes de représentations[END_REF][START_REF] Flament | Hypergraphes arborés[END_REF][START_REF] Slater | A characterization of soft hypergraphs[END_REF], arboreal hypergraphs are dual to acyclic hypergraphs and their intersection graphs are chordal, i.e. each cycle having four or more nodes contains a chord: an edge joining two nodes that are not adjacent in the cycle. Moreover, it can be shown that arboreal hypergraphs have the Helly property.

H = (V, E) is a sequence (v 1 , E 1 , v 2 , E 2 , . . . , v k , E k , v k+1 ) such that v i ∈ V for all 1 ≤ i ≤ k + 1, E i ∈ E for all 1 ≤ i ≤ k, E i = E j if i = j, v i , v i+1 ∈ E i for all 1 ≤ i ≤ k, and v k+1 = v 1 . Due to
Combining all these properties, the following result is obtained in [START_REF] Torres | Analyzing the dynamics of deterministic systems from a hypergraph theoretical point of view[END_REF].

Theorem 4. The following assertions are equivalent:

-H T is acyclic. -H X is arboreal. -K is chordal.
Note that a chord (t, t ′ ) within a directed cycle C in D induces a new directed cycle with a smaller number of nodes, as C contains both a directed path from t to t ′ and a directed path from t ′ to t. Hence, an orientation of a chordal graph contains a directed cycle of length 3 if and only if it contains any directed cycle. This observation was used in [START_REF] Torres | Analyzing the dynamics of deterministic systems from a hypergraph theoretical point of view[END_REF] to obtain a new characterization of acyclic transition hypergraphs: Theorem 5. The transition hypergraph H T is acyclic if and only if, for any orientation D of K, the following two statements are equivalent:

1. D is strongly valid. 2. D is acyclic.

Finding valid orientations

In the previous sections, we addressed the problem of the existence of a valid orientation and how to recognize and characterize such orientations. This motivates a canonical further question, namely, once the existence of a valid orientation has been confirmed for a deterministic system, can we also find it?

As pointed out in [START_REF] Torres | Model reconstruction for discrete deterministic systems[END_REF], infering a valid orientation of a transition conflict graph shall be done by taking observations on dynamic processes in the underlying deterministic system into account. That is: Based on the knowledge of the values of succ(x) at some states x ∈ X , we aim at finding a valid orientation that encodes the global dynamic behavior of the system since succ(x) can be determined with the help of this orientation for all states x ∈ X .

In the following we consider a deterministic system S = (G, u, trans) that fulfills the consistency condition from Theorem 1 and hence trans can be encoded as a valid orientation D of the transition conflict graph. Given as input the capacitated network (G, u) and an oracle for returning the value of trans(x) at any state x ∈ X , we want to determine D by calling the oracle as few times as possible since in practice, a call to the oracle stands for the execution of a (probably expensive and time-consuming) experiment.

We call a set X ′ ⊆ X of states a valid test set if the information about the corresponding highest-priority transitions {trans(x) : x ∈ X ′ } suffices for inferring the direction of all arcs in D. Consequently, we are interested in the following problem, formulated in [START_REF] Torres | Model reconstruction for discrete deterministic systems[END_REF].

Definition 3 (Minimum Valid Test Set Problem (MVTP)). Given a deterministic system S together with an oracle for returning highest-priority transitions, find a valid test set of minimum cardinality.

The meaning of inferring an orientation deserves further explanation. Let us denote by partial orientation a (mixed) graph D ′ := (T, A ′ , E ′ ) obtained by fixing the direction for some edges of K, with A ′ being the set of the corresponding oriented arcs, and E ′ the set of the remaining unoriented edges. A partial orientation is extendible if it is possible to choose directions for all unoriented edges in such a way that a valid orientation is obtained. Given an extendible partial orientation D ′ := (T, A ′ , E ′ ), a yet unoriented edge tt ′ ∈ E ′ is said to be inferable as (t, t ′ ) if the partial orientation D′ := (T, A ′ ∪{(t ′ , t)}, E ′ \{tt ′ }) is not extendible. Moreover, D ′ is sufficient for inferring a valid orientation D := (T, A) if all edges in E ′ are inferable as the corresponding arcs in A.

Example 3. Figure 3 illustrates these concepts. The partial orientation depicted in (a) is not extendible, as choosing any direction for edge t 2 t 3 produces one inclusionwise maximal clique without sink. In contrast, any direction chosen for this edge in (b) leads to a valid orientation, so t 2 t 3 is not inferable in the second example. A sufficient partial orientation is shown in (c): the two unoriented edges t 2 t 3 and t 3 t 4 must be oriented as (t 3 , t 2 ) and (t 3 , t 4 ). Orienting any of them in the opposite direction leads to a non-extendible partial orientation.

This shows that the optimal solution of MVTP may depend on the underlying valid (complete) orientation D, and not on the transition conflict graph alone. In general, recognizing if a partial orientation is extendible, or if an unoriented edge is inferable constitutes a difficult task, due to the lack of a characterization of valid orientations from a graph theoretical point of view. In this section we consider the particular case when D is acyclic. As mentioned earlier, acyclic orientations are always (strongly) valid and the only strongly valid orientations for deterministic dynamic systems with acyclic transition hypergraph H T (see Theorem 5). Trivially, if D is acyclic then any partial orientation cannot contain a directed cycle. On the other hand, in [START_REF] Torres | Model reconstruction for discrete deterministic systems[END_REF] it is proved the following: Lemma 4. Any acyclic partial orientation is extendible.

Recall from Theorem 2 that an orientation is strongly valid if and only if it does not contain a directed cycle of length three. Hence, for any extendible partial orientation

D ′ := (T, A ′ , E ′ ), if (t, t ′ ), (t ′ , t ′′ ) ∈ A ′ and tt ′′ ∈ E ′ then tt ′′ is inferable as (t, t ′′ ).
It follows from the previous lemma that an edge tt ′ ∈ E ′ in an acyclic partial orientation D ′ = (T, A ′ , E ′ ) can be inferred as (t, t ′ ) if and only if the digraph (T, A ′ ) contains a directed path from t to t ′ . As a consequence, D ′ is sufficient if for every tt ′ ∈ E ′ the digraph (T, A ′ ) contains either a directed path from t to t ′ , or a directed path from t ′ to t. We say in this case that D ′ has the path-property.

Conversely, given a (complete) orientation D = (T, A), an arc a := (t, t ′ ) ∈ A is called essential if the digraph (T, A \ {a}) does not contain a directed path from t to t ′ . Observe that the direction of a cannot be inferred in any partial orientation extendible to D. Hence, any sufficient partial orientation must contain all essential arcs from D. The next result from [START_REF] Torres | Model reconstruction for discrete deterministic systems[END_REF] shows that no further arcs are required. Theorem 6. Let D = (T, A) be a valid orientation and A * ⊆ A the set of essential arcs. The partial orientation D * := (T, A * , E * ), where E * is the set of edges from K corresponding to the arcs in A \ A * , is sufficient for inferring D.

Observe that the set A * is unique, and that it can be computed from D in O(m 2 ) time complexity, with m := |A|, for example by several runnings of a breadth-first search algorithm to determine if each arc of A is essential or not.

Determining the direction of essential arcs is specially important for reconstructing valid orientations. The following lemma from [START_REF] Torres | Model reconstruction for discrete deterministic systems[END_REF] implies that any valid test set has cardinality larger than or equal to the number of essential arcs in D.

Lemma 5. For any state x ∈ X , knowledge of the highest-priority transition from T (x) can be used to orient at most one essential arc.

As a consequence, the following result is obtained in [START_REF] Torres | Model reconstruction for discrete deterministic systems[END_REF].

Theorem 7. A valid test set X ′ ⊆ X is optimal for MVTP if and only if A(x)∩ A * = ∅ for every x ∈ X ′ , where A(x) := {(t, trans(x)) : t ∈ T (x), t = trans(x)} is the set of arcs whose directions are revealed by testing the system at x.

Note that such an optimal valid test set can be easily determined if D is known. However, in the setting of the MVTP it is not possible to devise a "winning strategy" that guarantees that each A(x) contains an essential arc, as the next example shows.

Example 4. Consider the conflict graph given in Figure 5(a). Observe that K contains three cliques of size 3 (triangles) and seven edges, and that every edge is contained in one triangle. It can be checked that for any edge e ∈ E, there exists a valid orientation where e is not essential. Hence, any winning strategy for MVTP must start by querying the oracle at a state x * ∈ X related to one of the cliques of size 3. But for any of these cliques, there is a valid orientation where A(x * ) contains no essential arc. Indeed, if T (x * ) = {t 1 , t 2 , t 3 } or T (x * ) = {t 1 , t 3 , t 4 }, choose the orientation from Figure 5(c). Otherwise, if T (x * ) = {t 1 , t 4 , t 5 }, choose the orientation from Figure 5(b). Even if it is not possible to devise a "winning strategy" that guarantees to orient an essential arc with each oracle call in general, a valid orientation can be obtained by Algorithm 3, provided that the underlying system has one state associated with each clique of the transition conflict graph K = (T, E). Observe that in this case the obtained orientation is strongly valid. remove trans(x) from Qi end while end for Algorithm 3: Inferring a strongly valid orientation.

Algorithm 3 takes as input a partition of the edges in E into a set of cliques Q := {Q 1 , . . . , Q k }. At each iteration of the outer loop, it processes a clique Q i ∈ Q. At first, the oracle is called to orient all edges incident to the unique sink node of Q i . Then this node is removed from Q i and the oracle is called again on the remaining subclique. The procedure is repeated until Q i contains only one node, which means that all its edges have been oriented. Since the inner loop is executed |Q i | -1 times, a total of k i=1 |Q i |k calls to the oracle are required to find the valid orientation D. This quantity is strictly smaller than m if |Q i | ≥ 3 holds for at least some Q i ∈ Q, since then there is at least one iteration where two edges are oriented simultaneously, and no edge is oriented more than once.

This indeed ensures:

Theorem 8. If the underlying system has one state associated with each clique of the transition conflict graph, then Algorithm 3 computes a strongly valid orientation.

Discussion

Petri nets constitute a well-established framework for modeling complex dynamic systems. It is common practice to study dynamic processes in terms of directed paths in the reachability or marking graph G(x 0 ) starting from a designated initial state x 0 . Hereby, a particular situation occurs when dynamic conflicts are present at states, in which two transitions are enabled, but switching one disables the other. In this case, model animation does not allow definite conclusions about any system properties [START_REF] Heiner | Petri nets for systems and synthetic biology[END_REF]. The reason is that the occurrence of dynamic conflicts is understood as alternative (branching) system behavior, where a decision between these alternatives is taken non-deterministically. Therefore, the classical reachability analysis has the drawbacks that it explores the studied system only from a local point of view, starting from a particular initial state x 0 ; -is only applicable for systems of a limited size since the reachability graph G(x 0 ) needs to be explicitly constructed, but grows exponentially in the size of the network; -cannot be used to study systems that exhibit a deterministic behavior.

Our aim was to overcome these difficulties by presenting a way to compactly model deterministic systems from a global point of view (independent from a particular initial state), and to predict the systems behavior for all possible system states (whithout generating explicitly the state digraph). For that, we have examined a new approach for encoding the dynamic behavior of certain deterministic discrete systems that relies on extending the familiar framework of Petri nets. Our encoding consists in a realization of the successor-oracle as a valid orientation of the edges of the transition conflict graph K, together with Algorithm 1. This encoding is compact in the sense that the amount of space required for its storage is polynomial in the size of the network. Therefore, it is well-suited for being integrated into simulation algorithms like [START_REF] Heiner | Schwarick: Snoopy -a unifying Petri net tool[END_REF] to study the dynamics of large complex deterministic systems, and to address issues such as reachability, boundedness, existence of deadlocks, and liveness, among others.

A possible interesting extension of our model concerns the study of dynamic systems where the concurrent switch of various transitions can occur. Throughout this paper we have assumed that a change from a state x ∈ X to its successor state succ(x) can always be explained by the switch of a single transition trans(x). However, there are deterministic systems where this does not hold, as shown in the following example.

Example 5. Consider a deterministic system (G, 1l, succ) with network G as depicted in Figure 5 and w = 1l. It is straightforward to check that the system has the four branching states x 0 , . . . , x 3 shown in the figure. The following table lists the sets of enabled transitions at each of these states, as well as the corresponding successor states specified by succ: j branching state x j T (x j ) succ(x j ) 0 (1, 1, 0, 0) T {t 1 , t 2 } (0, 0, 1, 1) T 1 (0, 1, 1, 0) T {t 2 , t 3 } (0, 1, 0, 1) T 2 (1, 0, 0, 1) T {t 1 , t 4 } (0, 1, 0, 0) T 3 (1, 1, 1, 0) T {t 2 , t 3 } (1, 1, 0, 1) T Observe that t 1 and t 2 have to be switched concurrently at state x 0 to reach succ(x 0 ), whereas at each of the other branching states a single transition is switched to reach the corresponding successor state, namely, t 3 at x 1 or x 4 , and t 4 at x 2 . The enabled transitions are highlighted in gray in Figure 5, while the transitions actually switched are marked in bold.

The above successor function cannot be realized with the help of a transition selection function trans due to the following reason. Considering x 0 as initial state, trans has to select one of the transitions t 1 , t 2 ∈ T (x 0 ). However, any choice leads to an intermediate state (x 1 for trans(x 0 ) = t 1 , x 2 for trans(x 0 ) = t 2 ) where the remaining transition from T (x 0 ) is still enabled but must not be selected, as both trans(x 1 ) = t 3 and trans(x 2 ) = t 4 are implied by the specification of succ. (See the reachability graph in Figure 5.) Thus, none of the potential interleaving sequences between x 0 and succ(x 0 ) can be expressed by means of single transition switches such that every switch is determined by the value of trans at the corresponding state. x 0

x 1 x 2 (0, 1, 0, 1) (0, 0, 1, 1) (0, 1, 0, 0) t1 + t2 t1 t2 t3 t4 Fig. 5. A deterministic system whose dynamic behavior cannot be modeled via a transition selection function. The enabled transitions at each state are highlighted in gray, the next transitions to be switched are shown in bold. All place capacities and arc weights are assumed to be equal to one.

One way of dealing with these systems could be through the inclusion of pseudo-nodes in the transition conflict graph, to account for the simultaneous switching of various transitions. The advantage would be that all results from the previous sections directly carry over to the extended setting. The disadvantage of such a modification is, however, the dramatic increase in the size of the transition conflict graph, as (in the worst-case) the number of required pseudo-nodes may grow exponentially with respect to |T |.

An alternative approach consists in working on a slightly different transition conflict graph, where an edge between two transitions means that they are in dynamic conflict (i.e. when switching one transition disables the other). In this case, T (x) does not longer induce a clique in K. Yet we can now define an orientation to be valid if for any state x ∈ X the set T (x) of enabled transitions induces a subgraph containing at least one sink. These sinks reveal an anti-chain of transitions with maximal priorities, which have to be switched concurrently. Theorem 1 can be generalized to this new setting in a straightforward manner, characterizing which deterministic systems admit valid orientations. The advantage of this scheme is that it is still compact with respect to the size of the network G. However, as the sets T (x) do not induce cliques in the conflict graph, many of the combinatorial properties pointed out in Section 3-5 do not hold anymore. Moreover, since all transitions that may switch concurrently are required to do so, it is again possible to construct examples of deterministic systems whose behavior cannot be modeled in this way. Hence, further research is necessary to ensure a compact encoding of a successor oracle for all deterministic systems. For a large number of such systems, however, the here presented results allow us already the use of such an oracle for the study of dynamic processes from a global point of view, independent from a particular initial state and the (complete) construction of the reachability graph.

Fig. 1 .

 1 Fig. 1. (a) A capacitated network of a dynamic system, and (b) its transition conflict graph. All place capacities and arc weights are assumed to be equal to one.

  Fig.2. A capacitated network and a valid orientation for its transition conflict graph which contains a directed cycle C = (t1, t2, t3). All arc weights and capacities of the places are assumed to be equal to one.

Fig. 3 .

 3 Fig. 3. Different types of partial orientations: (a) non-extendible; (b) extendible, but non-sufficient; and (c) sufficient

Fig. 4 .

 4 Fig. 4. A transition conflict graph (a) and two valid acyclic orientations (b)-(c). Essential arcs are marked bold.

  Algorithm 1: Implementing a successor-oracle by a valid orientation.all candidate transitions t ∈ T fulfilling y := x -M •t ∈ X is computed, then the condition t = trans(y) tested for each candidate by calling the successor oracle.

		then
		return x
	6: end if
		{Compute out-degree of transitions in the subgraph of D induced by T (x)}
		for t ∈ T (x) do
	9:	δ -(t) := |{tt ′ ∈ A : t ′ ∈ T (x)}|
		end for
		{Return successor state}
	12: t * ← t ∈ T (x) with δ -(t) = 0
		return x + M•t *

Input: (G, u, D), x ∈ X Output: pred(x) 3: {Construct set of transition candidates} cand(x) ← ˘t ∈ T : xp + wpt ≤ up, ∀p ∈ P -(t) ∩ B; xpwtp ≥ 0, ∀p ∈ P + (t) {Call successor-oracle to construct sets of predecessors} 6: pred(x) ← ∅ for t ∈ cand(x) do y ← x -M•t 9: if trans(y) = t then pred(x) ← pred(x) ∪ {y} end if 12: end for {Return set of possible predecessors} return pred(x)

Throughout this paper, we will use superindices to reference different states and subindices to specify places. Thus, x i p is the number of tokens assigned to place p at state x i .


Assisting Human Balance in Standing with a Robotic Exoskeleton

Ildar Farkhatdinov 1,2 , Julia Ebert 2,3 , Gijs van Oort 4 , Mark Vlutters 4 Edwin van Asseldonk 4 and Etienne Burdet 2,5 Abstract-This paper presents an experimental study on balance recovery control with a lower limb exoskeleton robot. Four participants were subjected to a perturbation during standing, a forward force impulse applied to their pelvis that forced them to step forward with the right leg for balance recovery. Trials with and without exoskeleton assistance to move the stepping legs thigh were conducted to investigate the influence of the exoskeletons control assistance on balancing performance and a potential adaptation. Analysis of the body kinematics and muscle activation demonstrates that robotic assistance: [START_REF] Beyl | Design and control of a lower limb exoskeleton for robotassisted gait training[END_REF] was easy to use and did not require learning, nor inhibited the healthy stepping behavior; (2) it modified the stepping leg trajectories by increasing hip and knee movement;

(3) increased reaction speed and decreased the step duration, (4) generally increased biceps femoris and rectus femoris muscle activity.

Index Terms-Prosthetics and Exoskeletons; Physically Assistive Devices

I. INTRODUCTION

L OWER limb robotic exoskeletons have been proposed for human performance enhancement and neuromotor rehabilitation [START_REF] Beyl | Design and control of a lower limb exoskeleton for robotassisted gait training[END_REF], [START_REF] Murray | An assistive control approach for a lower-limb exoskeleton to facilitate recovery of walking following stroke[END_REF], [START_REF] Bortole | The h2 robotic exoskeleton for gait rehabilitation after stroke: early findings from a clinical study[END_REF]. However, improving the safety and performance of wearable robotic systems, and the development of novel functionalities, still remains challenging research topics. Gait assistance during walking is the main application for the majority of lower limb exoskeleton robots. While some of the previous works [START_REF] Aguirre-Ollinger | Active-impedance control of a lower-limb assistive exoskeleton[END_REF], [START_REF] Wang | Actively controlled lateral gait assistance in a lower limb exoskeleton[END_REF] state that modification of human gait characteristics improves stability in walking, very few results were published on improving balance function with the help of wearable exoskeletons. Balance control in standing and walking is a crucial exoskeleton control function, which should be considered in the development and evaluation of wearable robots for posture and gait assistance [START_REF] Van Der Kooij | Towards exoskeletons with balance capacities[END_REF].

The present work describes an experimental study on robot-assisted stepping for balance recovery in case of upper body force perturbation in healthy humans. When losing balance, humans generally use a stepping strategy, which is a robust balance recovery strategy in healthy adults [START_REF] Do | Compensatory reactions in forward fall: are they initiated by stretch receptors?[END_REF], [START_REF] Peterka | Age-related changes in human posture control: motor coordination tests[END_REF], [START_REF] Thelen | Muscle activities used by young and old adults when stepping to regain balance during a forward fall[END_REF]. Currently there are no robotic exoskeletons which can support stepping for balance recovery, and it is unclear how an exoskeleton controller should be designed to act efficiently and cooperatively with its user in order to maintain stability during standing. We addressed this challenging question in more depth through the development and experimental evaluation of cooperative balance recovery control in a human-exoskeleton system. More specifically we investigated the effect of a simple stepping assistance torque impulse produced by an exoskeleton and applied to a hip joint flexion to improve balance recovery after the upperbody perturbation.

We envisioned that the exoskeleton could help stepping and thus stability recovery, because (H 1 ) the users would adapt to the assistance quickly (no learning would be required); (H 2 ) the exoskeleton could make balance recovery faster; (H 3 ) robotic assistance would help stepping thus reducing muscle activation. To test these three hypotheses we designed a simple balance recovery controller for a lower limb exoskeleton which can detect external body perturbations and provide assistance to the exoskeleton's user. Using the sophisticated LOPES III research exoskeleton [START_REF] Meuleman | Lopes iidesign and evaluation of an admittance controlled gait training robot with shadow-leg approach[END_REF], we could conduct a systematic experimental study in which participants pelvis was perturbed and balance recovery action with stepping could be compared with and without robotic stepping assistance.

This paper presents the experimental setup, defines the stepping control strategy with the exoskeleton, describes its implementation and the experimental protocol. We analyse the role of the assistance, muscle activation and kinematic re- sponse in the balance recovery performance through stepping with the robotic exoskeleton. We examine whether assistance leads to modifications of the natural stepping behavior as it is necessary to know if the exoskeleton will not disturb the healthy behavior of a user and this test can only be performed with healthy subjects. The results suggest that the simple robot-assisted stepping does not disrupt or modify the natural behavior, and enable faster reaction to destabilisation. This is a first study towards developing robot-assisted stepping to improve the stability in frail humans.

II. EXOSKELETON BALANCE CONTROL

State of the art. Existing works on augmenting balance with robotic exoskeletons have important limitations. In [START_REF] Doppmann | Towards balance recovery control for lower body exoskeleton robots with variable stiffness actuators: Spring-loaded flywheel model[END_REF], [START_REF] Ugurlu | Variable ankle stiffness improves balance control: Experiments on a bipedal exoskeleton[END_REF] a lower limb exoskeleton with variable stiffness actuators was used for balance recovery, however experiments were performed with the robot only. In [START_REF] Martelli | The effects on biomechanics of walking and balance recovery in a novel pelvis exoskeleton during zero-torque control[END_REF] the influence of passive exoskeleton mechanics on human biomechanics of walking and balancing was investigated. It was shown that a passive exoskeleton degraded the balancing performance when perturbations were applied to the exoskeleton's user. The importance of providing pelvis anterior movements in the exoskeleton to improve stability of walking was demonstrated in [START_REF] Stegall | Rehabilitation exoskeleton design: Exploring the effect of the anterior lunge degree of freedom[END_REF]. Studies [START_REF] Doppmann | Towards balance recovery control for lower body exoskeleton robots with variable stiffness actuators: Spring-loaded flywheel model[END_REF], [START_REF] Stegall | Rehabilitation exoskeleton design: Exploring the effect of the anterior lunge degree of freedom[END_REF] indicated that the exoskeleton design, specifically its kinematic structure, can significantly degrade balancing function. In [START_REF] Karavas | Humaninspired balancing assistance: Application to a knee exoskeleton[END_REF] a knee exoskeleton is used for balancing assistance based on mimicking estimated human knee joint impedance control. The experiments were conducted with one participant only and limited data was provided. A powered ankle-foot orthosis from [START_REF] Emmens | Improving the standing balance of people with spinal cord injury through the use of a powered ankle-foot orthosis[END_REF] was used to improve standing balance for two spinal cord injury patients. Recently, it was shown that a robotic exoskeleton can facilitate balance recovery after unexpected slippages during walking, by applying torque to a user's hips to assist with flexion/extension [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF]. The exoskeleton applied torques to a user's hips to assist with flexion/extension after slippage was detected.

Overall only a few balance-assisting controllers in lower limb robotic exoskeletons have been investigated with human-participants: balance recovery with one subject in [START_REF] Karavas | Humaninspired balancing assistance: Application to a knee exoskeleton[END_REF] and with two subjects in [START_REF] Emmens | Improving the standing balance of people with spinal cord injury through the use of a powered ankle-foot orthosis[END_REF]; influences on balance during walking with passive exoskeletons in [START_REF] Martelli | The effects on biomechanics of walking and balance recovery in a novel pelvis exoskeleton during zero-torque control[END_REF], [START_REF] Stegall | Rehabilitation exoskeleton design: Exploring the effect of the anterior lunge degree of freedom[END_REF]. Most importantly, these studies did not consider human's active behavior in balancing with the exoskeleton [START_REF] Doppmann | Towards balance recovery control for lower body exoskeleton robots with variable stiffness actuators: Spring-loaded flywheel model[END_REF], [START_REF] Ugurlu | Variable ankle stiffness improves balance control: Experiments on a bipedal exoskeleton[END_REF]. The study on exoskeleton-assisted balance recovery after slippage reported in [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF] considered the biomechanical responses of the participants but did not analyse the related muscle activation.

Proposed balance assistance. We consider a lower limb robotic exoskeleton attached to its user at the pelvis and the legs (Fig. 1a). The general scenario considered is balance recovery from external perturbation applied at the pelvis level. In such situations, a stepping balance recovery strategy is employed depending on the magnitude of the pelvis perturbation. Direction and stepping points will depend on the direction of the perturbation, resulting in stepping with left or right leg. This stepping balance recovery action will also depend on actual human-exoskeleton posture. We propose to implement an exoskeleton balance assistance controller that will take into account the above mentioned and will assist the exoskeleton user with stepping for balance recovery once the perturbation is detected.

In the experimental study during certain trials, an assistance torque was applied after a pelvis perturbation was detected, to assist with balance recovery. The goal of the assistance was to apply external force supporting natural behavior in stepping required for balance recovery (hip flexion of the stepping leg). Because balance recovery is rapid, it is likely that the body uses simple and robust muscular control to regain balance. As such, simple torques were selected for assistance, with a filter applied to prevent rapid accelerations, which would be both unnatural and unsafe.

Perturbations were detected by pelvis anterior-posterior acceleration, a p , and jerk, ȧp , at time t k , crossing a threshold of a lim =2.5 m/s 2 :

wait for time t k : a p (t k ) + ∆ p ȧp (t k ) > a lim , (1)
τ • = γ(a p (t k ) + ∆ p ȧp (t k )), (2)
where ∆ p =50 ms is acceleration prediction time interval, τ • is the magnitude of assistance torque, γ = 10 Ns 2 is a constant scaling coefficient. Once the pelvis perturbation was detected, assistance torque, τ • , was provided after a delay of 55 ms in the form of a 200 ms hip flexion torque with a 5 ms low-pass filter to the leg performing a stepping action (See Fig. 1b) for a recorded pelvis perturbation and hip assistance). The assistance design parameters (a lim , ∆ p , γ) were set in pilot testing trials with several subjects such that the torques occurred while the leg was in the air and participants had no complaints about interference from the assistance. Other studies on walking assistance with exoskeletons also used impulse-like assistive torque patterns which, however, were adjusted for each human-subject [START_REF] Murray | An assistive control approach for a lower-limb exoskeleton to facilitate recovery of walking following stroke[END_REF], [START_REF] Ding | Human-in-theloop optimization of hip assistance with a soft exosuit during walking[END_REF].

III. EXPERIMENT LOPES III robotic exoskeleton. The LOPES III lower limb robotic exoskeleton used in the experiments [START_REF] Meuleman | Lopes iidesign and evaluation of an admittance controlled gait training robot with shadow-leg approach[END_REF] (Fig. 1a) is composed of leg and pelvis attachments with horizontal push/pull rods connected to robotic shadow legs, an actuation mechanism with electric motors and controllers, and a treadmill. The shadow legs can be actuated in shank flexion/extension, thigh flexion/extension and abduction/adduction. The actuation mechanism enables pelvis control in forward/backward and mediolateral directions. Additionally, LOPES III is equipped with adjustable body weight support for a user. The exoskeleton's passive ankle joints are connected to the leg guidance bars with a series of revolute joints with axes intersecting in the ankle joint. The distances between hip, knee and ankle joints are adjustable for each user to enable natural and comfortable movements. The exoskeleton is operated in admittance control [START_REF] Van Der Linde | The hapticmaster, a new high-performance haptic interface[END_REF] at 1 kHz based on the measured human-exoskeleton interaction forces which are converted into desired exoskeleton joint positions to enable haptic transparency and rendering effects.

During the experiments LOPES actuators were operated in haptically transparent mode with the pelvis anterior-posterior active degree-of-freedom (DoF) used for force perturbations and right thigh movements (hip joint) used for balance recovery assistance.

Protocol and participants. Four healthy adult participants (1 female, 3 males; age 25-35) took part in the study which was conducted at the University of Twente, Netherlands, and was approved by the institutional ethical committee. In the beginning of the experiment the participants stood upright with their feet together, as shown in Fig. 1a. All participants were right-handed and right-footed, i.e. they preferred to use their right leg for stepping. To ensure that this was the case in all trials, we asked the participants to shift their weight toward the left leg.

A 200 ms forward perturbation (step filtered with a lowpass filter with 50 ms time constant) (Fig. 1b) was applied randomly every 4 to 10 s (uniform distribution), requiring subjects to take a step with the right leg to regain stability. The magnitude of the perturbation was approximately 35% of body weight (test trials demonstrated that such perturbations require stepping action for balance recovery). This was determined by initialisation trials preceding the experimental procedure to cause loss of postural stability without causing discomfort. The participants were instructed to hold the harness and not use their arms for balance recovery. After each step, subjects returned to an upright stance and stood straight for the next perturbation.

The experiment was composed of three phases: 1) baseline: balance recovery without robotic assistance, 2) assistance: balance recovery with robotic assistance (split into early and late assistance), 3) catch trials: balance recovery without assistance interspersed with assistance trials. Before the experiment the participants familiarised with the system, which took around 2-3 minutes per participant. The goal of the baseline experimental stage was to record balance recovery behavior after pelvis perturbations when the exoskeleton was haptically transparent and no assistance was used. In total 30 pelvis perturbations were introduced in the baseline phase. The baseline phase was followed by an assistance phase of 60 trials during which robotic assistance was applied to support stepping and balance. Six catch trials with robotic assistance removed were randomly introduced during last 30 trials of the assistance phase. The catch trials were used to investigate whether there was any learning in the assistance phase. The overall experiment took around 15-17 minutes per participant.

Data processing. The experimental data recorded at 1 kHz included joint angles and participant-exoskeleton interaction torques for hip and knee flexion/extension; pelvis position and velocity in horizontal plane, and centre of pressure (CoP) measured from the treadmill. Interaction torques were estimated by the exoskeleton's low level real time controller based on the measured human-exoskeleton interaction forces and the segments' lengths [START_REF] Meuleman | Lopes iidesign and evaluation of an admittance controlled gait training robot with shadow-leg approach[END_REF].

The stepping duration in balance recovery was calculated using the CoP. A threshold was set at 20% of the maximum lateral centre of pressure velocity in the full duration of the experiment. The end of each recovery step was defined as the time point after the perturbation at which the centre of pressure forward velocity crossed this threshold.

The forward step length was computed as the foot position w.r.t. the initial foot position before perturbation averaged over the 200 ms following the heel contact. Pelvis position along the anterior-posterior axis was set to zero at the onset of each perturbation, and the right foot x position was calculated using the recorded right hip flexion (θ HF ) and knee flexion (θ KF ) angles and the estimated leg segment lengths:

x foot = x pelvis + l thigh sin θ HF + l shank sin θ KF .
Electromyography (EMG) recordings of muscles on the right leg associated with the hip flexion/extension (GM -Gluteus Maximus, BF-Biceps Femoris, RF -Rectus Femoris, and gastrocnemius) were obtained at 1 kHz and saved during balance recovery with Delsys Trigno wireless EMG system. The rectus femoris muscle is involved in hip flexion, while GM and BF muscles contribute to hip extension. RF and BF are biarticular muscles that have been shown to have non-intuitive function depending on configuration [START_REF] Arnold | Muscular contributions to hip and knee extension during the single limb stance phase of normal gait: a framework for investigating the causes of crouch gait[END_REF], [START_REF] Hernández | In vivo measurement of dynamic rectus femoris function at postures representative of early swing phase[END_REF]. Additionally, the gastrocnemius muscle activation was recorded to observe any influence of the assistance controller to ankle-foot plantar flexion and knee flexion.

Raw EMG signals were de-meaned, high-pass filtered at 50 Hz, rectified, and low-pass filtered at 10 Hz (4th order Butterworth). Signals were normalised by subject, such that the highest peak value was 100% for each leg over all trials. This allowed for comparison between subjects.

Within-subjects and between-subjects statistics were similarly computed for the standing experiment, with a oneway ANOVA comparing baseline, early assistance, late assistance, and catch trials. Because of the smaller number of perturbations in each condition, early assistance consisted of the first 15 trials of the condition, while baseline and late assistance were the last 15 trials of their respective conditions.

Outliers were removed prior to analysis, based on the right hip flexion/extension data within each experimental state. Specific trials with hip trajectories markedly different from the mean over all trials were considered as outliers and eliminated. This was detected from the root-mean squared error (RMSE) relative to the overall mean, with a threshold of two times the average RSME. Furthermore, trials in which the peaks of at least one of the EMG recordings exceeded the double standard deviation margins around the mean recorded values were also eliminated from the analysis. This was done to exclude the trials with abstruse EMG recordings which could be caused by body movement artifacts. It was verified that no more than 10% of trials per experimental stage were removed for each participant.

IV. RESULTS

We analysed the right leg movements, muscle activation, pelvis and centre of pressure kinematics in stepping during balance recovery for each participant per experimental phase. The results per participant and experimental phase are presented as follows: right leg kinematics in Fig. 2, pelvis position, velocity and centre of pressure in Fig. 3, right leg muscles' activation in Fig. 4. In these figures the recordings are aligned in time, such that the time instant t=0 corresponds to the moment when a forward force perturbation was applied. We have also computed the within-participant and the between-participant statistical significance in the data, as shown in Table I and Fig. 5, respectively.

Hip flexion. The first row of Fig. 2 shows the mean (bold lines) and standard deviation margins (in shadow) for the right hip flexion recordings in four experimental stages (shown in four colours) for each participant (columns S1-S4).

Once a pelvis perturbation was applied a participant had to flex his/her right hip in order to move the right foot forward and recover balance with stepping. Hence, in all participants we see an increase of hip flexion during approximately the first 0.5 s. Stepping was complete at approximately 0.7 s, when the right foot was placed on the ground and hip angle was static. For all participants a clear difference in trajectories between baseline and assistance is observed. The recordings in catch trials are close to the baseline trajectories. Assistance torque applied to the hip during the assistance trials increased the hip flexion magnitude compared to the baseline cases. Hip extension movement which is observed during first 200-300 ms after the perturbation in the baseline trials is not present in early and late assistance trials. Hip flexion in catch trials is similar to the baseline trials.

Within participant analysis showed that for all participants the mean hip flexion with assistance was significantly larger than in baseline or catch trials (Table I). For all participants, no statistical difference was observed between baseline and catch trials. Between participant analysis showed larger hip flexion in early and late assistance than in baseline trials, which was statistically significant (p <0.05), as shown in Fig. 5a. There was no significant difference between baseline and catch trials. There was also no significant difference in hip flexion between early and late assistance trials in all participants.

Knee flexion Right knee flexion recordings for each participant are shown in the second row of Fig. 2. Similar to hip movements, we observe knee flexion during 0.5 s after the perturbation, after which it extends to approximately 0.3-0.4 rad when the stepping is complete (even though there was no direct exoskeleton torque assistance applied at the knee level). Trials with assistance exhibited larger knee angular displacements than in the baseline and the catch stages of the experiment. Knee flexion in the catch and the baseline trials do not differ from each other significantly.

Similar to hip flexion, within participant analysis showed that for all participants the mean knee flexion was significantly increased in assistance trials compared to baseline and catch trials (Table I). For three subjects there was no difference in knee flexion in baseline and catch trials. Results of between participant analysis of knee flexion are shown in Fig. 5b. It showed that knee flexion was increased significantly in all assistance trials (p <0.05).

Foot placement, step length and duration. Calculated trajectories for right foot position in the forward direction are shown in the last row of Fig. 2. During the assistance trials, the right foot was placed further away in conjunction with increased hip flexion and knee extension when compared to baseline and catch trials, which is clearly observed for the participants S1, S2 and S4. Within-participant analysis showed that the step length was increased in the early assistance trials compared to the baseline recordings for these three participants. For all participants, there was no significant difference between the baseline and catch trials (See Table I). Between participant analysis revealed no significant differences in step length between experimental stages (p = 0.15, F = 2.14).

Within participant analysis showed that step duration was longer in catch trials than in early and late assistance for all participants (Table I). There was no significant difference in step duration between early and late assistance trials. Three participants had reduced step duration in early assistance compared to baseline trials (p < 0.05). Between-participant analysis showed that step duration was significantly increased in catch trials compared to assistance trials (p < 0.05), as presented in Fig. 5.

Pelvis movement. Pelvis forward movement trajectories, velocity and CoP lateral displacement are shown in Fig. 3. The pelvis moved forward once the force perturbation was applied until the stepping for balance recovery was complete, with the body slowing and stopping at 15-30 cm distance from the origin. As seen from the first row in Fig. 3, the recordings of pelvis position during stepping are characterised with small standard deviation for participants S1, S3 and S4. For the same participants, the pelvis movement forward in the assistance trials was slowed down from around 200 ms when right hip assistance torque was applied. This can be clearly seen in the second row of Fig. 3: the pelvis velocity is significantly lower in the early and late assistance cases compared to baseline and catch trials during the perturbation and assistance actions (approx. first 400 ms), for all subjects. Probably, slower pelvis movements were the result of the reaction torques caused by fast hip flexion movements. We analysed the statistical significance for the pelvis velocity at time t=200 ms when the pelvis perturbation was complete but the hip flexion assistance was still active. Between participant ANOVA analysis revealed significant differences in pelvis velocity between experimental stages for all participants (p < 0.001, F = 48.37, Fig. 5d). As shown in Table I for the within-participant analysis of all subjects, pelvis velocity was decreased at the end of the perturbation as a result of stepping assistance (p < 0.001).

Stability. One of the ways to analyse stability of recovery relevant to our experiment is to take into account the distance between the stepping foot and the centre of mass (CoM) after the stepping is complete. Such measure allows quantitative comparison of postural stability in assisted and non-assisted trials and is a simplified version of the stability margin introduced in [START_REF] Hof | The condition for dynamic stability[END_REF]. One will prevent falling over if stepping foot is placed more anteriorly than the centre of mass. In our case the average distance in cm between the pelvis position (assumed to be close to CoM) and the right foot after the stepping was approximately 19±5, 27±6, 25±7 and 20±7 (mean±sd) for baseline, early and late assistance, and catch trials, respectively. This result demonstrates that the stability of standing was improved during exoskeletonassisted trials and it was statistically significant for three subjects as shown in Table I.

Lateral CoP trajectories with markers indicating the end of stepping are shown in the last row of Fig. 3. Once the perturbation was applied and the right leg was lifted from the ground for balance recovery, the CoP quickly deviated to the left until the stepping was complete. Once stable double stance was achieved, the CoP moved to the right as the overall CoM of the body was deviated to the right as well. For all participants except for S2, it can be clearly seen that stepping was complete faster compared to baseline and catch trials (see the third row of Fig. 3). Also, the CoP lateral deviation to the left in the assistance trials was slightly smaller for participants S1, S3 and S4.

Muscle activity. The normalised muscle activation of the right leg during stepping is presented in Fig. 4. There was no difference in integrated BF EMG (first row of Fig. 4) between conditions in the between-participants ANOVA (p = 0.55, F = 0.74). However, within-participant analysis showed that three subjects had increased BF muscle contraction from baseline to late assistance, and for all participants there was no significant difference between the muscle activation in baseline and catch trials.

The second row of Fig. 4 shows activation of RF muscle. There were no significant between-participant effects of experimental stage on integrated RF contraction (p = 0.11, F = 2.49). However, within-participant analysis showed that three participants had increased RF contraction in assistance trials compared to baseline and catch trials; for all participants there was no difference of activation in baseline and catch trials; three participants showed an increase from early to late assistance. The last row of Fig. 4 shows activation of gastrocnemius muscle. There was no main effect of experimental stage on gastrocnemius contraction in the between-subject analysis.

V. DISCUSSION

Previous studies [START_REF] Martelli | The effects on biomechanics of walking and balance recovery in a novel pelvis exoskeleton during zero-torque control[END_REF], [START_REF] Karavas | Humaninspired balancing assistance: Application to a knee exoskeleton[END_REF], [START_REF] Stegall | Rehabilitation exoskeleton design: Exploring the effect of the anterior lunge degree of freedom[END_REF], [START_REF] Emmens | Improving the standing balance of people with spinal cord injury through the use of a powered ankle-foot orthosis[END_REF] have investigated some aspects of balance with a robotic exoskeleton using testing with a single subject and the study [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF] investigated assisted balance recovery following slippage in walking with eight elderly participants. In this context, this paper has presented the first study which systematically analyses balance recovery in standing through stepping with a robotic exoskeleton on four subjects. Compared with [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF], in our study in addition to kinematic responses we measured and analysed muscle activation. The results demonstrated that a simple controller can be efficiently used for assisting balance in complex physical interactions between a user and robotic exoskeleton. We could analyse important behavioral trends, although some observations are not statistically significant due to the complexity of the experimental setup used in this work and the variability of human motor commands. The results can be analyzed with respect to the three predictions H 1 -H 3 described in the Introduction.

Adaptation to assistance. First, the results showed that the participants could easily adapt to the robotic assistance, which did require learning and did not affect the natural stepping response. This is important as assistance should not alter the healthy behavior. A statistical comparison of early and late assistance trials did not reveal any differences and balance recovery performance remained same during the assisted trials. A user's neuromuscular motor control could rapidly adapt to the forces and movements produced by the robot and no motor skills learning was required. There was no statistically significant difference in balance recovery between non-assisted baseline and catch trials demonstrating that the participants were able to return to their typical balance response once robotic assistance was disabled.

Kinematic response. The experimental results also verified our second prediction (H 2 ) that the exoskeleton could speed up the stepping. Balance recovery assistance modified the stepping leg trajectories by increasing hip and knee movement and it increased the reaction speed and decreased the step duration. Similarly to [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF] the assistance resulted in a significant change of the movement kinematics. The hip flexion assistance torque resulted in greater average hip flexion during the step. Notably, this appears to be due to the hip flexion occurring earlier, rather than simply causing a larger peak flexion due to the presence of external assistance torques. This is because the assistance torque was applied 55 ms following the detection of the perturbation, as opposed to the reaction delay of up to 100-200 ms for the subjects' muscle activation which is similar to the results reported in [START_REF] Do | Compensatory reactions in forward fall: are they initiated by stretch receptors?[END_REF], [START_REF] Peterka | Age-related changes in human posture control: motor coordination tests[END_REF], [START_REF] Thelen | Muscle activities used by young and old adults when stepping to regain balance during a forward fall[END_REF], [START_REF] Vlutters | Lower extremity joint-level responses to pelvis perturbation during human walking[END_REF]. In our case we achieved faster balance Fig. 5. Results of the between-participant statistical analysis for right leg stepping: a-c -mean kinematic parameters for all participants; d -pelvis AP velocity at the end of perturbation.

recovery by applying the assistance earlier than the subjects motor response onset times. However, as discussed later the timing of assistance should be taken into account to prevent increased muscle activation. Interestingly, a similar increase in knee flexion was observed in assistance trials even though the robotic assistance was applied only to hip movements. This indicates that it is possible to apply robotic assistance only to selected DoFs of the human body and the (rest of the) body will naturally adjust balance recovery response through neuromechanical interaction.

Postural stability was improved as a result of faster and larger joint movements because the foot placement with respect to the pelvis (CoM) was increased in assisted trials providing better support base. The observed larger step size in combination with a faster swing time assure that the CoM can be more effectively decelerated and so the perturbation counteracted. We see this as a positive result, as the study was conducted with healthy subjects who can already take appropriately sized steps to recover balance, and the assistance provided did not negatively impact this ability. Steps duration was slightly longer without assistance (catch and baseline trials) than in assisted trials, indicating that subjects adapted their behavior in anticipation of the assistance, and completing the recovery step took longer when the expected assistance was absent.

Muscle activation. The third prediction (H 3 ) was not verified, as muscle activation was increased when assistance was provided by the exoskeleton. The analysis showed that muscular contraction in RF and BF (hip flexion/extension movement) often increased as a result of assistance. However, there was no significant difference in the betweenparticipants analysis likely due to high between-subject variability. The within-subjects differences underlined the importance of selecting appropriate assistance torque magnitudes and timing parameters. Interestingly, the betweenparticipants analysis also showed a trend for reduced gastrocnemius muscle activity (ankle-foot plantar flexion movement) indicating that less ankle activity is required to push off for stepping. Even though this decrease was statistically insignificant, it demonstrates that the participants' whole body neuromuscular control was actively adapting to exoskeleton assistance forces. The GM muscle does not appear to have been significantly involved in the movement or impacted by the assistance.

Overall, the effect of assistance on muscular activation is mixed. While the GM appears to not be involved in or affected by the assistance, activation of BF and RF (both muscles in the thigh) apparently increased, and gastrocnemius muscle contraction decreased. The gastrocnemius is the only muscle that showed a reduction of contraction and is also the only muscle measured that is not responsible for hip movement. The RF and BF are antagonistic muscles [START_REF] Arnold | Muscular contributions to hip and knee extension during the single limb stance phase of normal gait: a framework for investigating the causes of crouch gait[END_REF], [START_REF] Hernández | In vivo measurement of dynamic rectus femoris function at postures representative of early swing phase[END_REF], but both showed a tendency toward increasing contraction; added assistance led to increased stiffening through co-contraction of the muscles responsible for hip flexion and extension. think that the main reason for the increased muscle activity in the assisted trials is the difference in time when assistance is applied by the exoskeleton and when the motor commands activate the hip flexion muscles as a response to the perturbation. It appeared that the robot was acting faster which led to a certain level of resistance from the users body at earlier stages of balance recovery. This issue can be addressed by carefully adjusting the assistance's timing and it is also related to the time instant when the perturbation is detected (pelvis acceleration threshold). One approach could be to adjust the assistance timing to each user with the exoskeleton support optimisation techniques that were already used to tune walking assistance [START_REF] Ding | Human-in-theloop optimization of hip assistance with a soft exosuit during walking[END_REF].

The limitations of our study include the limited number of participants and the experimental scenario which only considered forward perturbations in standing. Compared with the experiment in [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF] the exoskeleton used in the study was partially grounded (the electrical actuators of the LOPES system are attached to a rigid grounded frame), however, stiff and low-friction mechanism with high-performance admittance controller enabled us to realistically emulate a mobile wearable lower limb exoskeleton.

Adaptation for impaired users. The presented assistance method could be adapted for impaired users. In this case, the exoskeleton first should be actively supporting the impaired muscle function of the lower limbs all the time (at ankle, knee, hip and pelvis joints). At this time there are no published studies on full lower limb exoskeleton based balance assistance for impaired users. Only two studies report on partial assistance: at the foot-ankle level for people with spinal cord injury [START_REF] Emmens | Improving the standing balance of people with spinal cord injury through the use of a powered ankle-foot orthosis[END_REF] and at the hip level for elderly and transfemoral amputees [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF]. In general impairment case to enable full lower limb support in balancing the exoskeleton's controller should have or acquire knowledge of which joints should be supported during the stepping action (e.g. left or right hip). Recent applications have demonstrated that using exoskeletons to support impaired users requires the development of user-specific biomechanical modeling which can be integrated into the walking assistance controllers [START_REF] Murray | An assistive control approach for a lower-limb exoskeleton to facilitate recovery of walking following stroke[END_REF], [START_REF] Wu | An adaptive neuromuscular controller for assistive lower-limb exoskeletons: A preliminary study on subjects with spinal cord injury[END_REF], [START_REF] Huang | Modelling neuromuscular function of sci patients in balancing[END_REF].

Fig. 1 .

 1 Fig. 1. a: Participant before stepping with LOPES III exoskeleton; b: Sample single trial recorded data for balance recovery assistance.

Fig. 2 .

 2 Fig. 2. Right leg kinematic data during stepping for the four participants (S1-S4). Black vertical line in the last row corresponds to completion of stepping.

Fig. 3 .

 3 Fig. 3. Pelvis AP position, velocity and lateral centre of pressure during stepping for all participants (S1-S4).

Fig. 4 .

 4 Fig. 4. Normalised right leg muscle activity recordings during stepping for all participants (S1-S4).

ACKNOWLEDGMENT

This research was supported by the EU FP7 ICT-601003 BALANCE and ICT-611626 SYMBITRON grants. J. Ebert was also funded the U.K. Marshall Aid Commemoration Commission.