Discrete Event Systems Based Robotic Task Modeling
Most of the existing robotic task models are not based on formal approaches, are concerned only with a small number of behaviors and are typically tailored to the task at hand. We have proposed, back to 1998 [1] a systems-theory-based task modeling approach for general robotic tasks which enables a systematic approach to modeling, analysis and design, scaling up to realistic applications, providing methods for logical verification, stochastic performance, and design from specifications, as well as execution improvement over time through learning. Our approach is based on using discrete event systems (DES) models, mainly Petri nets and finite state automata, for robot plans representation. This particular representation enables using all the available DES analysis and design tools to handle robotic task formal analysis and design.
Representing robot plans by DES
A plan is composed of several actions, running concurrently or sequentially. Action sequences, loops, subplans running in separate robots from a team, are possible examples of plans under the above definition.
In our robotic task model, theree entities are defined:
- propositions (predicates with instantiated arguments), e.g., see(object), in(robot1, room3)
- primitive actions (may have arguments, but must be also bound to some actual object), e.g., move2object, standby, catch(glass)
- events, e.g., start_standby, button_pressed, wheel_failure
The subset of events corresponding to starting a primitive action are controllable. Those
corresponding to occurrences the robot(s) can not start or stop (e.g., due to the environment dynamics, ot to other agents' actions) are uncontrollable.
When using finite state automata (FSA) representations, propositions and primitive actions are collected in states, and events are associated to transitions.
Petri net (PN) models of robotic tasks distribute the state across the PN places. Some places represent propositions, other represent primitive actions. When one such place has a token, the model signals that a proposition is true or an associated primitive action is running, respectively. Events are associated to transitions.
One may have different FSA or PN views, namely a logical untimed view, where the model can be studied based on the language (event strings) it generates, or a stochatic timed view, where time is of concern, and considered stochastically distributed. If stochastic interevent time is associated to transitions, one gets stochatic timed FSA or PN. If the event time pdf is exponential, both the FSA and the PN reachability graph can be made equivalent to Markov Chanis. If we consider the controllable event subset as subject to decisions by a higher command level, the model ends up being a Markov Decision Process (MDP), and dynamic programming or reinforcement learning solutions can be applied to determine the optimal plan in terms of minimizing some cost function, where costs are associated to primitive actions, and may include thprimitive action reliability.
Robotic task supervision using LTL
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].
Robotic task performance analysis using Petri nets
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?
Synthesizing a plan from an initial set of specifications is the natural next step to analysis, but we have not done much into that direction yet.
Cooperative plan representation and execution
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].
Stochastic Hybrid Automaton Model of Large Robot Populations
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.
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.
This work was mainly the result of Dejan Milutinovic's PhD thesis, published in a File:DejanBookCover.jpg Springer book [9].
References
[1] P. Lima, H. Grácio, V. Veiga, A. Karlsson, "Petri Nets for Modeling and Coordination of Robotic Tasks", Proc. of IEEE International Conference on Systems, Man, and Cybernetics, San Diego, USA, 1998
[2] D. Milutinovic, P. Lima, "Petri Net Models of Robotic Tasks", Proc. ICRA2002 - IEEE International Conference on Robotics and Automation, Washington D.C., USA, 2002
[3] H. Costelha, P. Lima, "Modeling, Analysis and Execution of Robotic Tasks using Petri Nets", Proc. of IROS 2007 - IEEE International Conference on Intelligent Robots and Systems, San Diego, CA, USA, 2007
[4] H. Costelha, P. Lima, "Modeling, Analysis and Execution of Multi-Robotic Tasks using Petri Nets", Proc. of AAMAS 2008 - Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, Lisbon, Portugal, 2008
[5] B. Lacerda, P. Lima, “Linear-Time Temporal Logic Control of Discrete Event Models of Cooperative Robots”, Journal of Physical Agents, Vol. 2, No. 1, Special Issue on Multi-Robot Systems, 2008
[6] P. F. Palamara, V. A. Ziparo, L. Iocchi, D. Nardi, Pedro Lima, "Teamwork Design Based on Petri Net Plans", Proc. of RoboCup International Symposium 2008, Suzhou, China, 2008
[7] V. Ziparo, L. Iocchi, P. Palamara, Hugo Costelha, D. Nardi, "PNP: A Formal Model for Representation and Execution of Multi-Robot Plans", Proc. of AAMAS 2008 - 7th International Joint Conference on Autonomous Agents and Multi-Agent Systems, Estoril, Portugal, 2008
[8] D. Milutinovic, Pedro Lima, "Modeling and Optimal Centralized Control of a Large-Size Robotic Population", IEEE Transactions on Robotics, Vol. 22, Issue: 6, pp.1280-1285, 2006
[9] D. Milutinovic, J. Carneiro, M. Athans, P. Lima, "Modeling Dynamics of Cell Population Molecule Expression Distribution", Journal of Non-Linear Analysis: Hybrid Systems and Applications, Elsevier, Vol. 1, Issue 1, pp. 81-94, 2007
[9] D. Milutinovic, P. Lima, "Cells and Robots - Modeling and Control of Large-Size Agent Populations", Springer Tracts in Advanced Robotics (STAR) Series , Vol. 32, 2007