Hybrid Control in Sea Trac Management Systems John-Morten Godhavn, Trygve Lauvdal and Olav Egeland The Norwegian Institute of Technology N-7034 Trondheim, Norway John.Morten.Godhavn, Trygve.Lauvdal,
[email protected]
Abstract. Increasing trac on highways and in the air has in the re-
cent years motivated the design of hierarchical hybrid control systems. In this paper we will propose a hierarchical hybrid control system for the control of trac on sea, a Sea Trac Management System (STMS). The motivation is to reduce delays and improve the eciency and safety in increasingly overcrowded harbors, busy straits and narrow areas on sea. A controller unit on land plans the whole trac scenario, and interacts with advanced (hybrid) autopilots placed on each ship. A system as described above should take advantage of the new available technology, such as satellite based navigation (GPS-systems), digital sea maps, faster and more powerful computers, and more and better actuators.
Keywords: Hierarchical Hybrid Control, Sea Trac Management, Autopilot.
1 Introduction In some busy harbors of today there exists systems for trac control and surveillance. Most ships of today are at the same time equipped with some kind of autopilot. In this paper we will propose a way to combine these two kinds of systems into one control system. Every aspect of the motion of every ship in a limited area on sea will then be controlled by this system. To do this, the land based unit must be modi ed, the autopilots on board each ship must be made more advanced and hybrid, and we need a fast communication link between the ships and the landbased unit. We will propose a solution with a hierarchical structure, de ne what should be taken care of on each level in this structure, and how the di erent levels interact. A system with no human interaction as described in this paper is not realistic to be implemented within many years from now. The captain of the ship must at least be able to control the ship manually when something fails. Laws and regulations on sea must also be changed signi cantly in order to make an all automatic solution legal. An important issue for safety is redundancy, i.e. if some component fails, then there should exist a backup component to take over. The captain of the ship is the backup for the overall control of the ship.
The present set of tools for analysis of hierarchical hybrid systems is not satisfactory. The discrete part alone can be analyzed by existing methods in computer science. Likewise is it possible to analyze the continuous subsystems by wellestablished tools of control engineering. Simulations of hybrid systems can be used to identify problems, but simulations can of course not be used to veri cation or to prove stability. Technical advances that can make an STMS a reality include the availability of todays fast and relative inexpensive real time computers on board ships and in the land based Sea Trac Controller (STC). Knowledge of local conditions and regulations can be programmed into computers so that the need of pilots (people) with this knowledge can be relaxed. Improved navigation equipment as GPS measuring systems allows more exact tracking and detailed digital sea maps allows safer and more exible route planning. Ships built in the latest years are also often equipped with more actuators than the standard propeller-rudder combination. This gives a larger feasible set of trajectories, which should be utilized by the STC in narrow areas on sea. Todays system involve the use of sea lanes, i.e. dedication of broad routes on sea for the ships. These sea lanes are not very ecient and not optimal. The result is both planned and unplanned delays in sea travel. The potential improvement of both the safety and the performance is great if the STC and the autopilots on board cooperate continuously.
2 Proposed Architecture A hierarchical structure has to be utilized due to the high complexity with both a great number of control decisions (Discrete events) and a multiple set of low-level control laws (Continuous systems). A possible hierarchical control architecture for an STMS is shown in Fig.1.
2.1 Sea Trac Controller The STC is a discrete event control unit responsible for monitoring, coordination, and scheduling. This controller is the only part which is not placed on board the ships. Overall safety and performance is taken care of on this level. The STC monitors the motion of the ships with its own position sensors, which typically is a set of radars. The actual commands from the STC are packages with a sequence of via-points to each ship. A via-point is a set of coordinates (x ; y ) and a time interval [t min; t max ]. The ships should then reach the given via-points within the given time intervals. These sequences of via-points ensure safety, i.e. if all ships cross their via-points, then collision should be avoided. This implies that an increasing number of ships will demand an increasing number of via-points per ship (see Fig. 2). If it is impossible for the ship to follow the required path, then the autopilot renegotiates with the STC. i
i;
i;
i
Sea Traffic Control
Via points Coordination with other ships
Negotiations
Tactical Planner
Control modes
Rescheduling
Trajectory Planner Reference
Replanning
Regulation Layer Controls
Measurements
Physical Layer
Fig. 1. Architecture of the STMS control system. 2.2 Tactical Planner A detailed tactical plan is generated from the information given by the STC. A tactical plan takes the via-points and partitions the route into segments with di erent control modes. Typical control modes are: { Conventional mode: constant speed along straight lines or parts of circles (or more advanced motion). { Speed mode: Change speed, most often during straight line motion. { Stop-on-track mode: Stop ship and hold position. This is called Dynamic Positioning (DP) in the ship control literature.
C
B
D
Via-points
STC A
Fig. 2. Scenario for STMS: The gure shows ship A on its way to the quay, ship B wants to go through the strait, ship C is leaving the quay, and ship D wants to go from the strait and out to open sea. The STC has given several via-points to each ship in order to make this possible. { Come alongside quay (CAQ) mode: Special trajectories for approaching the
dock, could be a nonholonomic problem. An automaton for the Tactical Planner is shown in Fig. 3. Simpli ed mathematical models, such as kinematical models with bounds on velocities and turning radius, will be used in the construction of the tactical plan. Water current might be considered here by considering relative motion, i.e. compensate for the constant part of the water current in planning on this level. The via-points generated by the STC have to be very dense to guarantee safety. To reduce the workload and to increase the exibility of the system, it is desired that only a limited number of via-points are considered for regular trac. Some protocols (rules) for collision avoidance are hence necessary for the Tactical Planner. The autopilots on board should be able to detect and solve possible con icts without involving the STC. This feature is critical if e.g. the STC has a power failure. When maneuvers are aborted, the Tactical Planner renegotiates via-points with the STC. The Tactical Planner is a discrete event system (DES).
Conventional Straight
Idle
Turn
Change Speed
Switching points Via-points
CAQ
DP
Initial point
Fig. 3. Tactical Planner Automaton: The gure shows how the Tactical Plan-
ner assigns straight lines and circles so that the ship passes through the given via-points, and where the autopilot switches control mode along the trajectory.
2.3 Trajectory Planner Trajectory planning is done on this level. A smooth reference trajectory is generated, where performance limitations of the ship and other aspects such as passenger comfort and fuel consumption are considered. If a trajectory satisfying some ship dependent conditions is impossible to obtain, rescheduling is requested from the Tactical Planner. This is repeated until a feasible trajectory is found. A detailed dynamical model of the ship with disturbances and input saturation limits is considered. The Trajectory Planner is a hybrid system, since it deals with both discrete (control modes) and continuous time (smooth trajectories) signals.
2.4 Regulation Layer The trajectory generated on the previous level is fed to the Regulation Layer. Individual robust linear or nonlinear controllers are then applied for the di erent control modes. Each of these controllers has its own set of active and inactive actuators and measurements. One possible solution of stabilizing the system around a feasible trajectory is described in [9], where a time varying linear control law exponentially stabilizes the system locally. If the error grows outside the stable part of the statespace, then a new trajectory should be requested from the Trajectory Planner. Controllers are switched when entering a new control mode. These switches are dicult to analyze, but in this case most of the switches are predictable (time-
dependent), and there is a limited number of them. If the controller is unable to stabilize the ship along the trajectory, due to e.g. rudder saturation, a new trajectory is requested from the Trajectory Planner.
3 Similarities to and Di erences from ATMS The architecture here is motivated by the one proposed by prof. Sastry and his group at the UC Berkeley Robotics Lab for Air Trac Management Systems (ATMS) [8]. This makes sense since the control of an airport and a harbor has several similarities. Both systems have to serve a large number of customers who want access a limited set of resources. The objectives are eciency and safety. Typically there is a higher number of agents on an airport for some period of time, but on the sea each object stays for a longer period of time and thus have to be supervised longer. The geometry is simpler in a sea area since we then operate in only three degrees of freedom (DOF) instead of six. However, with only three DOF a severe limitation of space is the result. In the air planes can be "put on top of" each other and several trajectories can "cross" in (x; y)-coordinates without any danger. In addition they have a greater speed and thus their trajectory is released quicker. This is not the case in an area on sea, e.g. if a ship has been allocated to a trajectory and runs at a very low speed, other ships has to be allowed to cross this trajectory before the ship reaches the via-point. Thus time is an important parameter for the STC when approval is given to a ships via-points. Otherwise optimality is unreachable. Also ships can wait, while airplanes can not stand still in the air, they need space to do circles in the air while waiting. Due to the simple geometry, interagent coordination (i.e. identifying neighbor ships) is much simpler in an STMS architecture than in an ATMS architecture. Other related work is done on Intelligent Vehicle Highway Systems (IVHS), see e.g. [5] and the references therein.
4 Planning and Controller Design The way to an implemented system of the type mentioned above is very long and challenges appear at several levels. Some of these challenges are described below.
4.1 Collision Avoidance We propose that this problem should be shared between the STC and the ships. The STC should be responsible for keeping the total number of ships in the
crowded area small enough and the ships distributed around so that collision avoidance is achievable, while the autopilot on board each ship should have procedures for collision avoidance on a lower level. The help from the STC makes it necessary to consider only a limited number of di erent potential con ict scenarios. In most systems of today ships take care of this problem by themselves in a decentralized matter. Smaller, faster, and ships coming from the left must yield, is the main rule. In most cases this is sucient, since most ships are moving with low speed. However, with the new high speed vessels, the need for more advanced controllers arises to maintain an acceptable level of safety on sea.
4.2 Tactical Planning Based on the via-points received from the STC the automatic Trajectory Planner should make an optimal trajectory in order to interpolate them. There are several possibilities, e.g. shortest distance through the points. The work of L. E. Dubins [3] applies directly to generating paths of minimal length in the plane for vehicles moving only in the forward direction with a constraint on average curvature. The theorem says that the planar curve of minimal length consists of an arc of an circle, a straight line and an arc of an circle. This result can be used by the Tactical Planner. A more general approach for the planning of a trajectory seems to be a minimization of an optimal criterion: Z L(x( ); u( ); )d (1) J = T
0
where L() is some criterion for optimality, x( ) is the state vector and u( ) is the actuator vector. The weighting coecients will vary from ship to ship based on priorities, e.g. a tanker will prefer a fuel optimization criterion while a high-speed passenger vessel will prefer a comfort criterion. Optimization with respect to a fuel consumption criterion seems to be of limited interest done within a small area, but signi cant when a trajectory is planned over a long distance. Thus an STMS covering a large area has a great potential for fuel reduction just by including via-points with a time speci cation. This is due to the fact that the water resistance of the ship does not increase linearly with respect to speed, and that the fuel consumption on a distance L with optimal speed, is smaller than if the same distance is covered with a larger speed. Thus the autopilot can plan the speed necessary to arrive at the quay in time to get the desired resources and does not have to speed up in order to try to reach the destination within a speci ed time if the resource is available at a more suitable (later) time. Environmental disturbances which are predictable, e.g. slowly varying water current, should be compensated for on this level. This can be done by considering the notion of relative motion. This can be explained by looking at the kinematical
model of a ship under the in uence of constant water current: x_ = u cos ? v sin + W y_ = u sin + v cos + W (2) _ =r where (x; y) are position coordinates in an earth- xed coordinate system, u is surge velocity (forward speed), v is sway velocity (sideways speed), is yaw angle (course angle) and r is angular velocity in yaw. W and W represent the water current velocities along the inertial x- and y-axes. The velocities u and v are relative to the water and not to the inertial frame. Then only variations of the water current have to be considered as a disturbance by the Regulation Layer. x y
x
y
4.3 Trajectory Planning The somewhat coarse trajectory proposed by the Tactical Planner is modi ed on this level by considering a more detailed dynamical model of the ship including disturbances and actuator saturation limits. The dynamical model can be written on the form 2 3 u d 4 v 5 = f (u; v; r; ; X; d) (3) dt r
where the control inputs for this ship are the rudder and the propeller X , and the external disturbances are represented by d.
4.4 Regulation The classical ship autopilot has only one objective and that is to make the ship track a desired yaw angle. The disadvantage of this approach is the following; if the ship is traveling a large distance from (x1 ; y1 ) to (x2 ; y2 ), the course has to be changed several times because a small deviation from the correct angle result in a large error. The actual trajectory is then intuitively not optimal with respect to any criterion and thus unsatisfactory for an STMS. However, some ships have an additional controller with position feedback and can track a straight line between the two points. The traditional task of trajectory tracking is simple because it only consists of a straight line until a new line is de ned (in addition the ship speed is approximated constant). Thus switching between the two control modes are only done on a limited number of occasions. The traditional trajectory cannot be compared with the trajectory in an STMS. The trajectories in this system are more complex due to the possibility that it may include maneuvers as stop on track, change speed and come alongside quay. As a consequence switching between the control modes becomes an important issue and must be considered further.
4.5 Description of Control Modes The di erent control modes introduced are described. Implemented solutions and unsolved problems are discussed.
Course Keeping and Course Changing In a ship autopilot designed for
trajectory following, these two control objectives belongs naturally together and will be considered as one control mode in the STMS. However, in conventional autopilots they are divided into two separate modes due to the complexity of the controller under course changing. This control strategy is called cross-tracking. Another trajectory following principle (see [6] for details) is called Line of Sight (LOS) and is based on way points which, like the via-points, are sets of coordinates given in an earth- xed frame. The problem with the LOS algorithm is that only the yaw-angle is controlled (not the position). Some timing must also be included to be a good solution of the tracking problem in an STMS.
Course Keeping Standard course-keeping autopilots are easily implemented
on ships and there are several approaches to solve this task. In the literature course keeping autopilots range from simple PID-controllers, to more sophisticated non-linear controllers, e.g. feedback linearization. However these autopilots can only maintain the desired course angle, and in trajectory tracking one has to guarantee that the ship does not run in parallel with the trajectory. Thus an outer control loop is necessary to ensure that the ship follows a given path. This is not implemented on all ships. A conventional tracking system today is usually designed by rotating the earth xed coordinate system, neglecting the sway mode, and assuming constant ship speed, to obtain the simpli ed kinematics: y_
=U +d
(4)
y
where d is a slow-varying parameter describing errors due to linearization and environmental disturbances and U is a constant cruise speed. Thus the control objective is to ensure y = 0, and a simple PI-controller will guarantee tracking, i.e. Z = K y(t) + K y( )d (5) y
t
d
p
i
t0
will make the ship track a straight line between to points, (x1 ; y1 ) and (x2 ; y2 ) even with the presence of disturbances. However, with a speed controller in parallel the ship speed U is not necessary constant and correction to changes in speed has to be made to ensure acceptable tracking under speed changes. This is usually done by gain scheduling with respect to ship speed.
Course Changing When a ship track a circular trajectory the kinematics
introduce a control problem due to its nonlinear nature. The solution to this problem is an additional controller rotating the earth- xed coordinate system the desired angle at every sample. Thus the arguments in the previous section can be transfered and an extra controller rotating the earth- xed coordinate system is introduced. Thus the course keeping controllers guarantee asymptotic tracking also of the circular trajectory. Further research is necessary to develop nonlinear control laws.
Speed Control Due to the time speci cation related to position (x; y) ship
speed control with acceptable accuracy is an important issue in an STMS. The ship speed equations of motion are highly nonlinear di erential equation. To obtain maximum accuracy a nonlinear control law should be implemented. For details see [4]. Nonlinear speed controllers are commercially available, and no research is necessary. However far from all ships have this kind of controller installed and speed regulation is often based on radio communication from the bridge to the engine room.
Dynamic Positioning In order to control a ship in three DOF, extra thrusters
are required in addition to the rudder and a propeller in the main direction. Two controls and three DOF gives what we call an underactuated control system. This problem is similar to the well known parking problem for a wheeled vehicle. It can be shown that no continuous static state feedback can stabilize such systems. Either discontinuous or time varying feedback have to be applied, as it is done in control of nonholonomic systems (see e.g. [7]). If a ship with this equipment is required to maintain its position (DP), an advanced controller is required. The dynamic positioning of an under-actuated ship does not have the same accuracy due to the fact that motion in surge is required to stabilize the ship. Systems for dynamic positioning (DP) are commercially available and present no problem in the STMS if only ships with extra thrusters are allowed to enter the area. See e.g. [4] and [1] for details on two di erent approaches to the problem of DP systems. A dynamic positioning system is based on controlling the forces in x- and y-direction and moment round the z-axis. Since most ships have more thrusters than degrees of freedom there are several ways of allocating the thrusters, and an optimal thruster allocation algorithm is not available.
Come Alongside Quay The task of automatic control the ship to quay is
not very challenging if the ship is equipped with the necessary thrusters, i.e. the same equipment needed for dynamic positioning. The autopilot needs an extra set of sensors with very good accuracy and there has to be equipment on land which indicates where the ship is going to be secured. Except from the extra
equipment a DP control system can easily be extended to an automatic CAQ system. This kind of control system is however not commercially available, but is expected to be so within few years.
4.6 Requirements It is required that all ships which enter the controlled area on sea has an advanced hybrid autopilot on board, which can be controlled remotely from a land based unit. The autopilot must include all the modes described above. Especially all ships need a speed controller, something which is not the case today, where speed control often is done by radio communication between the bridge and the engine room.
4.7 Hybrid Control Issues From the continuous point of view the di erent discrete events present interrupts of the continuous control. One example of this is when two ships come to close, where \to close" is modeled by a safety area dependent on distance in x- and ydirection and the relative speed and acceleration of the ships in these directions. Then an alarm procedure is initiated in the Tactical Planner. If via-points have to be changed, then the changes must also be approved by the STC. From the discrete point of view the dynamics and kinematics of the ships present disturbances which partially are unpredictable. The DES does not know what will happen at what time. E.g. failure in the engine of one ship may cause a total replanning.
4.8 Stability and Performance The individual autopilots are assumed to give sucient local stability and performance properties while working in continuous mode, i.e. between the switches. Stability problems may however appear when control modes are switched. But on sea the time between each switch is typically very long compared to the time of (practical) convergence of each autopilot, i.e. we assume the control deviation is small in every switch. Then old control modes will in most cases not interact with new, and each control mode may be analyzed individually. Stability of the continuous part seems therefore to be achievable, although the switching problem has to be considered in more detail. Stability and performance of the total STMS is hard to analyze, and the present tools are not satisfactory. While waiting for appropriate tools to be developed, simulations are used. Some work has been done on stability analysis of switched systems by e.g. [2].
5 Final Remarks The goal with an STMS is to reduce the time spent by each ship inside the crowded area on sea. More cost-ecient, reliable and predictable trac is what we are looking for. Solutions to many of the control problems exist, e.g. autopilots for di erent operations on sea in [4], and many are available commercially today. Similarly there exists manual systems for sea trac control in some busy areas on sea (e.g. Brevikstr mmen in Norway), and there exists several systems for anti collision on sea (e.g. in The Oslo Fjord). The hybrid challenge is to combine these two kinds of systems together into one hierarchical control system that takes care of both safety and performance.
References [1] Balchen, J. G., Jenssen, N. A., Slid, S.: Dynamic Positioning of Floating Vessels Based on Kalman Filtering and Optimal Control. Proceedings of the 19th IEEE Conference on Decision and Control (1980) 852{864. [2] Branicky, M. S.: Stability of Switched and Hybrid Systems. Proc. of the IEEE Conf. Decision and Control (1994) 3498-3503. [3] Dubins, L.E.: On curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents. American Journal of Mathematics, 79:497{516 (1957). [4] Fossen, T. I.: Guidance and Control of Ocean Vehicles. John Wiley and Sons Ltd. (1994). [5] Godbole, D. N., Lygeros, J.: Longitudinal Control of the Lead Car of a Platoon. IEEE Trans. Vehicular Techn. vol 43 nr 4 (1994) 1125-1135. [6] Healey, A. J., Lienard, D.: Multivariable Sliding Mode Control for Autonomous Diving and Steering of Unmanned Underwater Vehicles. IEEE Journal of Ocean Engineering vol OE-18 nr 3 (1993) 327{339. [7] Murray, R. M., M'Closkey, R. T.: Exponential Stabilization of Driftless Nonlinear Control Systems using Homogeneous Feedback. CDS, Tech. Report nr 95{012, Caltech (1995). [8] Sastry, S., Meyer, G., Tomlin, C., Lygeros, J., Godbole, D., Pappas, G.: Hybrid Control in Air Trac Management Systems. UC Berkeley Memo UCB/ERL M95/82 October 1995. [9] Walsh, G., Tilbury, D., Sastry, S., Murray, R., and Laumond, J.-P.: Stabilization of Trajectories for Systems with Nonholonomic Constraints. IEEE Transactions on Automatic Control, January, 1994. This article was processed using the LATEX macro package with LLNCS style
