Behavior modeling for hybrid robotic systems
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
The behavior of a certain class of hybrid robotic systems can be expressed using formal languages. In this work, we show how languages can be generated from discrete abstractions of such hybrid systems; that these languages are regular; and they belong to the star free (SF) class of the Sub-regular hierarchy. Planning and control of hybrid systems is typically difficult due to the computational cost involved in predicting the system’s future states, since the states can take infinite values while evolving along the trajectories of continuous dynamics. A discrete abstraction of the hybrid system can reduce these values to a finite number, thereby fascilitating the solution to the reachability problem. Abstraction enables us to focus on planning the system’s overall behavior through controller sequences observed in the abstract system, instead of dealing with the dynamics associated with each controller. The constraints between controllers enable or disable their temporal sequencing. Similarity of these constraints with those found in formal language theory, allows us to express controller sequences as strings of symbols forming a formal language. A formal language analysis of hybrid systems provides an approach for automatic planning and control design synthesis in single and multi-agent robotic systems. The class of hybrid systems considered in this work have convergent continuous dynamics with parameterized attractors. We model a robot as a hybrid system, and abstract the hybrid system to a discrete transition system. Plans of controller sequences generated on the transition system are implementable on the hybrid system because of a (weak) bisimulation established between the two systems. Constraints are identified between controllers, that affect their sequencing, with each constraint forming a sub-regular class of controller sequences. Intersection of these languages yield (sub)regular robotic languages that express the overall behavior of the underlying hybrid system. Other models of robot (motion) control such as motion description languages and linear temporal logics generate regular and !−regular languages respectively. Subregular languages, generated by our classes of hybrid systems, offer structure that can be exploited to operate on system representations in a way that reigns in the complexity of the outcome. The technical contribution of this work in the field of analysis of hybrid systems is that it identifies classes of hybrid robotic systems that can be abstracted so that their overall behavior can be described using subregular languages, and characterizes these languages within the Chomsky hierarchy. This work contributes also to the formal language community by defining a new class of subregular languages, called the tier-based strictly local languages, which captures long-distance constraints between symbols. The tier-based language models have existed in phonology, especially in the form of autosegmental patterns. However, these models have primarily dealt with expressing certain phonological patterns on tiers, instead of analyzing the tiers, as our work does here. This work opens ventures for exploring learning of the regular robotic languages by using phonological learners. In addition, cooperative behaviors between homogeneous and heterogeneous robots, by performing intersection of their regular robotic languages, can be looked into as future work. Formal language theory also offers algebraic tools for analysis of the languages and automata, which can be explored for studying optimal plans of hybrid system behavior, and can aid in composing and decomposing languages.