Work Packages

The HYBRIDGE project includes the following technical work packages:

WP no.

Work Package description

WP Leader

Organisation

WP0 Final report Henk Blom NLR

WP1

Identification and modelling of uncertain hybrid systems

John Lygeros

UCAM/UPAT

WP2

Stochastic hybrid systems based modelling of accident risk

Henk Blom

NLR

WP3

Reachability analysis for probabilistic hybrid systems

Maria Prandini

UniBs

WP4

Compositional specification of stochastic hybrid systems

Arjan van der Schaft

TWEN

WP5

Control of uncertain hybrid systems

Jan Maciejowski

UCAM

WP6

Decentralized conflict prediction and resolution

Kostas Kyriakopoulos

NTUA

WP7

Error evolution control

Maria DiBenedetto

AQUI

WP8

Accident risk decomposition

Arun Bagchi

TWEN

WP9

Perform risk assessment of distributed control system

Henk Blom

NLR

WP10

Develop advanced risk assessment course

Henk Blom

NLR


Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP0: Final report

Leader: Henk Blom (NLR)

Followers: AQUI, UCAM, UPAT, TWEN, NTUA, UniBs, BAES, CENA, INRIA, AEAT

Objectives:

Consolidation of key HYBRIDGE results in an edited volume of papers.

Project Deliverables:

Id

Title

Date

Version

[Final]

HYBRIDGE Final Project Report by H.A.P. Blom and J. Lygeros (Editors)

April 2005

Final



Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP1: Identification and modelling of uncertain hybrid systems

Leader: John Lygeros (UCAM/UPAT)

Followers: UniBs, NTUA, AQUI, NLR, BAES, EEC

Objectives:

Develop modelling and system identification methods for stochastic hybrid systems. Identify a realistic multi-aircraft model from air traffic control data. Generate simplified models suitable for performing conflict prediction and resolution, both centralised (at the air traffic control level) and decentralised (on board the aircraft).

Work Description:

Task 1.1: Make a shortlist of operational cases where safety is a key issue when air traffic density increases, including a global identification of the main bottlenecks. Dense traffic operational cases will be identified for en-route, in the terminal manoeuvring area, around closely spaced runways and at the airport surface. These operational cases will be used to keep the work in other work packages focused on distributed control issues that are of key importance for the application in mind.

Task 1.2: Develop a modelling framework for stochastic hybrid systems. The framework will allow one to capture the interaction of discrete and continuous dynamics and uncertainty, in the continuous evolution, discrete transition times and discrete transition destinations. The model development will focus on the distributed nature of air traffic management.

Task 1.3: Identify a detailed multi-aircraft model, to be used as a "real world" for validating subsequent algorithms. Because of the interaction between stochastic and hybrid dynamics, conventional system identification methods are insufficient for this task. In the process, we will therefore develop new system identification results for dealing with this class of stochastic hybrid systems.

Task 1.4: Deduce simplified models, on which conflict prediction and resolution algorithms can be based. Model reduction will strike a balance between on the one hand tractability and computational efficiency and on the other accuracy and validity. Different models will be developed for different conflict detection and resolution approaches. The process will be iterative: the models will be tuned until the performance of the algorithms based on them is deemed acceptable.

Task 1.5: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D1.1]

Safety relevant operational cases in air traffic management by O.J. Watkins and J. Lygeros

November 2002

Final

[D1.2]

A Stochastic Hybrid System Modeling Framework by
M.L. Bujorianu, J. Lygeros, W. Glover and G. Pola

May 2003

Final

Papers published:

Id

Title

Date

Version

[R1.1]

Aircraft and weather models for probabilistic collision avoidance in Air Traffic Control, by J. Lygeros and M. Prandini

August 2002

Preprint for
IEEE CDC 2002

[R1.3]

Diagnosability of hybrid systems, by G.K. Fourlas, K.J. Kyriakopoulos and N.J. Krikelis

March 2002

Preprint for
MED 2002

[R1.5]

Interval predictors for unknown dynamical systems: an assessment of reliability, by G. Calafiore and M.C. Campi

August 2002

Preprint for
IEEE CDC 2002

[R1.6]

Switching control of stochastic linear systems: stability and performance results, by Maria Prandini (Invited session "Hybrid control and applications")

March 2002

Preprint for
SIMAI 2002

[R1.9]

Stochastic hybrid models: An overview by G. Pola, M.L. Bujorianu, J. Lygeros and M.D. Di Benedetto

April 2003

Preprint for ADHS 2003

[R1.10] A stochastic hybrid model for air traffic control simulation by W. Glover, J. Lygeros
September 2003 Preprint for HSCC 2004
[R1.12] Piecewise affine systems identification: a learning theoretical approach by M. Prandini
July 2004 Preprint for CDC 2004
[R1.13] Non-asymptotic quality assessment of generalised FIR models with periodic inputs by M.C. Campi, Su Ki Ooi and E. Weyer December 2004 Automatica, Vol. 40, Issue 12, Pages 2029-2041

Complementary papers and reports

Id

Title

Date

Version

[D1.3]

A Multi-Aircraft Model for Conflict Detection and Resolution Algorithm Evaluation by W. Glover and J. Lygeros

February 2004

Final

[D1.4] Simplified Multi-Aircraft Models for Conflict Detection and Resolution Algorithms by W. Glover, J. Lygeros September 2003
Final

 
Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP2: Stochastic hybrid systems based modelling of accident risk

Leader: Henk Blom (NLR)

Followers: TWEN, CENA, AQUI, UCAM, UPAT, INRIA

Objectives:

The objective of this work package is to characterise main types of accident risks in air traffic management in stochastic hybrid systems framework. Examples of accident risk in air traffic management are risk of collision with another aircraft or with an obstacle, risk of controlled flight into terrain and wake vortex induced accident risk. For air traffic management these risks are intertwined with the stochastic hybrid systems nature of air traffic management. The mathematical characterisation of these risks in stochastic hybrid systems terms allows one to study the stochastic analysis and control of these risks.

Work Description:

There are two natural classes of non-linear continuous-time stochastic hybrid dynamical systems still admitting theoretical analysis. One is formed by Piecewise Deterministic Markov Processes (PDMP), and the other is formed by Stochastic Differential Equations (SDE's) on Hybrid State Spaces. In comparison with SDE’s the strong point of PDMP is that they allow predictable jumps. However the strong point of SDE’s is that they allow Brownian motion in the model. For accident risk modelling in air traffic management both properties are very useful, e.g. the Brownian motion model is required to model random motion of aircraft due to e.g. variations in wind, while the PDMP model is required to model switches in control modes such as due to conflict prediction and resolution. The accommodation of all these needs is organised in four tasks:

Task 2.1: Develop accident risk equations in air traffic management which capture the two natural sides of accident risk: frequency and severity of accident event. At least the following risks will be covered: risk of collision with an obstacle, risk of collision with terrain, risk of mid-air collision between two aircraft under different airspace structures, risk of near mid-air collision between two aircraft, risk of collision between two aircraft on the airport.

Task 2.2: Accident risk modelling for SDE on hybrid state space. The accident risk equations of Task 1 will be combined with the stochastic analysis framework of SDE driven by Brownian motion and Poisson random measure, with as key outcome a mathematical characterisation of accident risk in terms of the extended generator characteristics of such SDE and the strong Markov property.

Task 2.3: Extend accident risk modelling to include the predictable instantaneous jumps of PDMP. The accident risk model of Task 2.2 will be extended with the stochastic analysis framework of PDMP, with as key outcome a mathematical characterisation of accident risk evolution in terms of the extended generator characteristics and the strong Markov property.

Task 2.4: In this task a Petri net formalism is developed which allows a systematic development of a PDMP/SDE model for the application at hand. Through mathematical proof it will be shown that a strict adherence to this Petri net formalism always yields a model instantiation which falls within the class of PDMP/SDE processes characterised in Task 2.3.

Task 2.5: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D2.2]

Stochastic analysis background of accident risk assessment for Air Traffic Management by Henk Blom, Bert Bakker, Mariken Everdij, Marco van der Park

July 2003

Final

[D2.3]

Generalised stochastic hybrid processes as strong solutions of stochastic differential equations by J. Krystul and H.A.P. Blom

May 2005

Final

[D2.4]

Modelling hybrid state Markov processes through Stochastically and Dynamically Coloured Petri Nets by M.H.C. Everdij and H.A.P. Blom

May 2005

Final

Papers published:

Id

Title

Date

Version

[R2.1]

Conflict probability and incrossing probability in Air Traffic Management by H.A.P. Blom and G.J. Bakker

August 2002

Preprint for
IEEE CDC 2002

[R2.3] Stochastic hybrid processes with hybrid jumps by H.A.P. Blom April 2003 Preprint for ADHS 2003
[R2.7] Modeling stochastic hybrid systems by M.K. Ghosh, A. Bagchi January 2004 Preprint for IFIP TC-7 book version
[R2.8] Petri-nets and hybrid-state Markov processes in a power-hierarchy of dependability models by M.H.C. Everdij and H.A.P. Blom April 2003 Preprint for ADHS 2003
[R2.9] Collision risk modeling of air traffic by H.A.P. Blom, G.J. Bakker, M.H.C. Everdij and M.N.J. van der Park
July 2003 Preprint for ECC 2003
[R2.14] Theoretical foundations of stochastic hybrid systems by M.L. Bujorianu and J. Lygeros May 2004
Preprint for MTNS 2004
[R2.15] Piecewise Deterministic Markov Processes represented by Dynamically Coloured Petri Nets by M.H.C. Everdij and H.A.P. Blom February 2005
Stochastics, Vol. 77, 2005, Issue 1, Pages 1-29

Complementary papers and reports

Id

Title

Date

Version

[C2.1]

Mathematical modelling of bias and uncertainty in accident risk assessment by H. Nurdin

June 2002

Master Thesis

[C2.2] Extended Stochastic Hybrid Systems and Their Reachability Problem by M.L. Bujorianu
2004 Preprint for HSCC 2004
[C2.3] General Stochastic Hybrid Systems by M.L. Bujorianu and J. Lygeros 2004 Preprint for MED 2004

 

Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP3: Reachability analysis for probabilistic hybrid systems

Leader: Maria Prandini (UniBs)

Followers: UCAM, NTUA, CENA, AQUI, NLR, EEC

Objectives:

Development of a method for the computation of the probability that a hybrid system trajectory enters a pre-specified set and for the assessment of the system performance in terms of, e.g., average time to reach a certain set, and application of this method to aircraft conflict detection. The objective is developing conflict detection algorithms for supporting both pilots and air traffic controllers in ensuring that conflicts - i.e., situations where two aircraft come closer than a minimum allowed distance - do not occur.

Work Description:

Task 3.1: Reachability Analysis and Performance Evaluation for probabilistic hybrid systems. In a probabilistic framework, the reachability problem consists of determining the probability that the system trajectories enter some prespecified set starting from some probability distribution on a certain set of initial conditions. Developing a methodology for the reachability analysis of probabilistic hybrid systems will then involve dealing with two aspects: 1) the theoretical aspect of introducing a stochastic process that assigns a unique probability to the reachability event; 2) the computational aspect regarding how to estimate the probability of the reachability event and to quantify the level of approximation introduced. Randomized methods will be used to solve the computational aspect. Randomized algorithms will also be proposed to evaluate the system performance in terms of quantities such as, for example, the average time to reach a certain set.

Task 3.2: Aircraft Conflict Detection. The algorithms developed in Task 3.1 will be applied in an air traffic context. Here, the reachability problem of interest consists of determining the probability of conflict, i.e., the probability of the hybrid system reaching an unsafe set where two aircraft come closer than a minimum allowed distance. An alert will be issued if the probability of conflict exceeds a certain threshold. Criticality measures other than the probability of conflict and the ones proposed in the literature (e.g., incrossing risk, minimum pairwise distance, time to minimum pairwise distance, etc.) will also be proposed, in the attempt of taking explicitly into account the human-in-the-loop component. The performances achieved by detection algorithms incorporating different criticality measures will be compared by using Monte Carlo simulations and the validation model from WP1. The possibility of resorting to different models for short-term conflict detection, performed on board of the aircraft by the Flight Management System over a time horizon of seconds to minutes, and mid-term conflict detection, performed by air traffic controllers over horizons of the order of tens of minutes, will be considered. The interaction between the alert systems on board of the aircraft and on the ground, respectively assisting pilots and air traffic controllers, will be studied.

Task 3.3: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D3.1]

Reachability Analysis for Probabilistic Hybrid Systems with Application to Air Traffic Management by M. Prandini and M.C. Campi

November 2004

Final

[D3.2]

Probabilistic aircraft conflict detection by M. Prandini and O J. Watkins

May 2005

Final

Papers published:

Id

Title

Date

Version

[R3.6] On Reachability and Minimum Cost Optimal Control by J. Lygeros June 2004 Automatica, Vol. 40, 2004, Issue 6, Pages 917-927
[R3.8] Minimum Cost Optimal Control: An Application to Flight Level Tracking by J.Lygeros
April 2003 Preprint for MED 2003
[R3.9] Stochastic Reachability for Discrete Time Systems: An Application to Aircraft Collision Avoidance by O.J. Watkins and J.Lygeros
September 2003 Preprint for CDC 2003
[R3.13] Invariant measure of stochastic hybrid processes by C. Yuan and J. Lygeros
September 2004 Preprint for CDC 2004
 
Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP4: Compositional specification of stochastic hybrid systems

Leader: Arjan van der Schaft (TWEN)

Follower: AQUI, UCAM, UPAT, NLR, INRIA

Objectives:

Stochastic hybrid dynamical systems naturally come up in the modelling of many real-life systems, including air traffic management systems. Usually these systems are of an inherently complex nature, involving many subsystems interacting with each other. Main aim is to develop a compositional formalism for the specification of stochastic hybrid dynamical systems, which allows to unambiguously specify the complex system from its constitutive parts and to employ formal and analytic methods in the analysis and control of the resulting complex system.

Work Description:

A natural class of non-linear continuous-time stochastic hybrid dynamical systems still admitting theoretical analysis is formed by Piecewise Deterministic Markov processes (PDMP). In particular, the dynamics of these systems can be expressed by an extended generator leading to a generalised Dynkin formula. In this work package a compositional formalism for the specification of complex PDMP from small-scale models, based on process algebras, will be developed. Scalability with complexity deserves particular attention. The research will benefit from very recent work on the process-algebraic specification of timed, hybrid, and stochastic automata. Apart from the specification and performance analysis of complex stochastic models arising in air traffic management systems such a framework is also expected to support Collaborative Decision Making (between airlines, ATC, airports, meteo, pilots, etc.). The work is organised in four tasks:

Task 4.1: Develop process algebraic specification of PDMP.

Task 4.2: Comparison with other frameworks

Task 4.3: Develop semantic models

Task 4.4: Study control theoretic properties

Since the first part of the work package is concerned with the general modelling, formal analysis and representation of stochastic hybrid dynamical systems, there is a connection with all the other work packages. Special connection is envisioned with the work packages on Model Identification and Predictive Control (WP1), Error evolution control (WP7) and Accident risk modelling (WP2). The connection with WP7 and WP2 will take place in the use and analysis of PDMPs for the description of stochastic hybrid systems. The relation with WP1 will be in the modelling of stochastic hybrid systems and their control.

Task 4.5: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D4.2]

CPDP: A compositional framework for stochastic hybrid systems of the PDP type by S.N. Strubbe and A.J. van der Schaft

February 2004

Final

[D4.3]

Semantics, bisimulation and interaction-structures for the CPDP model by S.N. Strubbe and A.J. van der Schaft

December 2004

Final

[D4.4]

On Control of Complex Stochastic Hybrid Systems by Stefan Strubbe, Jan Willem Polderman, Agung Julius and Arjan van der Schaft

April 2005

Final

Papers published:

Id

Title

Date

Version

[R4.1]

Achievable behavior by composition, by A.J. van der Schaft, A.A. Julius

August 2002

Preprint for
IEEE CDC 2002

[R4.2] Communicating piecewise deterministic Markov processes by S.N. Strubbe, A.A. Julius and A.J. van der Schaft April 2003 Preprint for
ADHS 2003
[R4.4] Stability analysis for hybrid automata using conservative gains by R. Langerak, J.W. Polderman and T. Krilavicius
April 2003 Preprint for
ADHS 2003
[R4.5] Control of hybrid behavioral automata by interconnection by A.A. Julius, S.N. Strubbe and A.J. van der Schaft April 2003 Preprint for ADHS 2003
[R4.8] Bisimulation of dynamical systems by A.J. van der Schaft October 2003 Preprint for HSCC 2004
[R4.11] Equivalence of hybrid dynamical systems by A. Van der Schaft
April 2004 Preprint for MTNS 2004
[R4.12] Balancing dwell times for switching linear systems by G. Pola, J.W. Polderman, M.D. Di Benedetto
May 2004 Preprint for MTNS 2004
[R4.13] Equivalence of dynamical systems by A.J. van der Schaft
December 2004 IEEE Transactions on Automatic Control, Vol. 49 Issue: 12, Pages 2160-2172
[R4.14] Bisimulation for General Stochastic Hybrid Systems by M.L. Bujorianu, J. Lygeros and M. Bujorianu
January 2005 Preprint for HSCC 2005
[R4.15] Bisimulation for Communicating Piecewise Deterministic Markov Processes
by S.N. Strubbe, A.J. van der Schaft
January 2005 Preprint for HSCC 2005
[R4.16] Stochastic equivalence of CPDP-automata and Piecewise Deterministic Markov processes by S.N. Strubbe, A.J. van der Schaft
October 2004 Preprint for IFAC World 2005
 
Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP5: Control of uncertain hybrid systems; conflict resolution

Leader: Jan Maciejowski (UCAM)

Followers: UPAT, NTUA, UniBs, BAES, EEC, NLR

Objectives:

Extend hierarchical and model predictive control techniques to stochastic hybrid systems. Use them to develop algorithms for assisting air traffic controllers and pilots with conflict resolution manoeuvres. Obtain theoretical guarantees for the performance of the algorithms and validate the results by Monte Carlo simulation.

Work Description:

ATM conflict resolution will be posed as a control problem. The conflict resolution tasks and advisories will be hierarchically decomposed. Conflicts will be resolved locally whenever possible. For cases where local resolution is infeasible or inefficient, co-ordination requirements will be derived. The co-ordination will be performed at the ATC level. Conflict resolution manoeuvres at this level will be determined by optimising a cost function over predicted aircraft trajectories in a model predictive control set up. The model will reflect the underlying ATM structure (WP1) as well as the action of decentralised controllers (WP6). The cost function will reflect the probability of conflict and practical issues, like passenger comfort, fuel consumption and the preferences of air traffic controllers and pilots. As usual in model predictive control, only the first action of the computed optimal solution will get implemented. The optimisation will be repeated if the conflict persists. A number of challenging problems, both theoretical and practical will be addressed in the process, which are organised in four subsequent tasks:

Task 5.1: Decomposing the conflict resolution task hierarchically, dealing with information sharing in he presence of uncertainty and establishing co-ordination requirements based on the decentralised controllers design.

Task 5.2: Encoding the requirements in the model predictive control framework. The problem formulation will not be the standard one. The controls enter discretely, and the dynamics are both hybrid and probabilistic. The MPC methodology will be extended to address these issues.

Task 5.3: The optimisation problem is likely to be computationally demanding. Randomised algorithms will be employed to obtain efficient estimates of the optimum and confidence bounds.

Task 5.4: Preferences of air traffic controllers and pilots need to be addressed in order to ensure that the resolution manoeuvres are acceptable to be implemented by the humans involved. Heuristics will be employed to guide the optimisation procedure in order to improve the computational performance. Monte Carlo simulation on the detailed multi-aircraft model of WP1 will be used to validate the theoretical predictions. The scalability of the results to more complex problems will be addressed.

Task 5.5: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D5.2] Model predictive control formulation of conflict resolution task by A. Lecchini, W. Glover, J. Lygeros, J. Maciejowski
July 2004 Final

[D5.4]

Monte Carlo conflict resolution algorithm with simulation examples by A. Lecchini, W. Glover, J. Lygeros, J. Maciejowski

April 2005

Final

Papers published:

Id

Title

Date

Version

[R5.1] Cautious hierarchical switching control of stochastic linear systems by M.C. Campi, J.P. Hespanha, M. Prandini May 2004 Int.Journal of Adaptive Control and Signal Processing, Vol. 18, Issue 4, Pages: 319-333
[R5.3] General Stochastic Hybrid Systems: Modelling and Optimal Control by M.L. Bujorianu and J. Lygeros
September 2004
Preprint for CDC 2004
[R5.4] Uncertain convex programs: randomized solutions and confidence levels by G. Calafiore and M.C. Campi
January 2005 Mathematical Programming, Series. A, Vol. 102: Pages 25–46
[R5.5] Air Traffic Control with an expected value criterion by A. Lecchini, W. Glover, J. Lygeros and J. Maciejowski March 2004 Preprint for IFAC World 2005
[R5.6] Air Traffic Control in approach sectors: Simulation examples and optimization
by A. Lecchini, W. Glover, J. Lygeros and J. Maciejowski
January 2005 Preprint for HSCC 2005

Complementary papers and reports

Id

Title

Date

Version

[D5.1]

Hierarchical Decomposition of Conflict Resolution Tasks by A. Lecchini, J. Lygeros and D. Dimarogonas May 2004 Final
[D5.3] Randomised algorithms and implementation by A. Lecchini, X. Papageorgiou, J. Lygeros, J. Maciejowski, K. Kyriakopoulos April 2005 Final

 

Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP6: Decentralized conflict prediction & resolution

Leader: Kostas Kyriakopoulos (NTUA)

Followers: UniBs, BAES, UCAM, NLR, EEC

Objectives:

Development of a probabilistic approach addressing airborne path-planning and conflict resolution approaches and in relation with possible strategies in co-ordination with the ground side of path-planning and conflict resolution. This development will bring into account dynamics that are: Continuous, e.g. arising from the physical motion of aircraft, Discrete, e.g. arising from the structure of the ATM process, and Stochastic, e.g. arising from environmental uncertainties, tracking, communication, data-consistence errors and differences in situational awareness.

Work Description:

For conflict detection and resolution many systems in the air and on the ground work together. Ground examples are at a strategic level scheduling and planning by airports, airlines and traffic flow management, and at a tactical level Flight Path Monitoring, Medium Term Conflict Detection, Short Term Conflict Alert and monitoring by the air traffic controller. Air examples are FMS, TCAS, ASAS and the pilots. Against this background, we study decentralised conflict resolution with the aim to improve the contribution of the airborne elements in this decentralized set up.

Task 6.1: First an inventory will be made of the various distributed conflict resolution systems and humans in air traffic management from a modelling, control and standard path-planning perspective.

Task 6.2: Subsequently, the problems these systems pose at the co-ordination level will be studied with emphasis on the key new issues posed to the standard path-planning problem in terms of modelling and control and the scalability with increasing complexity:

The dimension of the problem is increased and SO(3) kinematic models may be required.

The obvious tendency to use simple kinematic models for the motion of the aircraft has to be related with the corrupting noises coming from either the plant or the pilot's behaviour.

Conflict prediction techniques should be based on both the selected motion model and the uncertainty in the predicted collision time.

Local optimisation should be based on the model of motion and higher-level commands e.g. coming from air traffic control.

A supervisory integrated collision prediction and avoidance scheme has to be devised by considering all the agents flying within the space of an ATC.

The stability of the overall scheme has to be assessed by considering both the hybrid nature of the state space and the multiple scales of feedback.

Task 6.3: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D6.1]

Inventory of Decentralized Conflict Detection and Resolution Systems in Air Traffic by Dimos V. Dimarogonas and Kostas J. Kyriakopoulos

June 2003

Final

[D6.2]

Global Decentralized Conflict Resolution by D.V. Dimarogonas and K.J. Kyriakopoulos

March 2005

Final

Papers published:

Id

Title

Date

Version

[R6.1] Closed Loop Navigation for Multiple Non - Holonomic Vehicles by S.G. Loizou and K.J. Kyriakopoulos May 2003 Preprint for
ICRA 2003
[R6.2] Decentralized Motion Control of Multiple Holonomic Agents under Input Constraints by D.V. Dimarogonas, M.M. Zavlanos, S.G. Loizou and K.J. Kyriakopoulos September 2003 Preprint for CDC 2003
[R6.3] Decentralized Motion Control of Multiple Mobile Agents by M.M. Zavlanos and K.J. Kyriakopoulos February 2003 Preprint for MED 2003
[R6.4] Closed Loop Navigation for Mobile Agents in Dynamic Environments by S.G. Loizou, H.G. Tanner, V.Kumar, K.J. Kyriakopoulos September 2003 Preprint for IROS 2003
[R6.6] Lyapunov-like Stability of Switched Stochastic Systems by D.V. Dimarogonas and K.J. Kyriakopoulos
March 2004 Preprint for ACC 2004
[R6.7] Decentralized Feedback Stabilization of Multiple Nonholonomic Agents by S.G. Loizou, D.V. Dimarogonas and K.J. Kyriakopoulos
March 2004
Preprint for ICRA 2004
[R6.8] Decentralized Stabilization and Collision Avoidance of Multiple Air Vehicles with Limited Sensing Capabilities by D.V. Dimarogonas and K.J. Kyriakopoulos
March 2005 Preprint for ACC 2005
[R6.9] Automatic Synthesis of Multi-Agent Motion Tasks Based on LTL Specifications by S. Loizou and K.J. Kyriakopoulos
August 2004 Preprint for CDC 2004
[R6.10] Decentralized Motion Control of Multiple Agents with Double Integrator Dynamics by D.V. Dimarogonas and K.J. Kyriakopoulos January 2005 Preprint for IFAC World 2005
[R6.12] A Feedback Stabilization and Collision Avoidance Scheme for Multiple Independent Nonholonomic Non-point Agents by D.V. Dimarogonas and K.J. Kyriakopoulos March 2005 Preprint for MED 2005
[R6.13] Interesting Conjugate points in formation constrained optimal multi-agent coordination by J. Hu, M. Prandini, and C. Tomlin March 2005 Preprint for ACC 2005

Complementary papers and reports

Id

Title

Date

Version

[D6.2i]

Intermediate Report on Decentralized Conflict Resolution Algorithms by D.V. Dimarogonas and K.J. Kyriakopoulos October 2004
Final

 

Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP7: Error evolution control

Leader: Maria DiBenedetto (AQUI)

Followers: NLR, TWEN, BAES, EEC

Objectives:

Development of estimation methods and observer design techniques for stochastic hybrid systems, and the application of these methods to devise algorithms with guaranteed performances for assisting human operators in avoiding error propagation and controlling error evolution in distributed systems. This estimation is essential for the design of a control strategy for error recovery.

Work Description:

Task 7.1: Identify the specific error evolution control problems in air traffic management. The aim of this task is to develop an insight into the key problems of fault and error evolution in the widely distributed air traffic management, communication, navigation, surveillance and human decision making networks. This inventory allows to focus the follow up work towards the main issues of these distributed complex systems.

Task 7.2: Identification of a hybrid model which appropriately describes the dynamics involved in error evolution control and captures the key problems studied in Task 7.1. Development of estimation methods and observer design techniques for this class of stochastic hybrid systems. The objective is to establish how to combine classical techniques for discrete and continuous systems to develop an observation scheme for hybrid systems. A hybrid observer provides an estimate of the hybrid state (continuous and discrete) from the evolution of the hybrid inputs and outputs. Therefore, the objective is twofold: 1) Design of an observer for the continuous systems, and 2) Estimation of the discrete states using information provided by the continuous observer and the discrete structure of the hybrid system.

Task 7.3: Detecting human situational awareness errors. One of the key problems in distributed safety critical systems is that humans can have errors in their situational awareness, and these errors can than evolve into the system where they may create all kind of safety critical situations. Since direct observation of human situational awareness is impossible, alternatives have to be developed. These problems will be studied in this task and detection approaches will be developed. Specific air traffic management situational awareness example(s) will be considered during this study.

Task 7.4: Fault and error detection in prescribed time horizon. Time delay in fault or error detection and identification is critical and no results are available in the literature on this particular problem for hybrid systems. Our objective is to extend previous results in order to assess fault detection within a given maximal interval of time and to design a fault/error-tolerant control strategy. Specific communication network related air traffic management problems will be considered in this study.

Task 7.5: Application to air traffic management. The aim of this task is how the newly developed architectures in error evolution control can best be used for air traffic management. Within an aggregated large scale model of air traffic management the resulting performance improvements with respect to error propagation and error evolution control will be evaluated numerically, and the scalability of these results with increase of complexity will be addressed.

Task 7.6: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D7.2]

Hybrid Observer Design Methodology by E. De Santis, M.D. Di Benedetto, S. Di Gennaro, G. Pola

August 2003

Final

[D7.3]

Situation awareness error detection by M.D. Di Benedetto, S. Di Gennaro, A. D'Innocenzo
August 2004 Final

[D7.4]

Error Detection within a Specific Time Horizon by Maria D. Di Benedetto, Stefano Di Gennaro, Alessandro D’Innocenzo

March 2005

Final

[D7.5]

Critical observability for a class of stochastic hybrid systems and application to Air Traffic Management by M.D.Di Benedetto, S. Di Gennaro, A. D’Innocenzo

May 2005

Final

Papers published:

Id

Title

Date

Version

[R7.1]

Integrated Control-Implementation Design
by A.Balluchi, L.Berardi, M.D.Di Benedetto, A.Ferrari, G.Girasole, A.L.Sangiovanni-Vincentellli

November 2002

Preprint for
IEEE CDC 2002

[R7.7] Notes on the Nested Observers for Hybrid Systems by S. Di Gennaro
September 2003 Preprint for ECC 2003
[R7.8] On Observability and Detectability of Continuous-time Linear Switching Systems by E. De Santis, M. D. Di Benedetto, G. Pola December 2003 Preprint for CDC 2003
[R7.9] Observability for Hybrid Systems by A.Balluchi, L.Benvenuti, M.D.Di Benedetto, A.L.Sangiovanni-Vincentellli
December 2003 Preprint for CDC 2003
[R7.10] An Observer for Switching Nonlinear Systems with Mode Dependent Time Delays by P. Pepe September 2003 Preprint for WSEAS 2003
[R7.12] Polynomial filtering for Stochastic Systems with
Markovian Switching Coefficients
by A. Germani, C. Manes, P, Palumbo
December 2003 Preprint for CDC 2003
[R7.13] A State Observer for a Class of Nonlinear Systems with Multiple Discrete and Distributed Time Delays by A. Germani and P. Pepe May 2004
Preprint for MTNS 2004
[R7.14] Bisimulation theory for switching linear systems by G. Pola, A.J. van der Schaft, M.D.Di Benedetto
August 2004 Preprint for CDC 2004
[R7.15] Structural discrete state space decompositions
for a class of hybrid systems
by E. De Santis, M. D. Di Benedetto, G. Pola
February 2004 Preprint for MED04
[R7.18] Can linear stabalizability analysis be generalized to switching systems by E. De Santis, M.D. Di Benedetto, G. Pola
July 2004 Preprint for MTNS 2004
[R7.19] Critical Observability and Hybrid Observers for Error Detection in Air Traffic Management by M.D. Di Benedetto, S. Di Gennaro, A.D'Innocenzo March 2005 Preprint for MED 2005

Complementary papers and reports

Id

Title

Date

Version

[C7.1] A new experiment in research on hybrid systems: The center of excellence DEWS by M.D. Di Benedetto, J. Lygeros and the DEWS Team April 2003 Preprint for ADHS 2003

Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP8: Accident risk decomposition

Leader: Arun Bagchi (TWEN)

Followers: NLR, CENA, INRIA, AQUI, UCAM

Objectives:

Accident risk assessment for complex safety critical systems such as air traffic management, has to be done by an appropriate combination of stochastic analysis and Monte Carlo simulations. Unfortunately at this moment the identification of an appropriate way to combine both approaches is more an art than a science, and the art tends to fall short when the scale of complexity increases, and the control becomes distributed. The aim of this work package is to develop novel methods for the decomposition of risk such that extreme low risk values can be assessed through a hierarchy of conditional Monte Carlo simulations.

Work Description:

The work is organised in four tasks:

Task 8.1: Review existing risk decomposition and assessment methods, both analytical ones, Monte Carlo simulation approaches and combinations of these two. This review should distinguish between theory based methods and heuristic methods.

Task 8.2: Develop new risk decomposition and assessment methods. One of the key directions to be explored is the development of risk decomposition methods that make use of the fact that for strong Markov processes the Markov property holds true for stopping times.

Task 8.3: Development of conditional Monte Carlo simulation techniques for accident risk assessment that make use of the risk decomposition developed in Task 8.2, and comparison of the new approach with the existing ones identified in Task 8.1.

Task 8.4: Extend the risk decomposition approach with a recursive Bayesian estimation approach which enables the updating of the accident risk assessment while more and new information is coming available.

In each of these tasks the scalability with increasing complexity is addressed.

Task 8.5: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D8.1]

Risk Decomposition and Assessment methods Report.by Jaroslav Krystul, Arun Bagchi, Henk Blom

June 2003

Final

[D8.3]

Monte Carlo simulation of rare events in hybrid systems by J. Krystul and H.A.P. Blom

July 2004

Final

[D8.4]

Bias and uncertainty modelling in accident risk assessment by M.H.C. Everdij and H.A.P. Blom

May 2005

Final

Papers published:

Id

Title

Date

Version

[R8.2] Joint IMMPDA Particle filter by H.A.P. Blom and E.A. Bloem May 2003 Preprint for Fusion 2003
[R8.3] Tracking Multiple Maneuvering Targets by Joint Combinations of IMM and PDA by H.A.P. Blom and E.A. Bloem
September 2003 Preprint for CDC 2003
[R8.4] Sequential Monte Carlo simulation of rare event probability in stochastic hybrid systems by Jaroslav Krystul and Henk A.P. Blom
March 2005
Preprint for IFAC World 2005

Complementary papers and reports

Id

Title

Date

Version

[C8.1]

Genetic genealogical models in rare event analysis Report by F. Cérou, P. del Moral, F. Le Gland and P. Lezaud

December 2002

Final

[D8.2] Accident Risk Assessment and Monte Carlo Simulation Methods by P. Lezaud, J. Krystul, H.A.P. Blom June 2004 Final

Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP9: Perform risk assessment for a distributed control system

Leader: Henk Blom (NLR)

Followers: TWEN, INRIA, AQUI, CENA, EEC

Objectives:

The objective of this WP is to demonstrate how the various developments in all other work packages contribute to safety management. This will be done through performing a safe separation assessment for an advanced ATM operation which makes explicit use of distributed control over multiple aircraft. In doing so, the various developments from the other work packages are combined either in the definition of the ATM operation to be assessed, or in the execution of the risk assessment.

Work Description:

The work is organised in the following sequence of tasks:

Task 9.1: Identify the advanced ATM operation, including a systematic identification of all non-nominal situations and hazards. For the advanced ATM operation we will consider one in which it is expected that the proper co-ordination between air and ground in conflict resolution is an essential condition for realising significant capacity improvements. Potential applications are closely spaced runway situations at a busy airport and collaborative airborne separation assurance in dense en-route or TMA traffic areas.

Task 9.2: Develop a mathematically unambiguous stochastic hybrid model for the operation considered, and specify all model assumptions made, all model parameters and their values that are introduced. In view of the complexity of the development of such a mathematical model an existing model instantiation in Dynamically Coloured Petri Net (DCPN) form will be used as starting point, and all improvements will be developed in an iterative way: extend model specification, update assumptions and update list of model parameters and their values.

Task 9.3: Develop appropriate risk decomposition and uncertainty assessment approaches. For this, use is made of the methods developed in WP8. Subsequently extend already available accident risk evaluation software according to the model instantiation and risk decomposition of Tasks 9.2 and 9.3.

Task 9.4: Perform the risk assessment with support of stochastic analysis and Monte Carlo simulations for the instantiated models and their software implementation, and assess how sensitive the risk result is for changes in the values of the most relevant parameters.

In each of these tasks the scalability with increasing complxity is addressed.

Task 9.5: Produce and present Scientific paper(s)

Project Deliverables:

Id

Title

Date

Version

[D9.4]

Sequential Monte Carlo simulation of collision risk in free flight air traffic by H.A.P. Blom, G.J. Bakker, J. Krystul, M.H.C. Everdij, B. Klein Obbink and M.B. Klompstra

August 2005

Final

Papers published:

Id

Title

Date

Version

[R9.1] Approximation of first passage times of switching
diffusion
by J. Krystul and A. Bagchi
May 2004 Preprint for MTNS 2004
[R9.2] Particle filtering for stochastic hybrid systems by H.A.P. Blom and E.A. Bloem March 2004 Preprint for CDC 2004

Complementary papers and reports

Id

Title

Date

Version

[D9.1]

Description of advanced operation: Free Flight by B. Klein Obbink

March 2005

Final

[D9.2]

Compositional specification of a multi-agent system by Dynamically Coloured Petri Nets by M.H.C. Everdij, M.B. Klompstra, H.A.P. Blom,
B. Klein Obbink

November 2004

Final

Top WP0 WP1 WP2 WP3 WP4 WP5 WP6 WP7 WP8 WP9 WP10

WP10: Develop advanced risk assessment course

Leader: Henk Blom (NLR)

Followers: TWEN, AEAT, AQUI

Objectives:

The aim is to develop post-academic courses on stochastic analysis based risk assessment, which are based on an existing advanced risk methodology for Air Traffic Management. Two courses will be developed: a basic course, which is directed towards the application of the risk assessment methodology, and an advanced course, which is directed towards the instantiation of a new risk assessment application within the methodology.

For both training courses announcement material will be produced, which is directed to Air Traffic Management community and other safety related communities (e.g. railways), and to research communities.

Work Description:

Task 10.1: Development of the basic course and the course material

Task 10.2: Development of the advanced course and the course material

Task 10.3: Material announcing the courses


Project Deliverables:

Id

Title

Date

Version

[D10.3]

Introduction course on Monte-Carlo Simulation for Collision Risk and Safety Assessment

Advance Course on Safety Risk Assessment Based Stochastic Analysis with special emphasis on Air Traffic Management

April 2005 Final