DEVS-Based Building Blocks and Architectural Patterns for Intelligent Hybrid Cyberphysical System Design (2024)

1.1. Review of DEVS Abstractions for Brain Architectures

DEVS is a system theoretic characterization of discrete event simulations based on abstraction of events and time intervals from continuous data streams [15,16,17]. Such abstractions carry information that can be efficiently employed, not only in simulation, but also in accounting for the real-world constraints that shape cognitive information processes [18,19]. An abstraction attempts to capture the essence of a complex phenomenon relative to a set of behaviors of interest to a modeler. A discrete event abstraction represents dynamic systems through two basic elements: discretely occurring events and the time intervals that separate them [1]. Discrete event models of neurons, neural processing architectures, and “fast frugal” bounded rational decision-making models [12] offer the abstractions for capturing cyber-physical cognitive systems structure and behavior. While other formalisms allow representation of space and related resources, only discrete event models offer the additional ability to explicitly and flexibly express time and its essential constraints on system behavior and structure. Discrete event models can be distinguished along at least two dimensions from traditional dynamic system models—how they treat passage of time (stepped vs. event-driven) and how they treat coordination of component elements (synchronous vs. asynchronous). Recent event-based approaches enable more realistic representation of loosely coordinated semi-autonomous processes, while traditional models such as differential equations and cellular automata tend to impose strict global coordination on such components.

Definitions for state-based realization of cognitive behaviors based on mathematical system theory and DEVS fundamentally include temporal and probabilistic characteristics of neuron system inputs, state, and outputs [1] and provide a solid system-theoretical foundation and simulation modeling framework for the high-performance computational support of such applications. Spiking neural nets (SNN), [20,21,22,23,24,25] a form of hybrid continuous discrete event abstraction, have demonstrated potential for solving complicated time-dependent pattern recognition problems because of their inclusion of temporal and dynamic behavior [3]. Realizations of SNN’s in DEVS have been shown [25,26]. Event-based simulation is inherently efficient since it concentrates processing attention on events—significant changes in states that are relatively rare in space and time—rather than continually processing every component at every time step. Exploiting asynchronous behavior and sparsity of events, activity, and fan-out that seems to characterize real brain processing, neural nets of large sizes (millions of neurons and billions of synapses) can be simulated on a desktop computer [24]. For the same reasons, DEVS can support fast and energy efficient hardware implementation [25] of spiking neural nets (SNN) and other such models. In particular, DEVS supports the abstractions underlying neural net models for which:

1.2. Functional Architecture for Hybrid Intelligent Cyberphysical Systems

Figure 1 sketches the functional layers for a hybrid (discrete event, discrete time, and continuous modeling formalisms) control architecture for intelligent cyberphysical systems built under the DEVS system-theoretic framework [1]. An instance of architecture is the detailed design model of an unmanned vehicle and its associated discrete-event and continuous variable controllers. This simulation model was developed using a unified and flexible DEVS-based toolkit for modeling and simulation of a complete functional stack to develop and validate the system. Castro et al. [28] showed that the underlying DEVS simulator is capable of managing all dynamics (discrete event, discrete time and continuous) involved in the hybrid system. Differential equations represent continuous dynamics of the aircraft on the physical layer using quantized state system (QSS) integrators. A finite state discrete event controller at the top layer links to the action implementation layer containing a coupled model of DEVS atomics planners and conventional feedback controllers in. The DEVS-based architecture achieved simulation speed-ups of up to one order of magnitude above widely employed robot middleware-based simulation setups thus enabling on-board predictive simulations.

Taking this architecture as representative of state-of-the-art DEVS-based hybrid intelligent cyberphysical system architectures, we will focus on the decision layer and review the architectural features presented in [11] in order to examine them for updating to current knowledge.

3.1. Fast Discrete Event Neuron Architectures for Decision Layer

We proceed to review the DEVS characterization of neural network models based on discrete rather than continuous abstractions. DEVS abstractions capture the many features of biological neurons that are not represented in conventional artificial neural networks and to exploit these capabilities to perform intelligent control tasks [31,32]. Of particular note is the “One-spike-per-neuron” concept that refers to information transmission from neuron to neuron by single pulses (spikes) rather than pulse trains or firing frequencies [33]. The distinguishing feature of the one-spike neural architecture is that it relies on a temporal, rather than firing rate, code for propagating information through neural processing layers. This means that an interneuron fires as soon as it has accumulated sufficient “evidence” and therefore the latency to the first spike codes the strength of this input. Single spike information pulses are thus able to traverse a multi-layered hierarchy asynchronously and as fast as the evidential support allows. “Act-as-soon-as-evidence-permits” behavior can be implemented by “order-of-arrival” neurons which have plausible real-world implementations [33]. Such processing is invariant with respect to input intensity because latencies are uniformly affected by such changes. Moreover, coding which exploits firing order of neurons is much more efficient than a firing-rate code which is based on neuron counts.

The basic concept that supports discrete event abstraction of neural behavior is strength-to-latency coding. Here the strength of the input of an evidence-gathering neuron (such as sensory neuron) is coded in the latency of its output response for downstream neurons. In other words, the greater the stimulation of an input volley (evidence) the quicker the generation of a corresponding output spike. Thus, a neuron with lots of evidentiary support will be “heard” earlier by neurons in the next processing layer than one with low or no input strength. Dispersion in such latencies sets the stage for neurons that are sensitive to the order of arrival of spikes. An input train arrives on the input lines in the order of their weights accumulates maximum activation and may cause the neuron to fire if this exceeds the threshold. Any other order of arrival will accumulate less activation and therefore, depending on the threshold level, may not generate an output spike. Thus, the neuron can discriminate among different order-of-arrivals of stimuli. This ability to distinguish between N! input patterns (where N is the number of input wires) thus supports a combinatorically more efficient information code than one based on the number of stimulated input wires rather than their order of stimulation [33].

The “one-spike-per-neuron” architecture [33,34] proposed several processing layers between input from sensors and outputs going to actuators. Sensory layer neurons react directly to incoming energy (in various modalities such as visual or infrared electromagnetic waves, sonar, etc.) These neurons perform the analog-to-latency coding just discussed. Fusion/Analysis layer neurons fuse the data collected from the various sensors into stereotyped complexes that can be further related to reactive courses of action. These neurons operate on the order-of-arrival principles discussed above. Priming of alternative candidates for behavioral course of action is also done by order-of-arrival neurons. Decision, i.e., selection from the candidates, is performed the by winner-take-all neurons. Action sequencing plays out the memorized sequence of actions associated with a selected course of action and is done by event-based control neurons.

In [11] it was hypothesized that a proposed generic neuron model could be specialized to satisfy all the requirements for behavior at each of the layers. Here we step back and examine the problem of uncovering fundamental requirements, whether implementable in a single generic neuron or not, for realizing cognitive behavior that are also biological plausible.

3.2. Fast and Frugal Heuristics: Voting Example

The “fast frugal and accurate” (FFA) perspective on real word intelligence [12,13] provides a holistic cognitive system framework that characterizes decisions that an intelligent system has to make under time pressure and limited information. FFA hypothesizes that fast and accurate heuristics can be constructed from simple building blocks that control attention to informative cues, quickly terminate search processing, and make final decisions. As an illustration of an FFA we briefly discuss an example, the “take the best” inferencing heuristic which employs only a fraction of the available knowledge and stops immediately when the first answer is found (rather than the best answer). “Take the best” does not attempt to integrate all available information into its decision. Consequently, it is non-compensatory, non-linear, and can violate transitivity, the cannon of rational choice.

As an example of FFA, we review a recent study of how people determine their votes for political candidates [14]. Recognizing that the actual amount of political information possessed by voters is small, unevenly distributed, and time pressured, the study confirmed the predictions of [14] which predicts that employing specific cognitive shortcuts can help voters make good and quick decisions, even with a lack of information. Voters appear to simplify decision making by focusing mainly on those policy positions they consider important. The study measured the congruence between a voter and candidate by the distance between their positions on the most important issues to the voter. This enables the assertion that voters’ decisions are correct if they have chosen the candidate with the highest congruence. This explains experimental results where voters are able to make correct decisions (as measured in this manner) independently of the amount of information available. The results confirm that fast and frugal heuristics may be the decision strategies that voters adopt to make quick, frugal, and correct (as measured) decisions.

“Take the best” amounts to using a lexicographical ordering of candidates based on importance of issues and matching between a candidate’s and voter’s views on the issues. In other words, the voter looks at their most important issue and compares candidates on this issue. The candidate most congruent to his views on this issue is chosen unless it is not possible to rank on this issue, in which case the same procedure is applied to the next important issue, and so on. Note that importance of issue does not depend on the candidate—so importance comes first in the lexicographical order.

If fast and frugal heuristics characterize human bounded rationality, then they ought to be implementable by discrete event neural architecture introduced earlier. Indeed, let us sketch a construction to show this to be the case. Figure 5 depicts a network of DEVS components that implements “take the best” for the voting example. First Arrival is an NE that lets the first spike to arrive through and blocks subsequent arrivals. Computation Delay is an IC between First Arrivals that delays an incoming spike by an amount specified by a parameter. As a model of cognitive behavior, the delay represents in an inverse manner the strength of the weight of the connection—the shorter the delay the earlier the spike will arrive at the target node. Thus, in Figure 5, the Computation Delays represent the respective importance of issues to the voter so that the most important issue emerges from the First Arrival en route to the downstream instance. These delays are packaged together in a Parallel Delay that is a hierarchical parallel DEVS coupled model. The most important issue continues to be evaluated in parallel for each candidate with the one most congruent with the voter’s attitudes emerging from the second First Arrival.

Figure 5 identifies potential building blocks with First Arrival and Computation Delay as primitives and Parallel Delay as a composite. We focus on First Arrival to consider its minimal realization and potential implementations. Recall that our approach to establishing that a model is a minimal realization of a given cognitive behavior, illustrated in Figure 6, is to specify the behavior as a system at the I/O behavior level. This requires us to define the behavior formally as a function mapping input segments to output segments.

Figure 7 shows how the minimal realization is derived in this case using the approach of constructing the reduced version of the monoid (semigroup with identity) representation of all DEVS segments as generalized from the case of strings introduced above. As an example, X = {a,b} and starting with the empty segment the tree grows by adding branches for segments ending with events a and b, respectively. Whenever a node is encountered with the same derivative function as one earlier encountered it can be merged with the earlier one. For a finite state function this will eventually bring a halt to the unfolding of the tree. The output function requires outputs with these respective values and that subsequent inputs do not result in outputs. A null event segment does not change the output. Thus, there are 4 different derivative functions β, β_a, β_b, and β_aa for the original requirement, β, the outputs after the input events a and b, respectively, and the blocking of subsequent input. In general, we see that n + 2 states are required for an event set X with cardinality n.

Note that the specification is deceptively simple as it hides the underlying semantics that operationalize the definition in the proper simulation infrastructure. Please refer to [1] for a detailed exposition.

Figure 8 displays a user-developed state diagram in MS4 Me [27] for this DEVS model.

To establish a hom*omorphism from this model to the minimal realization, we note that the states waitforInput and passive map to the initial and final states of the latter. The state send, is actually the phase of the state pair (send,x) where x is the event received so that it represents the storage required for the n states of X. We can easily trace the transitions of this model and of the minimal realization to check that the correspondence is preserved.

3.3. Activation as Distinct from I/O Processing

We now introduce an important capability called activation that is distinct from input/output processing. As illustrated in Figure 8, the state waitforActivate replaces the waitforInput and passive states as the starting and ending state. An Activate input sets the model to a new waitForInput state that is equivalent to the original except that it can be sent back to the initial state by a DeActivate input. The representation in DEVS is obtained essentially by adding the definitions:

δ_ext(waitForActivate,∞,e,Activate) = (waitForInput,∞)

δ_ext(waitForInput,∞,e,DeActivate) = (waitForActivate,∞)

δ_ext(send,∞,e,DeActivate) = (waitForActivate,∞)

While appearing to be a small change when represented in the state diagram, the additional capability has large consequences in the implementations to be discussed.

3.4. Variations on First Arrival

As a first example where activation facilitates design, we consider detecting the arrival of the first two candidates.

To implement the ordered pair arrival, we can employ a coupled model of FirstArrival units with activation capability as in Figure 9.

Here the input is sent to both components as in a parallel composition but the Activate coupling is implemented in a serial manner. The upper FirstArrival starts in the activated state and detects the first arrival while the second component is not active. Receiving the activation from the first (now passive) component, the second component can now wait for the second arrival and respond to it when it arrives. Any subsequent inputs will be blocked by both units. Note: we will discuss the included DeadlineTimer component momentarily.

Following the methodology of Figure 2, we ask how the realization in Figure 9 relates to a minimal realization of the ordered pair arrival behavior. By unfolding the monoid tree as earlier discussed, we note that the tree expands to depth 2. Due to the restriction on reoccurrence, the number of nodes beyond the root is n(n − 1) where n is the cardinality of the event set. Therefore, the required number states is n² − n + 1. In comparison, the pair of FirstArrival components gives the coupled model a state cardinality of (n + 2)² so that it has order(n) more states than minimally required. As before, we can define a hom*omorphism from the FirstArrival pair to the minimal realization noting the first level of the tree maps to the first unit states with a similar mapping from second level to the second unit.

Note that this method can be extended from ordered pairs to ordered tuples of any size, m. The coupled model of Figure 9 then expands to contain m FirstArrivals with the same kind of coupling pattern which distinguishes I/O processing from activation—the former a distribution in parallel, and the latter in serial. The implementation has (n + 2)^m states while the minimal realization has n(n − 1)…(n ⋯ m + 1) = n!/(n − m + 1)! states. Again, a hom*omorphism from the implementation to the minimal realization maps successive stages of the implementation to successive levels of the monoid tree.

As before this definition can be extended to any size, m of arriving tuple so that the unordered set of the first m events that arrive is output. This reduces the size of the minimal realization to the combinatorial n!/(n − m + 1)!m! states. We note that the same form of implementation can be retained, leaving the question open of constructing a smaller implementation that exploits the loss of information due to removal of order in the output.

As illustrated in Figure 9 and Figure 10, an implementation here can add a timer in parallel with a FirstArrival composition and have it deactivate the latter at the expiration of the deadline duration. Given that no limitation is placed on the occurrence of the events relative to the deadline, the minimal realization must still be able to reproduce the original output and there it must have at least the same number of states as before. In addition, the composition with the timer, which has initial and final states, doubles the number via the cross-product.

3.5. Perception of Order of Discrete Event Arrival

With an ultimate interest in generation and recognition of DEVS segments of events we first characterize the behavioral requirements underlying perception of order of discrete event arrival. We will provide a minimal realization for such behavior and use its implementation subsequently in the finite language framework for DEVS segments. As in Figure 11, consider two discrete events, a and b, that occur in a given time interval and are input to a system that is supposed to output judgements about the arrivals in relation to each other. We represent the perception of order of occurrence as a function that maps event segments into a value at end of the interval. Further, different from the considerations earlier made for decision making, we include the separation in time between the events as relevant. We start with the requirement that the function be able to mark the arrival of b after a within a given interval. Other possibilities to distinguish include a or b happening alone, simultaneous occurrence, and no events occurring within a given interval. As in Figure 11, we formulate the computation, β, as an I/O Function behavior in the DEVS formalism. We then provide a realization at the state level as a DEVS atomic model and show this to be a minimal realization.

Unfolding the monoid tree, we obtain Figure 11 which leads to the minimal realization. Note that we distinguish between an arrival of event b following event a within interval μ and later than that by corresponding segment length limits.

As above, we can formally represent the behavior of the order-of-arrival neuron mentioned earlier. By unfolding the monoid tree, we can lay out a minimal realization which given any specific order of arrival of n distinct events, i.e., any permutation of the events, recognizes it with n+1 states. By unfolding the tree, we see that the minimal realization of the behavior that recognizes any one of an incident permutation of n events has n! + 1 states (a reduction in size from nⁿ states required to recognize any combination of n events).

3.6. Elementary Perception Unit

To create an Elementary Perception Unit (EPU), the FirstArrival design is extended to include a parameter specifying a particular event to recognize and a time to wait for the event after activation. As in Figure 12, this makes use of the DEVS time advance function that assigns a time to remain in a state before transitioning to the next assigned one—in this case to a state indicating that no event of the specified form has been received.

The coupled model in Figure 13 implements the order of arrival of event a followed by event b, where the EPUs recognize a and b, respectively. The coupling manifests the earlier pattern in which activation and I/O processing couplings are distinguished. Activation is passed on sequentially from the first EPU to the second upon the positive event recognition by the latter. In contrast, the input is distributed to all components uniformly, as is the reset input. Similarly, activation is emitted externally only from the last EPU. However, the time out notice can emerge from any component.

In the following we extend this capability to regular languages which are sets of event segments that can be defined in a generalized finite state manner.

4.1. DEVS Recognizer Models

We strip the time information to obtain the string x₁,x₂,..,x_n. The erasure of time information is called the natural encoding of DEVS segments to strings. We extend the concept of language recognition and generation from sequences to DEVS segments. Roughly, this requires that the DEVS model partitions the set of all segments into accepted and non-accepted sets just in case the stripped sequences are partitioned in the same manner by an automaton. Indeed, the way we proceed is to extend a finite state automaton to a DEVS in such a way that the language it accepts is in fact, the set of sequences stripped from the DEVS input segments. Figure 14 illustrates the approach. An atomic model that recognizes a single symbol e.g., the language {x} appears in Figure 14a with input Activate to send it from the Wait state to the Hold State as shown in Figure 14c. After this, an input with label x happening some time later will cause the model to enter the Send state and to output an Activate output signaling the acceptance of the input. Any other input label will return the model to the Wait state without sending such an output. The model in DEVS set notation appears in Figure 14b.

4.2. Constructing a DEVS Recognizer for Segments Sets in DEVS(X)

As illustrated in Figure 15a, we define an input-driven DEVS as a DEVS model for which the time advance in all states is infinite. Effectively, this means that the only source of state change is from external events and we may omit the internal transition function as in the definition: M = <X,S,δ_ext,ta> where ta(s) = ∞, for all s ∈ S. For convenience we also omit the output function. Furthermore, we will require that the elapsed time, e plays no role in state transitions due to inputs so that: δ_ext (s,e,x) = δ(s,x). Now, as illustrated in Figure 15b, a transition system, underlying a finite automaton, can be defined as T = <X,S,δ> where δ:S × X→ S. Therefore, we have the following proposition:

A sketch of the proof is illustrated in Figure 15c. Construct a DEVS M whose states and transitions are labelled in one-one correspondence to those of T. Suppose that T undergoes a state sequence s0, s1, s2, s3 in response to an input sequence x1, x2, x3. Then if M is fed an event segment with natural encoding to x1 x2 x3, M will undergo the state trajectory shown which in stripped form matches that of T. Technically, we can show that the natural encoding together with the one-one state mapping constitute a hom*omorphic simulation of T by M (see definition in [1]).

We also readily have the converse:

Now we can extend T to an automaton A_T by adding to it labels for an initial state and a set of final states. Likewise, extend M to a DEVS Recognizer, R_M with addition of the same initial state and set of final state labels. Then stated in succinct form:

Expanded, this means that the set of DEVS segments that drive the input free DEVS from its initial state to a final state, when stripped of their timing, is the set of sequences that drive the corresponding automaton from its initial state to one of its final states.

Note that to conform to the input/output interface for the DEVS model of Figure 14a, we have the model start in a Wait state and have it transition to the initial state upon receiving an Activate output. Likewise, we have it generate an Activate output when transitioning into a final state. This converts its input-free nature to a full-fledged DEVS. However, this interaction is only manifest for the Activate interface.

The proof centers on the fact that the internal operation of an input-driven DEVS is exactly replicated in the automaton constructed from it. Conversely if a set is accepted by an automaton, then an input-free DEVS can be constructed that replicates this behavior in relation to the natural encoding.

4.3. Regular Realization at the DEVS Network Level

In this section our goal is to develop templates for realizing the behavior expressed by regular languages in the form of DEVS coupled models. This will be done by realizing finite state automata in network form in a particular way that allows generalization to continuous time segments.

There are multiple representations of a regular language as a regular expression and as a finite state automaton. The mapping in Figure 16a,b gives a simple example. Further there are multiple realizations of finite state machines in networked form as e.g., well-known clocked sequential circuits. As illustrated in Figure 16b,c, the realization approach we take employs the recognizers for elementary symbols from Figure 16. In the mapping, each transition label is mapped to a recognizer of that label and each state is mapped to an activation node shown as a black oval component. For example, the states s0 and s1 are mapped to activation nodes s0 and s1, while the transition from s0 to s1 labelled a is mapped to a recognizer for a. Starting in initial state s0 is represented by external activation of its representative component. External input is coupled to each recognizer’s input port. As in Figure 12, a recognizer can only pass on activation to its target state representative if has received activation from a predecessor state. The mapping is algorithmic and can be implemented to generate coupled model recognizers for the source regular expression as illustrated in Figure 16d in a DEVS simulation environment [26].

Note that the activation node behavior can be easily captured by a simple atomic DEVS which produces an Activate output in response to the first Activate input that it receives. Quick considerations shows that the minimal realization of this behavior requires only two states.

Formally, we can prove the theorem:

The proof shows that exactly one activation node is in the Active state and it enables the recognizers for its corresponding state’s outgoing input labels. Only one recognizer for each label accepts the next external event (assuming deterministic automata) and activates the target activation node representing the next automaton state. The proof then proceeds by induction to show that at the end of the input segment a final state is reached or not according to whether or not it is in the regular language.

5.1. Summary of Building Blocks and Architectural Patterns

Building blocks can be summarized as:

Architectural patterns:

5.2. Multiple Subsystems Competition Application

Now we discuss an application that illustrates the application to system design.

An example where the overall methodology illuminates the modeling of cognitive behavior is offered by the multiple memory systems theory [38] which asserts different kinds of information are processed and stored in different parts of the brain. This can lead to different proposals for action in response to a situation and the need to resolve the competition. In Figure 17, the Procedural, Emotional, and Declarative systems operate in parallel with common inputs and outputs. Further, each have their own structures and independently extract different kinds of information from the ongoing activity. Procedural memory refers to constant stimulus-response (S-R) relationships that lead to successful outcomes. Information processed and stored in this system tends to produce the response whenever the stimulus is encountered. The Emotional system refers to (S-Af, or stimulus-affect associations) while the Declarative system stores and applies S-S higher level cognitive factual knowledge relations.

An experiment [38] tested the theory’s claim of independent parallel potentially conflicting decisions by placing rats in a maze with different configurations to elicit different foraging strategies.

Each configuration provided the rat with a different kind of information about the location of food on the maze. Normal rats learned to locate the food easily in all three configurations. The first task requires keeping track of the locations of past successful accesses to food to enable predicting future food locations (requiring spatial map declarative processing). In the second task lights inform the rats about the current location of the food and they learn to associate the light with the food availability (requires operant stimulus-response procedural processing). The third task confines a rat to one location and requires associating environmental cues there with presence or absence of food (requiring emotional system classical conditioned response processing). Lesions to different parts of the brain confirmed the separate location and independence of the respective systems responding to these tasks. However, training from the first task did cause reduced performance in the second task as rats showed uncertainty whether to follow the light cues or the dependence on prior location.

To explain this reduction, the experimenters hypothesized that (1) the system with the most coherent representation produces the strongest output and wins the competition for control of behavior, but (2) another system with a less coherent representation can produce output that is sufficiently strong to negatively influence behavior [38]. In Figure 17, we show this direct resolution of conflict by direct outputs from the parallel systems to the actuator output. In contrast, the candidate selection computation primitive, represented by the FirstArrival component, would enable the conflict to be resolved before any output is generated. In this design, the relative strengths of the system outputs would be manifested as computation delays with the fastest gaining control of the final output. In a variation, the deadline feature could leave a subset to compete for final output with resulting degradation in performance. This would predict that under time pressure, output behavior is more likely to be optimal than with none applied. As in FFA, if rats are forced to make a choice, they make the best available. Thus, design of artificial agents might potentially improve on natural systems with more advanced designs for conflict resolution decision systems.

Future research should be focused on using and extending the methodology for further exploring potentially useful DEVS building blocks and architectural patterns for Hybrid Intelligent Cyberphysical Systems [39,40].

A note about using Classic DEVS rather than PDEVS as basis for the theory developed in this paper: Classic DEVS was used in an effort to keep the exposition as simple as possible for the reader unfamiliar with DEVS. I believe that the main results carry through to the PDEVS case which introduces the complications of simultaneous events and multiple simultaneous inputs. However, establishing this claim is left for future work. It should be stated that the current results apply to discrete event neural nets due to the vanishing probability of synchronous events [24].