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

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.

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