Discrete Event Systems Based Robotic Task Modeling

Supervisory Control of DES consists of restricting the behavior of a DES in order to achieve a set of specifications, usually expressed as required and/or admissible languages, with respect to the original language of the unsupervised system.

In this work, we use Linear-Time Temporal Logic (LTL), an extension of Propositional Logic which allows reasoning over an infinite sequence of states, to specify the performance objectives for a given DES in a more natural language, and build a supervisor that restricts the DES’ behavior to those objectives by construction.

The figure depicts an FSA representing the different possible behaviors for a single soccer robot. For instance, when the robot has the ball (state with_ball) it may decide to prepare to get close to the ball to prepare to kick it, to move with the ball towards the goal, or to prepare a pass, choosing the receiver, in case the uncontrollable event blocked_path occurs. This FSA can be composed with similar FSA representing the behaviors of homogeneous teammates. An LTL specification prevents any robot in the team from receiving a pass until one of them is selected as the receiver by the passer. Another situation is when the robot does not have the ball: the options are either moving towards the ball to catch it or getting ready to receive a pass. Again, an LTL formula can be used to avoid that more than one robot move towards the ball simultaneously. More details in [5].

For both models, it is convenient to build up a separate environment model of the same type, i.e., an FSA or a PN model of the environment, where transitions are associated to robot controllable events (thus representing its effects), or uncontrollable events (thus representing environment natural events, including those caused by other agents starting their own actions.
In fact, especially for PNs, the key issue is that one can build a large complex robotic task model by connecting simple PN modules which represent the dynamic of the robot subsystems (e.g., the PN representing the navigation system, or the perception system status). Macro-actions can also encapsulate action compositions. And the whole robot plan, represented by a PN, can be composed with the environment pan, also represented by a PN (in fact, this composition between the robot plan and the environment models is also true for FSA representations).
Robotic task performance analysis should be performed over the above closed loop model of the robot situated in its environment. Two main classes of analysis problems are:

• qualitative/logical analysis: such as determining PN liveness (is the plan resetable, can the robot recover from an error?), boundedness (are we using too many resources, e.g., calling a primitive action to run concurrently in a number of processors – or robots – larger than those available?), blocking (deadlocks, livelocks)
• quantitative/stochastic performance analysis: is a plan robust to changes of primitive action reliability around their nominal values? what is the probability of succes of a plan, given the reliability of its composing primitive actions?

Petri net plan representations are especially adequate to represent plans for cooperative robots. In this case, places must also represent communicated messages (sent and received), which in fact represent again predicates which, when their arguments are instantiated, become true or false propositions. Examples: waiting4you_sent, waiting4you_received, arriving_sent, arriving_received. Two types of communicated signals are relevant for cooperation (coordination + teamwork): those required for synchronization, and those required for commitment.
Synchronization concerns coordination, e.g., two robots transporting a bar and exchanging signals to avoid that one of them advances too much ahead or lags behind. One example in soccer robots can be seen in this video animation of a pass.

We have been using Petri nets to program individual and relational behaviors in the SocRob project with soccer robots, with synchronization and commitment. Commitment is based on the formalism of Cohen’s and Levesque’s joint commitment theory, and essentially assures teamwork, i.e., once two or more robots get involved in a relational behavior, they mutually commit to inform their involved teammates if the joint goal became irrelevant or can not be reached anymore (e.g., due to a failure of one of them to proceed with its part of the behavior).
The following two videos show 2 robots of our RoboCup ISocRob MSL team performing a pass, both in simulation and reality (the same code is used in both cases).
A similar concept was applied to the ISocRob 4LL team, with 2 AIBOs exchanging ball passes – see video, including simultaneous PN execution. This was joint work with Daniele Nardi’s group, at U. Rome “La Sapienza” [6][7].

We have introduced a novel approach to the study of the dynamics of molecule expression level in large-size cell populations, whose goal is to understand how individual cell behavior propagates to population dynamics. In fact, the results obtained can be used to study the dynamics of (cell) populations in general, and we have also extended it to model robot swarms, and to come up with optimal stochastic control laws for them.
A Hybrid Automaton framework is used, where each discrete state corresponds to a macro state of the (cell, robot) population, and the continuous state to the micro state of each element in the population. The transitions between discrete/macro states are stochastic, and their rates are the most relevant parameters of the model.

For the cell populations, this approach enables the simultaneous modeling of the formation and dissociation of cell-to-cell conjugations, and the molecular processes they control. Serial encounters among the cells are described by a stochastic approach under which the cell distribution over the state space is modeled and the dynamics of the state probability density functions is modeled by a partial differential equation. This work was motivated by the investigation of T-cell receptor expression distribution. These receptors are essential for the antigen recognition and the regulation of the immune system. [9]
For robot/agent populations, this resulted in an approach to the modeling and control of swarms, i.e., multi-robot/agent populations composed of a large number of robots/agents. Beyond the population dynamics modeling, the control problem of maximizing the probability of robotic presence in a given region was introduced. The Minimum Principle for the optimal control of partial differential equations was exploited to solve this problem and it was applied to the mission control of a simulated large robotic population. [8]

This work was mainly the result of Dejan Milutinovic’s PhD thesis, published in a Springer STAR Series book [10].

Prof. Michael Athans (Emeritus Professor at MIT) was also involved in the co-supervision of Dejan, and this work started up a collaboration with Instituto Gulbenkian de Ciência, namely with Prof. Jorge Carneiro, coordinator of the Theoretical Immunology group.