SHIFT and SMART-AHS: A Language For Hybrid System Engineering Modeling and Simulation

Notice that the cruising state redefines velocity, which becomes algebraically defined (as a constant in this case) instead of differentially defined (as the integral of the acceleration).

Transitions between discrete modes are defined in the transition clause, as in the following example.

type car
{
	...
	transition
		accelerating  -> cruising {}
		  when velocity >= 30,
		cruising -> braking {}
		  when position(car_in_front) - position < 5;
} 

The example uses the state variable car_in_front containing a reference to another car, whose relative position is used in deciding when to apply brakes.

Transitions are labeled by a (possibly empty) set of event labels. These labels allow transitions to synchronize with each other. Moreover, transitions may be guarded by boolean expressions -- introduced by the when keyword -- and may trigger a set of actions grouped in a do clause. These actions reset (4) (i.e. assign) the values of variables, may create new components and may reconnect their inputs and outputs.

Suppose that we wish the car to brake when a road-side controller signals an emergency. This can be specified with the transition

type car
{
	...
		cruising -> braking {controller:emergency}
		  when position(car_in_front) - position < 5;
} 

The definition of the controller type includes an exported event, emergency, and a transition that triggers it.

type controller
{
	export emergency, ...;
	discrete normal, panic_mode, ...;
	transition
		normal -> panic_mode {emergency}
		  when some critical condition;
	...
} 

SHIFT allows the system modeler to specify very complex patterns of synchronous composition of finite state automata. The transition guards may contain existential quantifiers that query the state of sets of components (possibly all existing components). For example, let cars be the set of all the components of the car type and let the road consist of a single lane. Then, the variable car_in_front is updated as follows.

type car
{
	...
	transition
		cruising -> cruising {}
		  when exists c in cars :
		         position(c) > position
			 and position(car_in_front) > position(c)
		  do {
			car_in_front := c;
		  },
		...
} 

The initializations of a newly-created component of some type are defined in the setup clause. For example, each component of type car may add itself to the set cars when it is created.

type car
{
	...
	setup
		do {
			cars := cars + {self};
		};
} 

In practice a SHIFT program would not use this exact code unless cars were a small set. A more efficient mechanism requires maintaining multiple sets of cars associated with lanes and highway segments.

SHIFT Support Environment

SHIFT programs are translated directly into C by the shic<\t> compiler. The resulting C file is then linked with the SHIFT runtime library in order to produce an executable (a file conventionally ending with .sim<\t>). The runtime library takes care of the implementation of the high level data structures used by SHIFT (e.g. sets) and makes provisions to integrate the differential equations via standard Runge-Kutta algorithms. There are no special optimizations that are done by the compiler (6). The only requirement imposed on the system is that the behavior of the run-time which essentially interprets the set of finite state machines and differential equations complies with underlying mathematical model.

There are several subtleties involved in the interaction between the RK integration routine and the guard evaluation code. Languages like Omola/Omsim that support only a static set of differential equations can perform compile-time optimizations to select integration step sizes. In SHIFT since the dependencies among the components can change at run-time, it is not possible to optimize integration step-sizes with respect to guard-crossings. SHIFT applications so far have been primarily in non-stiff systems, hence a fixed-step RK integration algorithm had the best performance. We recognize that this is still an open research field.

The executable file can be run is two ways: by starting a command line monitor or by connecting the simulation with a Tcl/Tk graphical user interface in a client/server fashion (7)

Both the command line monitor and the graphical environment allow the user to control the running simulation. Typical operations include

• data inspection
• stepping by time click and by "simulated time"
• stopping and resumption of execution in correspondence of discrete transitions.

Developing Simulation Frameworks in SHIFT: The SMART AHS Case

1. To provide researchers with a standardized tool which can be used for evaluation of simulation results under different policies.
2. To allow the quick construction of alternative simulation models.
3. To allow the simulation of models at different granularity levels.
4. To be able to handle medium to large scale simulations.

In Sections 3.1 and 3.2 we describe the SMART AHS architecture and discuss the lessons learned in its deployment as one of the standard tools used by the National Automated Highway System Consortium (NAHSC).

SMART AHS Architecture

The highway types comprise Lane, Section, Segment, Barrier, Block and Weather. These types and their structure constitute a data description language for highways. The vehicle types are centered around a container type called AutomatedVehicle. Its most immediate sub-components are Controller, VehicleModel and VREP (Vehicle Roadway Environment Processor). FigureX contains a schematic representation of the AutomatedVehicle SHIFT code.

This architecture meets the requirements by allowing the system modeler to plug in different controllers and vehicle dynamic models. Researchers at PATH have successfully developed two classes of models for highly detailed vehicle dynamics simulation and for high volume highway simulations with complex vehicle maneuvers.

The detailed simulation model describes a vehicle at the level of gear shifting and engine dynamics. The model is realistic and based on real data collected by General Motor researchers.

The "high volume" simulation model uses a simplified vehicle dynamics model (there is no need to simulate the engine dynamics when computing flows over stretches of highway) and a controller which is devoted to maintain safety parameters (e.g. distance from the vehicle in front) and to perform merge maneuvers on entrance and exit ramps.

Micro Simulation of Houston Metro Katy Corridor

Most of the work done to develop the simulation went into the construction of a Controller module which would obey a distributed protocol for cruising and merging into existing traffic. A code fragment for the Controller is shown hereafter.

type Controller
{
	output
		continuous number acceleration;
	...
	state
		Vehicle the_vehicle, side_lane_vehicle;
		continuous number same_lane_accel;
		number nominal_speed;
	...
	discrete
		cruise {cruise_law};
		yield {yield_law};
	...
	flow
		default {
			same_lane_accel =
			track_acceleration(same_lane_rel_speed,
                                           xDot(the_vehicle),
                                           nominal_speed);

		};
		cruise_law {
			acceleration = same_lane_accel;
		};
		yield_law {
			 acceleration = min(same_lane_accel, side_lane_accel)
		};
	...
	transition
		cruise -> yield {}
		  when rear_gxp(the_vehicle)
		       >= L_gap_visible_range(junction)
      	               and exists mp in merging_vehicles(junction) :
	                      ((rear_gxp(mp) >= front_gxp(the_vehicle))
	                       and (rear_gxp(mp)
			            <= front_gxp(the_vehicle) + lateral_sensor_range)
	                       and (xDot(the_vehicle)
				    <= xDot(mp) + yield_rel_speed_threshold))
		  do {
			side_lane_vehicle := mp;
		  },
	...
}

A fragment of the Controller code. The fragment shows the transition that takes the (instance of) the Controller of the_vehicle from the cruise to the yield state. The condition upon which this transition is allowed is expressed in the when clause. The variables suffixed by _gxp and _gyp represent positions. The accessor xDot(the_vehicle) is integrated to the current speed of the vehicle.

When the transition has taken place, the integration will use a modified set of equations to produce the value for the acceleration parameter, whose computation eventually relies on a C function (track_acceleration).

The GUI environment was used to visualize the results of the simulation in order to spot problematic areas of the protocol. We tested four cases on a matrix given by high and low traffic demand and by enforcing two different vehicle tracking policies. The traffic demands levels can be summarized as follows:

low

ca. 2000 vehicles/hour injected in the highway system.

high

ca. 4000 vehicles/hour injected in the highway system.

Discussion and Evaluation of the SMART AHS Framework

• SHIFT provides a sound and restricted mathematical model (Hybrid Systems) which can be successfully mastered by an engineer in a rather short period of time. The tools provided (differential equations and finite state automata) are the "right" ones for the kind of models we were targeting.
• SHIFT and SMART AHS code is significantly more compact. The SHIFT implementation of SMART AHS consists of 3,300 lines of SHIFT code and 2,000 lines of C legacy code (10), plus about 5,000 lines for the full SHIFT runtime (11). The Houston-Metro case study consisted of 3,800 additional lines of SHIFT code. The predecessor of SMART AHS (SMART AHS_C++) consisted over 20,000 lines of C++ code, without the code for the distributed merging controller and the highway building
• The SMART AHS framework has a very small set of "how-to-use" rules that a programmer needs to know about. As a result new users can immediately become more productive in application development. Based on our experience with the previous incarnations of SMART AHS, frameworks based on C/C++ usually have too many "how-to-use" rules that are not enforced by any compiler and result in unpredictable run-time errors if not followed properly.

The entire simulation study of the Houston Katy Corridor was built from scratch (i.e. the highway layout, the vehicle dynamics models, the merge and cruise protocol and the actual simulation runs) in less that three work weeks.

The merge simulation case study is being followed by more complex studies regarding

• emissions evaluation,
• coordination protocols involving radio communications,
• "platooning" of cars on automated highways, and
• detailed physical simulation of crash and "near-miss" situations for safety analysis.

Preliminary Cost Analysis

The cost for the Houston case study turned out to be in the order of 3 men/month. Subsequent projects (emission control simulation, platooning and coordination) reused much of the overall structure developed in the first place for the Houston Case Study and showed a faster turnaround of the simulation results.

SHIFT is used in other application domains such as autonomous underwater vehicles, and air traffic management simulations. However, our group has not undertaken a formal project tracking effort in order to evaluate the overall impact of the technology outside California PATH.

Conclusion

To support our claim we have described our experience with the SMART AHS framework for the simulation of complex highway systems. Our experience indicates that SHIFT and SMART AHS do achieve the objectives that were at the base of its design.

In particular, SHIFT is currently enjoying a growing popularity and is being used as a teaching tool in various courses in the Electrical Engineer Department of UC Berkeley.

Future work on SHIFT will include the following items:

• further research on the interaction between the integration and guard crossing algorithms;
• parallelization and distribution of the run-time system;
• integration with automated verification systems such as Kronos [].

As already mentioned, at this point we cannot provide a direct comparative study of the "simulation development costs" for SHIFT and SMART AHS with respect to a more traditional approach based on standardized libraries. Setting up such a study would require a considerable effort in itself and the identification of a proper set of tools to compare SHIFT and SMART AHS against. However, the feedback we gathered from the users of SHIFT makes us very confident that the results would tip the balance in its direction.

Acknowledgments

Availability

References

[1] R. Alur, C. Courcoubetis, T. A. Henzinger, and P. Ho.
Hybrid Automata: An Algorithmic Approach to the Specification and Verification of Hybrid Systems.
In R. L. Grossman, A. Nerode, A. P. Ravn, and H. Rischel, editors, Hybrid Systems, volume 736 of Lecture Notes in Computer Science, pages 209--229. Springer-Verlag, 1993.

[2] M. Antoniotti, A. Deshpande, and A. Girault.
Microsimulation analysis of automated vehicles on multiple merge junction highways.
In Proceedings of the IEEE Conference on Systems, Man, and Cybernetics (SMC97). IEEE, October 1997.

[3] M. Antoniotti, A. Deshpande, and A. Girault.
Microsimulation analysis of multiple merge junctions under autonomous ahs operation.
In Proceedings of the IEEE Conference on Intelligent Transportation Systems (ITSC97). IEEE, November 1997.

[4] F. Barros.
Dynamic Structure Discrete Event System Specification Formalism.
Transactions of the Society for Computer Simulation, 1:35--46, 1996.

[5] H. Boehm and M. Weiser.
Garbage Collection in an Uncooperative Environment.
Software Practice and Experience, pages 807--820, September 1988.

[6] C. Daws, A. Olivero, S. Tripakis, and S. Yovine.
The tool KRONOS.
In Hybrid Systems III, Verification and Control, volume 1066 of Lecture Notes in Computer Science. Springer-Verlag, 1996.

[7] A. Deshpande, A. Göllü, and P. Varaiya.
A Formalism and a Programming Language for Dynamic Networks of Hybrid Automata.
In Hybrid Systems IV. Springer-Verlag, 1997.

[8] F. Eskafi, D. Khorramabadi, and P. Varaiya.
An Automated Highway System Simulator.
Transportation Research Journal, part C, 3(1), 1995.

[9] D. Harel.
Statecharts: A Visual Approach To Complex Systems.
Science of Computer Programming, 8(3):231--275, 1987.

[10] F. Maraninchi.
The Argos Language: Graphical Representation of Automata and Description of Reactive Systems.
In Proceedings of the IEEE International Conference on Visual Languages. IEEE, 1991.

[11] S. E. Mattson and M. Anderson.
The Ideas Behind Omola.
In Proceedings of the IEEE Symposium on Computer Aided Control System Design, CADCS 1992. IEEE, March 1992.

[12] R. Milner, J. Parrow, and D. Walker.
A calculus of mobile processes, I and II.
Information and Computation, 100(1):1--77, September 1992.

[13] H. Praehofer, F. Auernig, and G. Resinger.
An Environment for DEVS-based Multiformalisms Simulation in Common Lisp/CLOS.
Discrete Event Dynamic Systems: Theory and Application, 3(2):119--149, 1993.

[14] J. T. Schwartz, R. B. K. Dewar, E. Dubinsky, and E. Schonberg.
Programming with Sets. An Introduction to SETL.
Springer-Verlag, 1986.

[15] P. Varaiya.
Smart Cars on Smart Roads: Problems of Control.
IEEE Transactions on Automatic Control, 38(2):195--207, February 1993.

[16] B. Zeigler.
Multifaceted Modeling and Discrete Event Simulation.
Academic Press, London, Orlando, 1984.

Notes

1. The SHIFT systems provides a C API for this style of programming.
2. Our terminology abuses words like type. Using more standard Object Oriented terminology, we would speak of instances and classes. We use the term "component" since the control theory application domain imposes a natural part-of metaphor on the software architecture.
3. Of course, only continuous number variables make sense in a differential definition
4. The terminology, once again is borrowed from the field of hybrid system studies.
5. Among them: single inheritance, complex set and array formers á la SETL [14], garbage collection (using Boehm's conservative GC [5]), a foreign function interface facility and a C API which allows an experienced programmer to control SHIFT simulations from C and C++ programs.
6. As a matter of fact, many constructs and compilation policies could be optimized away by some rather simple data flow analysis. However, this has not been so far the emphasis of our work.
7. The choice to use a client server architecture for the GUI was based on two considerations. (1) The development of the GUI could progress rather independently of the development on the SHIFT compiler and runtime. (2) It was recognized since the early design stages that SHIFT simulations could require huge memory spaces: hence the necessity to being able to run simulation remotely on powerful workstation while interacting with them on a local -- and less powerful -- machine.
8. The term "autonomous" is here intended in the following sense: a vehicle/driver which takes decisions based only on its sensor input and on certain assumptions on the behavior of nearby vehicles. The high automation characteristic can be thought of as modern Adaptive Cruise Control technology.
9. However, the slow down is due mainly to the current implementation of sets in SHIFT. New tests will be performed with a new implementation which will improve on the memory usage of the internal data structures.
10. Mostly, I/O routines for the uploading of the engine model data.
11. Which includes all the necessary development hooks, GUI hooks, C API and Foreign Function Interface.