Discrete Event Systems Based Robotic Task Modeling: Difference between revisions
| Line 15: | Line 15: | ||
When using finite state automata (FSA) representations, propositions and primitive actions are collected in states, and events are associated to transitions. | When using finite state automata (FSA) representations, propositions and primitive actions are collected in states, and events are associated to transitions. | ||
<BR> | <BR> | ||
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 | 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. | ||
<BR> | <BR> | ||
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. | 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. | ||
Revision as of 19:21, 19 November 2008
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.