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.

Stochastic Hybrid Automaton Model of Large Robot Populations

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