1. Introduction

This paper presents steps towards the design of an on-board system dedicated to road traffic collision risks avoidance. The system is expected to produce sure detection of collision risks, it is also expected to produce safe actions, giving thus an efficient assistance to the driver [Bouchefra K. et al, 1995].

The design process, which is limited in this paper to software aspects, corresponds to a top down scheme; it includes the modelling, the specification and the verification steps.

The modelling step is based on a multi-agent approach; it leads us to the A²STRE architecture (Architecture of Agents Situated within the road Traffic aREa). The agents within this architecture are intended to interact in order to analyse a road traffic scenery and to produce actions that allow safe travels. The second section presents this architecture.

The ObjectGEODE tool, used in the specification step, produces a formal description of the architecture. This description includes externally developed programs that represent the agents’ behaviour; the description illustrates also the interactions between the agents. The third section presents the basic rules of the Specification and Description Language (SDL), the agent to agent interactions are then described in term of finite states and communicant automata. The formal description allows an automatic verification of the architecture. Indeed, the formal description corresponds to a graph representation, so the verification returns to some graph analysis. The fourth section presents the Message Sequence Chart language (MSC) which is used for interactions representation; this language allows the verification of temporal ordering properties.

The fifth section presents the A²STRE specification and verification using ObjectGEODE. Finally, a conclusion resumes the results and highlights the limitations of the actual tools.

2. A²STRE Multi-agent Based Architecture
1. Introduction to Multi-Agent Systems

A multi-agent system is defined by an environment and some entities, also called agents, that evolve within this environment. These agents are dedicated to solve a specific problem according to a method which can lead to distribute the problem (this case defines a concurrent activity of the agents), or to a distributed solving method (this case corresponds to agents with complementary skills) [Ferber J., 1995].

The design of a multi-agent system requires the definition of the agents’ model; this leads to identify agents’ knowledge and skills. It also requires the identification of their interaction abilities. The solving process is expected from the agent to agent interactions.

There exist different models of agents. The reactive model is related to those agents that are able to deal with precise states of the environment. The cognitive model points at agents that are able to process complex tasks and so are able to deal with complex states of the environment. The model of an agent is closely related to the environment it will evolve in, this leads basically to consider temporal aspects and so time constraints on agents activities [Maes P., 1992].

This paper presents the software level of an on-board system which is designed according to the above-mentioned considerations. Each agent within the architecture is dedicated to a specific task; the proposed architecture defines a society of agents with complementary skills. In the remainder of the paper, a vehicle that is equipped with the on-board system is called the observant Vehicle; the other vehicles within a road traffic scenery are called the Obstacles.

2. A²STRE Agents

Agents’ architecture: the agents are built according to the generic architecture in figure 1. Each agent receives data, from another agent, according to a point to point communication mode, it then processes these data according to the task it is dedicated to and it produces messages that are sent to another agent. The activity of each agent is emphasised by its level of satisfaction; a high level of satisfaction corresponds to a task that is processed successfully. The level of satisfaction of the agents is a key element in the organisation of the global activity within the architecture.



Figure 1: Generic model of an agent

Hierarchical organisation of the activity : The global activity of the agents defines the response of the system to the stimulus generated by the traffic scenery. This activity is realised according to a hierarchical organisation, indeed the A²STRE architecture consist of three hierarchical levels (see figure 2).



 Figure 2: Hierarchical organisation of the activity

This organisation defines a unidirectional flow of data. The data flow coming from the traffic scenery (collected by the appropriated sensors) passes by agents of the low level, then by agents of the mid-level and finally by agents of the high level. This bottom-up data flow corresponds to an analysis step, it leads to the elaboration of an explicit representation of the current traffic scenery. A top-down data flow, going from agents of the high level to the agents of the low level defines the system’s response.

According to the proposed management of the activity, the agents are not always all directly involved in the analysis of a traffic scenery. Thus, the management of critical situations, which requires a reactive response, involves only the agents of the low level. This last case corresponds to a data flow that goes from the agent which is dedicated to collect the data coming from the environment to the agent that executes actions on the environment.  

Global activity adaptation: The system’s response changes according to the dynamics of the scenery, this response highlights a data dependency between the agents.

The global activity of the agents is related to the level of satisfaction of each one. A satisfied agent is an agent that returns satisfactory results (for example, the agent dedicated to the identification of the obstacles’ behaviour is satisfied once a model is associated to each obstacle). In our scheme, the agents that require the results of a satisfied agent became independent of it, they use then saved and satisfactory information that has been collected at previous interactions. Accordingly, two chains of activities are distinguished, a main chain of activity and a secondary one. The main chain of activity involves all the unsatisfied agents while the secondary chain of activity involves the satisfied ones.

Adapting the global activity corresponds then to establish both chains of activities, this is equivalent to identify which agents are satisfied and which are not.

The following paragraphs describe the agents introduced above (see figure 2).

Description of the low-level agents: the agents of this level are directly involved with the data that are issued from the environment.

The "Perception" agent: The "Perception" agent collects data that are issued by the physical sensors. These data describe the Obstacles (indications are collected about Obstacles’ relative location, intention, …) and the context of the road traffic scenery. The Obstacles are then considered according to the road traffic rules. This processing defines a first level of interpretation. The results are emitted to the "Tracking" agent. The "Perception" agent is also designed in order to originate reactive responses. This scheme corresponds to the activation of the "Action" agent when a critical situation is identified. The level of satisfaction of the agent is defined to be always low.

The "Tracking" agent: The "Tracking" agent processes data that are sent by the "Perception" agent. The "Tracking" agent is designed for long term obstacles’ behaviour analysis. The agent elaborates and manages sets of cards that describe the kinematics of the Obstacles. This processing defines also another level of interpretation. The level of satisfaction of the agent is adapted to the correctness of the processing.

The "Action" agent: The "Action" agent executes orders that are emitted by the "Planning" agent or by the "Analysis" agent (see below) or by the "Perception" agent. This agent is of great importance in our scheme for the management of critical situations. The "Action" agent is designed to be always unsatisfied.

Description of the mid-level agents: The agents of this level deal with the data that are emitted either by the agents of the low level or by those of the high level. These agents are described hereafter.

The "Characterisation" agent: This agent receives data that are emitted by the agents of the low level. The "Characterisation" agent realises a matching processing between the received data and a set of a priori models [Bouchefra et al, 1997(a)].

The aimed result of this processing is to associate a behavioural model to each Obstacle. A set of four a priori models is defined according to different behaviours the Obstacles are expected to adopt when they face a collision risk. These a priori models are the following: the cognitive model, the antagonistic model, the reactive model, the basic model. The cognitive model corresponds to Obstacles that collaborate in the management of a collision risk, such Obstacles are identified according to their ability to respect the traffic rules, to communicate and to respect their intentions. The antagonistic Obstacles correspond to the obstacles that do not usually collaborate or respect the traffic rules although they can communicate their intentions. The basic Obstacles correspond to the obstacles that never collaborate, or respect the traffic rules or communicate their intentions. The reactive Obstacles correspond to the obstacles that also never collaborate or communicate their intentions, but are expected to respect the traffic rules. The matching processing consists to find the nearest model that fits the representation of the considered Obstacle; this processing consists then in a distance-like calculation. The results are sent to the agents of the highest level and also to the "Planning" agent. According to a considered Obstacle, the level of satisfaction of the "Characterisation" agent is high (=1) if one model fits exclusively the representation of the Obstacle.

The "Planning" agent: This agent receives data that are sent by the "Characterisation" agent and by the agents of the high level. Its task consists in the planning of the actions that allow reaching a targeted local destination. The resulting plan is used to activate the "Action" agent. The level of satisfaction of the "Planning" agent is associated to the reliability of the global activity of the agents. This level is high when each new target destination can be reached with the current plan is processed.

Description of the high level agents: The agents of this level are the "Scheduler" agent and the "Analysis" agent.

The "Analysis" agent: This agent receives data that are emitted by the agents of the lowest levels. Its task consists to determine a target destination that fits an initial destination and that avoids collision risks. The agent estimates the trajectory of each Obstacle, and measures of the risk that may be induced by each obstacle [Bouchefra et al, 1997(b)].

The processing is based on a function that returns a risk measure that is proportional to the location of the expected collision. Among two locations of expected collisions, the value of the risk measure is higher for the nearest one. Each estimated trajectory has a graph representation called a PRE-Graph, each vertex of the graph corresponds to the estimated location of the considered Obstacle’s trajectory. The analysis of the road traffic scenery is then translated into a processing of the PRE-Graphs. The agent determines a target destination that allows the avoidance of areas where collisions are expected. The target destination is transmitted to the "Planning" agent. The "Analysis" agent is in its highest level of satisfaction when no collision risk is expected, which means that the collisions have been managed efficiently.

The "Scheduler" agent: The "Scheduler" agent is not directly involved in the processing of the data that are related to a road traffic scenery. The agent adapts the global activity of the other agents according to the level of satisfaction of each one. Each agent sends its level of satisfaction to the "Scheduler" agent. The adaptation of the activity consists then to maintain within a main chain of activity all the agents that are unsatisfied while the satisfied agent are maintained in a secondary chain of activity. The main chain of activity represents the response that is elaborated by the agents. This response may be reactive, planned, complex, ...

The agent determines the acquaintance of each agent.

3. Agent to agent interactions

The agents interact by exchanging messages according to a point to point communication mode; the messages are represented by cards that respect an interaction structure. This structure indicates the emitter and the receiver of the message, it indicates the nature and the values associated to the message, it also indicates the level of satisfaction of the emitter. The message emitted by a satisfied agent, let us call it the X agent, allow the agents that require it to process their tasks without having to communicate with the agent X as long as this agent remain satisfied. A satisfied agent is loosely coupled with the other agents; it is only concerned with the verification of its level of satisfaction. Consequently, the main chain of activity associates the agents that are closely involved in the management of the current traffic scenery, it exist between these agents a strong data dependency relationship. The continuous modifications within the road traffic modify the dependencies between the agents. Thus a satisfied agent may return to an unsatisfactory state. In such case, the agent is replaced in the main chain of activity and is then tightly coupled with its acquaintances. Depending of which agents define the main chan of activity, there are various processing schemes. A reactive scheme corresponds to the management of critical situations or well-determined situations and involves the "Perception" and the "Action" agents. A cognitive scheme involves all the agents; these are then all required in the main chain of activity. The planning scheme corresponds to the management of a traffic scenery that involves the agents of the two first levels; the main chain of activity includes the "Planning" agent.

3. system specification
1. Introduction

According to the needs for more and more complex systems, the requirement for an efficient organisation is widely established [Bræk R. et al, 1993]. This organisation may require multiple skills, and then one may have to co-ordinate the efforts. Accordingly, a clear description of the targeted system is one key element within such organisation. This description is also of great interests for many other reasons among which system maintenance is easier. A specification consists to express the needs in term of system’s requirement. The difficulty is to obtain a description concordant to the system. Among various tools for system’s specification, there exist dedicated languages [Parker K.R. et al, 1991, Lang, 1993].

2. Specification and Description Language

The specification and description language (SDL) is conceived in order to respect a set of criteria [SDL recomm, 1992]. The SDL language is unambiguous as it allows only one semantic interpretation. It is complete because the developer can easily verify that all the needs have been expressed. It is also consistent; the description makes it easy to detect any conflicts within the needs. Also, the description can easily be up-dated.

The SDL language allows a hierarchical description of systems. The first hierarchical level describes the logical organisation of the system. This organisation defines the system’s architecture, which is expressed in term of connected blocs. Each bloc has its own functionality and is realised by a set of processes. The inter-bloc connections correspond to bi-directional or to unidirectional point to point communications. The communications are instantaneous.

The second hierarchical level describes the behaviour of each process in term of communicant finite states automata. A process executes an action according to the three following steps. It first receives a message (a message is an SDL signal), it processes this message, and then sends its results. Executing this sequence corresponds to a transition of an automaton from one state to another. An asynchronous execution of processes highlights interleaving relationships of the transitions between the processes.

The third and last hierarchical level describes the data on the basis of the Abstract Data Type (ADT) format. This format allows an implementation free from any material choice.

The description of the system is then formal. Such description is useful as one can easily establish appropriated rules according to his aims, thus one can translate the description into any other language (such as a programming language).

4. system Verification
1. Introduction

The aim of verification is to check that each expressed requirement fulfils the needs. As mentioned above, a formal representation makes it possible to establish appropriated rules for automatic verification. Here, there exist also dedicated languages.

Thus, the ObjectGEODE tool allows automatic verification of certain properties within an SDL description (see §5). Unfortunately, this tool doesn’t allow the verification of certain temporal properties.

2. Message sequence chart language

The message sequence chart (MSC) [MSC recomm, 1992], allow the description of temporal ordering between processes within a system. This description is formal. Consequently, it is used for process to process interaction verification.

Each MSC describes the process to process interactions in term of point to point communicant finite states automata. These interactions are described by a diagram. A set of MSC’s can be combined according to boolean operators, a temporal ordering property is then verified if the result of the MSC’s combination expresses this property [Sarkar A. et al, 1995].

The execution of a process is graphically represented by a top down vertical axis. Then, if A and B are two actions within a same process, then these actions are located on the same axis and are sequentially processed. If A and B belong to two different processes, then they are represented by two different axes and are processed according to a parallel scheme. A parallel-processing scheme is described by multiple axes, inter-processes communications are represented by connections between that are oriented from the axis of emitter to axis of the receiver. The figure 3 shows an MSC description in which two processes P and Q exchanges the message m.



Figure 3: Example of an MSC description

 

5. A²STRE specification and verification

The A²STRE architecture has been described using SDL and MSC languages. Hereafter is presented each of these descriptions.

1. A²STRE specification

The SDL language is used for the architecture’s specification. Each agent of the architecture is described in term of an SDL process; this description includes externally developed programs that represent the agents’ behaviour. Agent to agent interactions are based on point to point communications that use reliable links, each communication consists to exchange only one message. The figure 4 illustrates the SDL description of the A²STRE architecture. In this description, the first bloc associates the "Perception" and "Tracking" agents, the "Scheduler" agent is directly represented by the routing mechanisms.

 



 

Figure 4: SDL description of the A²STRE architecture

2. Processes

A states automaton represents agent’s behaviour described in section §2. In addition, two local variables are needed to implant the distributed protocol of control.

The first variable level of boolean type indicates the level of satisfaction (level is assigned false if the agent is unsatisfied), the second variable data represents the structure of messages exchanged between agents (its type is referred by the term type_of_cards).

The figure 5 illustrates the SDL representation of an agent.



Figure 5: SDL representation of an agent

 

The figure 6 hereafter describes the "Perception" and "Action" agents. The Perception bloc is designed to produce messages continuously. The Action bloc defines the "Action" agent. This bloc is designed to destroy messages continuously. The Perception bloc is designed in order to simulate the environment.

 



Figure 6: SDL description of the first and last agents of the on-board system

 

An SDL process may integrate externally defined functions. Thus, C functions can be integrated into an SDL representation, and they can access to the local variables of the SDL representation.

3. Communication links

The communication system is designed for bi-directional message exchanges. The messages from the environment are transmitted in the way flowing from the Perception bloc to the Action bloc; this flow corresponds to the data flow. In the opposite way, agents’ level of satisfaction are transmitted this flow corresponds to the control flow. The inter-bloc communication links correspond to the data flow exchanged by the agents. This data flow is continually adapted according to the level of satisfaction of the agents. As mentioned above, there are two chains of activity. The first one associates the unsatisfied agents while the second one associates the satisfied agents. Adapting the data flow corresponds to transfer agents from one chain of activity to the other according to their level of satisfaction. The SDL translation of this mechanism leads us to establish all possible links and to define constraints that make valid only the links of the unsatisfied agents. The figure 7 illustrates the data flow and the control flow of the architecture’s SDL representation.

 



Figure 7: Illustration of the data and control flows within the SDL representation

4. Process control

The process control consist to identify the valid links. The figure 8 shows the valid links when all the agents are unsatisfied.

 



Figure 8: Data links when all the agents are unsatisfied

 

The figure 9 shows the structure when the "Characterisation" and the "Planning" agents are satisfied. The secondary chain of activity contains the "Characterisation" and the "Planning" agents, the main chain of activity associates the rest of the agents. According to the valid links, each agent sends messages to its following acquaintance and receives messages from its precedent acquaintance.

 



Figure 9: Data links when the "Characterisation" and the "Planning" agents are satisfied

 

The links are associated to a boolean variable; a link is enabled or disabled according to its associated variable.

Each process contains a vector of boolean variables, the i^th element of the vector represents the i^th link’s variable: if the value of the i^th element is TRUE then the corresponding link is enabled with the appropriated bloc, the link is disabled if the value of the link’s variable is FALSE. The figure 10 illustrates a subset of valid links.

 



Figure 10: Illustration of valid links

 

Once a link is enabled, a message can be sent if the agent is unsatisfied. Finally, the process control consists to up-date the local values of the boolean variables.

The arising problem concerns then how to maintain a coherent mapping between the agents’ level of satisfaction and the synchronisation of message exchanges.

The actual mechanism is based on a back propagation control flow. A communication protocol is then defined, it consists of the following steps: 1. A message is sent to the following agent on the basis of the above-mentioned conditions; 2. A wait is initiated in order to receive the following agents’ levels of satisfaction; 3. The local level of satisfaction is up-dated and is sent to the precedent agents.

This protocol defines a synchronous interaction mechanism. Thus, an SDL process contains two SDL descriptions, one describing an agent’s behaviour, the other dedicated to the process control.

The first SDL description contains a state "Start" that initialises the processing and a state "Waiting" that illustrates the requirement for an incoming message before the processing of the rest of the instructions.

These processing depend on the received information as described above. For example, fhe figure 11 below illustrates the "Planning" agent.

 



Figure 11: SDL description of the "Planning" agent

 

The second SDL description defines the process control. Within, the SDL language only one message can be received at once, consequently the levels of satisfaction require multiple communications to be all received, these messages are saved in local variables according to the order of their arrival (First_Ack, Second_Ack, Third_Ack, ...).

The following figure illustrates the SDL description in the case of the "Characterisation" agent.

 



Figure 12: SDL description of the "Characterisation" agent

5. Verification

The ObjectGEODE tool [Verilog (b), 1996] offers the possibility to verify certain behavioural properties. The integrated SDL language allows the following verifications: the tool seeks for deadlocks, non-expected behaviours, data type violations, and reception of non-expected messages. It also points at the non-reachable states of the description and also indicates the inappropriate transitions.

The MSC language [Haugen, 1994] allows the verification of temporal ordering properties. In our case, this consists to check all possible ordering of the agents chains of activity, each of these chains defines one structure [Godefroid P., 1995].

 

 

The table 1 shows all possible structures (U means unsatisfied, S means satisfied). In our case, with a set of five (5) agents and with two agents continually unsatisfied, there are eight (8) possible structures.

 

"Characterisation" agent	"Analysis" agent	"Planning" agent	Structures
U	U	U
S	U	U
U	S	U
S	S	U
U	U	S
S	U	S
U	S	S
S	S	S

 

Table 1: MSC verification

 

The process control is completely described by the eight (8) MSC’s descriptions. Three operators allow combining these MSC’s; these are the SCENARIO, REPEAT and OR operators.

The on-board system (SCENARIO operator) executes in a repeatedly manner, (as indicated by the REPEAT operator) one of the eight MSC’s (this correspond to the OR operator).

The figure 13 illustrates a combination of MSC’s. The figure 14 shows the MSC representation of two different chains of activity.

 



Figure 13: MSC combination

MSC description : The flow of exchanged messages when only the ‘‘Characterisation" agent is satisfied

MSC description : The flow of exchanged messages when the agents ‘‘Perception’’ and ‘‘Action’’ are unsatisfied

Figure 14: MSC descriptions for different main chains of activity

 

The exhaustive simulation results prove that the MSC’s property is verified by the SDL description. Furthermore, the results show also that no deadlock is determined and that no messages are lost. The table 2 resumes the results.

 

Number of states : 25548 Number of transitions : 64282 Maximum depth reached : 65 Maximum breadth reached : 1536 duration : 1 min 29 s Number of exceptions : 0 Number of deadlocks : 0 ...

 

Table 2 : Simulations results

6. Conclusion

The design of an on-board system requires a methodology according to which multiple skills can be efficiently involved. Among different aspects, there is a requirement for adequate tools that allow structured descriptions of the project at its different development steps.

Nowadays, there are different languages that respect criteria that lead to structured descriptions. Furthermore, these languages produce formal descriptions and thus allow automatic verification of properties.

Accordingly, a software design process includes the following steps:

• (1) the first step consist to identify the adequate architecture, in our case a multi-agent based model is proposed;
• (2) the second step leads to the system’s specification, this is equivalent to express the model according to a formal basis; in our case the SDL and MSC languages are the basis of a formal description;
• (3) The third step consists to verify that the model is concordant with the specification, this step leads to a more accurate model and one may have to consider again the steps (1) and / or (2).

The drawback of the actual languages is, in our case, related to their limitation when one has to efficiently express temporal duration. These languages are limited because the specification of a system leads to a code representation whose size growths exponentially when one adds a new semantics. So, our specification is partially guaranteed.

The challenging issue of the specification and verification based methodologies concerns then extended languages. The targeted systems may allow a compromise that brings an expressive time representation at the specification level without augmenting the complexity at the coding level.

Bouchefra K. et al, (1995), "IVHS viewed from a multi-agent point of view". In Congres of Intelligent Vehicles'95. Boston, USA, sep.

Bouchefra K. et al (a), (1997), "Basis for intelligent interactions", IFAC-IFIP Conference on Control of Industrial Systems (Crujic, Borne, Ferney, Ed.). Elsevier Science Ltd. Belfort, FRANCE.

Bouchefra K. et al (b), (1997), "Formal model for road traffic collision risk avoidance", IFAC-IFIP Conference on Control of Industrial Systems (Crujic, Borne, Ferney, Ed.). Elsevier Science Ltd. Belfort, FRANCE.

Bræk R. et al, (1993), "Engineering real-time systems, an object oriented methdology using SDL". The BCS practitioner series, Prentice Hall.

Ferber J., (1995), "Les systèmes multi-agent, vers une intelligence collective". InterEditions publishers.

Godefroid P., (1995), "Partial-order methods for the verification of concurrent systems". LNCS 1032, Springer-Verlag.

Haugen, (1994), "MSC methodology". Report n° L-1313-7, SIU, December.

Lang, (1993), "Using formal description techniques : an introduction to Estelle, Lotos and SDL". In Wiley series communication and distributed systems, New-York.

Maes P, (1992), "Situated agents can have goals". In Designing Autonomous Agents, theory and practice from biology to engineering and back, edited by P. Maes. Vol 80(5).

MSC recomm (1992), "Draft Recommendation Z. 120, Message Sequence Chart". ITU-T, CM XR 22-E, Geneva, March.

Parker K.R. et al, (1991), "Formal description techniques". Proceeding of the IFIP, FORTE’91, volume 4, Sydney, Australia.

Sarkar A et al, (1995), "Specification-modelling methodologies for reactive-system design". Current Issues in Electronic Modelling Volume 3. High-Level System Modelling : Specification Languages. Edited by J.M. Bergé, O. Levia and J. Rouillard. Kluwer Academic Publishers.

SDL recomm. (1992), "Recommendation Z.100 : specification and description language SDL". Blue Book, Vol. X.1-X.5.

Vere S. et al, (1990), "A basic agent". In Computational Intelligence, 6(1). 1990.

Verilog (b), (1996), "SDL simulator, reference manual". Verilog S.A. 1996.