Sotiris Lazarou

Antonis C Kakas

Christiana Neophytou

Andreas Constantinou

Automated Scientific Assistant for Cancer and Chemoprevention

Keywords: Abductive Reasoning, Systems Biology, Cancer Modeling

Logical modeling of cell biological phenomena has the potential to facilitate both the understanding of the mechanisms that underly the phenomena as well as the process of experimentation undertaken by the biologist. Starting from the general hypotheses that Scientific Modeling is inextricably linked to abductive reasoning, we aim to develop a general logical model of cell signalling and to provide an automated scientific assistant for the biologists to help them in thinking about their experimental results and the possible further investigation of the phenomena of interest. We present a first such system, called ApoCelSys, that provides an automated analysis of experimental results and support to a biology laboratory that is studying Cancer and Chemoprevention.

Introduction: Scientific Modeling in Logic

Modeling scientific phenomena requires that we set up a link between our mental understanding of the phenomena and the empirical information that we collect from observing the phenomena. In most cases the scientific effort concentrates on setting up experiments that would provide empirical information suitable for developing further (in the extreme case abandoning) our current model for the phenomena. An abstraction therefore is required both at the object level of understanding the processes that generate the phenomena and at the meta-level of understanding how to set up experiments that would reveal useful information for the further development of our scientific model. Using logic as the basic for scientific modeling facilitates this abstraction at both levels and the connection between them. For Molecular Biology, logic is particularly suited as (at least currently) the theoretical models of cell biology are more at the descriptive level and experiments are developed following a rationale at the qualitative level rather than the quantitative level.

The purpose of the work in this paper is two fold. To develop logical models of biological process through which we can carry out a biologically valid analysis of experimental (in-vivo or in-vitro) results and to provide based on this automated help to the Biologists in thinking about the scientific process of their experiments and their possible further investigation of the phenomena they are studying. The aim is to (incrementally) develop an underlying model for signal propagation in a cell that is independent of any particular biological phenomena and process on top of which we can then modularly build a model for specific biological problems. The underlying model needs to capture the propagation of increased as well as that of decreased activation, where the increase and decrease are determined through relative changes with respect to a normal level of activity.

We present a model for cell signaling formulated within the framework of Abductive Logic Programming (ALP), together with a tool to be used as an automated assistant by the biologist. The study is carried out with emphasis on the particular biological process of apoptosis as studied by the group of Cancer Biology and Chemoprevention at the Department of Biological Sciences at the University of Cyprus. Their aim is to investigate the molecular mechanisms through which natural substances or their derivatives participate in the inhibition of carcinogenesis (chemoprevention) or the inhibition of tumor progression.

Biological Background

Physiological processes are conducted in cells through sequences of biochemical reactions known as molecular pathways. Each molecular pathway consists of a series of biochemical reactions that are connected by their intermediates: the products of one reaction are the substrates for subsequent reactions, and so on. Apoptosis or programmed cell death (PCD) is a physiological process which is vital for normal development and elimination of damaged cells in living organisms (reviewed in [START_REF] Elmore | Apoptosis: a review of programmed cell death[END_REF]). Apoptosis is a main tumor suppressor mechanism within the body because it gets rid of cells that have extensive DNA damage. Its deregulation can lead to cancer and other diseases.

Chemotherapy primarily refers to the treatment of cancer with an antineoplastic drug. Evidence in the literature suggests that Vitamin E natural and synthetic analogues may target the main survival pathways of the cell (i.e., PI3K and NF-kB), which provides not only an amplification response of the apoptotic pathway, but also kills selectively cancer cells whose survival may depend on activating these pathways [START_REF] Constantinou | Vitamin e and cancer: An insight into the anticancer activities of vitamin e isomers and analogs[END_REF][START_REF] Neuzil | Vitamin e analogues as a novel group of mitocans: anti-cancer agents that act by targeting mitochondria[END_REF]. The goal of our biological study is to investigate the molecular events by which a Vitamin E synthetic derivative (VitESD) leads to apoptosis in breast cancer. For this purpose, we use two breast cancer cell lines, MCF-7 and MDA-MB-231, which are widely used as tumor models.

In vitro experiments are time-consuming and expensive as we need to screen a large number of possible targets in order to identify proteins that are involved in the signaling cascade affected by the compound under investigation. The use of an automated system will allow for calculated suggestions of molecules likely to be involved in the apoptotic pathway induced by the drug.

our model, generate new information that helps to develop further the model. In effect, abductive reasoning rationalizes the empirical data with respect to the current model with further hypotheses on the incompleteness of the model. Abductive Logic Programming (ALP) [START_REF] Kakas | Abductive Logic Programming[END_REF][START_REF] Kakas | Abduction in logic programming[END_REF] provides a framework for logical modeling that also directly supports abductive reasoning and hence it is particulary suited for scientific modeling. A model or a theory, T , in ALP is described in terms of a triple (P, A, IC) consisting of a logic program, P , a set of abducible predicates, A, and a set of classical logic formulas IC, called the integrity constraints of the theory. The program P contains definitional knowledge representing the general laws about our problem domain through a complete definition of a set of observable predicates in terms of each other, background predicates (which are again assumed to be completely specified in P ) and a set of abducible predicates that are open and which thus carry the incompleteness of the model. The integrity constraints, IC, represent assertional knowledge of known properties of the domain that must necessarily be respected and maintained when we complete further our theory. Given such an ALP theory the abductive reasoning that infers an abductive explanation is defined as follows.

Definition 1. Given an abductive logic theory (P, A, IC), an abductive explanation for an observation O, is a set, ∆, of ground abducible atoms on the predicates A such that:

-P ∪ ∆ |= LP O -P ∪ ∆ |= LP IC.
where |= LP denotes the logical entailment relation in Logic Programming.

The abductive explanation ∆ represents a hypothesis, which together with the model described in P explains how the experimental observations, Q could hold. The role of the integrity constraints IC is to impose additional validity requirements on the hypotheses ∆. They are modularly stated in the theory, separately from the basic model captured in P. As such, they can also be used, as we will see below, to steer the search for specific forms of explanation that our domain experts are looking for.

Modeling Apoptosis and Drug Effects

The core of our logical model consists of a fairly general representation of the activity of Signal Propagation in a cell. The task is that given a network of pathways generated through biological experiments, such as the one shown in Figure 1, to logically model the signal propagation over this and the effect of the presence of external drugs on this propagation.

We will consider the propagation of two types of signals: positive signal and negative signal. Normally cell signalling refers to the propagation of a positive signal, namely the iterative increase in activity of molecules along the pathway. In the propagation of a negative signal we refer to the iterative decrease in activity of molecules along the pathway. The increase and decrease of activity are taken relative to some level which is considered to be the normal background level of activity. The propagation of a negative signal is appropriate when we want to follow the inhibition effects of molecules. The core principles of positive and negative signal propagation are respectively the following.

Positive Propagation The activation of a molecule X will cause the activation of a molecule Y that follows X (i.e. Y is induced by X) in a signalling pathway, provided that Y or this reaction from X to Y is not inhibited by the activation of another molecule. Negative Propagation The inactivation of a molecule X will cause the inactivation of a molecule Y that follows X in a signalling pathway, provided there is no other molecule Z that also induces Y and Z is activated. In these principles we abstract away the details of the actual chemical processes that occur to bring about a single step of propagation and we do not distinguish between the different types of signal propagation that are biologically possible. In general, this high-level abstract view of a single step of propagation is depicted in Figure 2 where the biological pathways are abstracted into a graph with positive or inducement links and negative or inhibitory links. Hence the substance D will be activated when any one of A and B are activated but its inhibitory gene, I, is not activated. Similarly, D will be inactive when C is inactive or when I is activated.

Fig. 2. An abstraction of Cell Signalling

Under the normal operation of the cell signals start from some boundary points, such as A or B. When an external drug is added in the cell then we have the possibility that this could activate or inactivate a molecule at any part of the network (or even enable new hitherto unknown links in the network) present in the background network. The task of the biological research in which the logical model and its automation is to assist, is to discover the effect of the drug on these background networks and the possible existence of other pathways relevant to the cell operation that is studied, e.g. apoptosis, as in the case of our study.

The above basic principles of signal propagation are captured by the following recursive rules for active/2 and inactive/2 in a logic program, P , together with the a set of integrity constraints, IC, of the theory T =< P, A, IC > in ALP. The "Phase" variable in the model relations distinguishes experiments where different drugs could be present with different possible effects of these drugs as captured by the lower-level predicate, possible drug ef f ect/3, defined via some biological knowledge that we have a-priori of the drugs or via some hypothetical behavior of the drug to which the biologist wants to restrict their attention of study. The predicate absent/2 is also used to describe the variation in the set up of the various experiments where the biologist will arrange for some molecules to be effectively taken out the cell and hence to signal can go through them.

The reaction/2 and inhibitor/2 relations are given directly from the biological background pathway networks in the literature (see for example figure 1 again) as a database of extensional information of the following form:

reaction(rct(ing2,p53)).
inhibitor(bax,bcl2). reaction(rct(p53,caspase2_raiid_pidd)). inhibitor(bcl2,noxa). reaction(rct(p53,bax)).

inhibitor(bcl2,mcl1_puma). reaction(rct(p53,noxa)).

inhibitor(mcl1_puma,mule). ... ...

The observable predicates in the model are the two predicates of active/2 and inactive/2 through which the observations in any single experiment are turned into a conjunctive query for an abductive explanation through the model of T . Observations are of two types: activation or inactivation of some molecule from which it is known (or assumed in the model) that some overall operation of the cell, such as apoptosis will ensue or not and the activation or inactivation of intermediate molecules (markers) that the experimenter has measured.

In the above model the only abducible predicates refer to assumptions that we can make on the effect of the Drugs on the molecules. Other abducible predicates can be added if we want to extend the model to cover the possibility of some other unknown external effect on the molecules or indeed the possibility of the existence of other unknown background reactions.

5 ApoCelSys: a scientific advisor system ApoCelSys is a system that uses the model described in the previous sections to simulate the essential function of apoptosis, otherwise known as programmed cell death. The main purpose of the system is the creation of explanatory assumptions for validating the phenotype that was observed by the user and presenting a set of hypotheses on the effect of the synthetic substance introduced in the cell. A user interface, shown in figure 3, provides a graphical representation of the molecular pathways leading to apoptosis. This helps to simplify the insertion of the experimental data and the observations to be explained, whether these come from real in-vitro or hypothetical experiments . The user can set the status of any gene to any of the five predefined statuses: "active" either "fixed" by the experimenter or "observed"; "inactive" similarly either "fixed/absent" or "observed" or "neutral" otherwise. Also the possible effect of the drug on the gene can be regulated by the user if and when such information is available. Otherwise, the system assumes that the drug can possibly affect the gene in either way of inducing or inhibiting the gene.

The user can save this experimental data so that s/he can collect and easily revisit a set of experiments that have been analyzed by the system. After passing the experiment's information as input and executing the query, the system displays the first explanation found using distinguishing colors on the corresponding elements (red for the assumption of drug inhibited and green for drug induced).

A tool for enumerating the explanations is also available through which the user can view, filter and present the most interesting, in her opinion, explanation for a more detailed examination. During this single explanation display, the system also allows the propagation of the substances' primary effect on the rest of the cell for an overview of the pathway activation and in particular the way that apoptosis is activated or not. An example of this can be seen in figure 3 where the explanation that the drug induces traf 2 rip ciap f add tradd, aif , endo g and inhibits XIAP propagates to activate jnk, cjun, . . . and this eventually propagates to activate apoptosis. It also shows how this explanation has an inactivation effect on s1433 and bcl2 bmt.

Frequency Charts for Multiple Explanations Due to the multiplicity of the explanations that can be generated, automated analysis tools provide effective views on the likelihood of each assumption on the entire spectrum of explanations. The use of this tool creates graphs that exhibit the probability of the assumption of inducing or inhibiting elements throughout all produced explanations. An example is shown in figure 4 where we can see that aif and endo g have the most hits in being induced by the synthetic substance and that as a second choice the most probable effects are the inducements of bak, xiap, tbid and bid. In addition, if requested, the system is in a position to compute, analyze and present charts displaying the likelihood of any gene being activated irrespective of being a direct drug effect or of being a consequence of the latter. This information can be interpreted as displaying all possible pathways along with their appearance frequency, thus enabling the user to better judge the most probable pathways to apoptosis. These visual tools allow the easy comparison by the user between multiple variations of an experiment or even between cross-experiments.

Validation and Evaluation of the System

In order to validate the system we have analyzed the experimental results of real in-vitro experiments as described in section 2 for investigating the action of V itESD. One such experiment was carried out with the MCF-7 cancel cellline and another one with the MDA-MB-231 cell-line. The purpose was to judge These two experiments were analyzed with the ApoCelSys system and then the results were given back to the biologist to evaluate them. For the MCF-7 experiment the results suggest that Bak and tbid are greatly induced and that Smac/Diablo is also moderately activated by the presence of V itESD. The ApoCelSys system therefore suggests that most likely V itESD helps to activate apoptosis through the intrinsic pathway of apoptosis. The frequency distribution chart, generated by the ApoCelSys system, showing molecules that become inactive in the presence of the drug, suggests that PI3K, the upstream regulator of AKT, is in fact inhibited during apoptosis in our system and that Calcium levels (Ca2)-which control Calpain and subsequently Caspase activation-are also diminished. These findings are in line with the central role that AKT may play and further attenuate the caspase-independent mode of action of the V itESD.

Similarly, interesting results were produced for the second experiment with the MDA-MB-231 cells. Furthermore, in both cell lines, Survival factors such as growth proteins are suggested to become inactivated in the presence of the drug. This highlights another unexplored possibility that could explain the induction of apoptosis in our system: the inhibition of Growth Receptors on the cell membrane. The implication of these receptors coincides with the inactivation of PI3K and AKT which as mentioned before seem to play a central role in our system.

Expanding the Biological Investigation

The development of scientific theories often requires broadening the domain of investigation in several ways. For example, it may be relevant to combine the study of the cell process we are interested in with that of other cell processes that we know or suspect that are related to our primary interest. During the process of developing the ApoCelSys system the biologists expanded their investigation to the proliferation process of the cancer cells in addition to that of apoptosis. This required that the underlying pathways network to contain also the main established pathways for cell proliferation, some of which have cross over points with the apoptosis networks. The modular and logical nature of our model allowed this to be carried out in a straightforward and immediate way.

In-silico Thought Experiments Scientists often use thought experiments for guiding them in their future investigations. These can help in understanding the significance of new ideas and how they can help to expand the horizon of investigation. The ApoCelSys system facilitates the examination of experiments that the Biologist may want to hypothetically ask. For example, what would the explanatory effect of the drug be if we also observed some other molecules in the cell? How would the experimental results be explained if we added new information in the model such as new information on the suspected action of the drug in the form of additional integrity constraints, such as that the drug cannot induce together a set of molecules or that it can only induce a molecule if some other molecules are not active. Also the biologist can examine how would the results be affected if we assume that there are some extra reactions (links) in the background network of pathways? For example, the biologists may suspect that there might exist a new inducement link between two molecules. Adding this extra link and reanalyzing the same observed data can give valuable glues as to whether this is plausible and how it would be experimentally confirmed. This process of hypothesizing in a controlled manner new structures on the underlying network and analyzing their significance can be semi-automated. We are developing tools that would assist the biologist in such thought experiments.

Overall Evaluation of ApoCelSys as an Assistant From a working biologist point of view the overall evaluation of our system is summarized in the following. The ability to input our actual results in an automated assistant that contains all the information needed to describe the cellular microenvironment provides a much simpler alternative than in vitro screening of a large number of proteins. Also the capacity to adjust this microenvironment in order to depict the variability that exists between cell lines greatly enhances the usefulness of this system. The major benefit of this assistant is the frequency distribution charts which provide an indication for which molecules to be investigated next, thus saving time and cutting laboratory costs. Furthermore, the ApoCelSys system may serve as a tool for the discovery of unknown reactions between molecules that can reveal novel pathways to be targeted in cancer therapy.

Evaluation of Computational Behaviour

We have carried out a series of experiments to investigate the computational properties of the current (and first) implementation of the system. This implementation relies on a new implementation of the A-system [START_REF] Ma | A-system v2[END_REF] for computing (minimal) explanations but does not in its current form exploit the constraint solving capabilities of the A-system. The response time of the system is dependent on the users' input and may vary from a few seconds to a couple of hours for a complete search of all minimal explanations.

We have thus tried to investigate to what extend it is necessary to compute all explanations and how we can find a representative sample of these. Under the assumption that the effect of the drug to produce the results on the molecules that we have observed in the experiment cannot be "too far" along the pathways from these observed molecules, we have restricted the depth of search by the Asystem and have tried to learn what is a reasonable threshold on the search depth bound. Using the real experiments described above as a basis and running the system with various depth limits we obtain the results shown in figure 5.

According to these we can see that no major fluctuation in the nine most prob-Fig. 5. Search Depth Variation of Explanations able hypotheses of induced molecules except for a single molecule, bid, on the lowest depth limit of 200. The same can also be observed in figure 6 in which all molecules found in figure 5 have been sorted by their inducement probability and labeled with non-zero positive numbers, where one stands for the most probable molecule to be induced by the substance. In this figure, we can observe that most of the molecules retain their positions, which shows that even in low depth searches, the results provided are of satisfactory quality.

However restricting the search could result in loosing valuable information when our assumption of no "long-distance" effect is not appropriate. The large Fig. 6. Probability of drug inducement of molecules computational time of an unrestricted search is due to the complex pathways and the fact that the top down search of the A-system contains parts that are unnecessarily duplicated. We plan to develop other implementations that are based on bottom up computational models using tabling or ASP solvers.

Related Work

There are several earlier works of Symbolic Systems Biology which also use a form of logical modeling within Logic Programming (Abductive or Inductive) and rely on abductive and/or inductive reasoning for the analysis of experimental results. Some of the earliest such approaches include [START_REF] Zupan | Abductive inference of genetic networks[END_REF] for the analysis of genetic networks based on abduction, [START_REF] Papatheodorou | Inference of gene relations from microarray data by abduction[END_REF] for generating gene interaction networks from micro-array experiments within ALP and [START_REF] Ray | Automated abduction in scientific discovery[END_REF][START_REF] Ray | Inferring the function of genes from synthetic lethal mutations[END_REF] for discovering the function of genes from auxotrophic metabolic experiments or for studying lethal synthetic gene mutations using the XHAIL framework and system [START_REF] Ray | Nonmonotonic abductive inductive learning[END_REF] that supports abductive and inductive reasoning within the representation framework of ALP. In [START_REF] Tamaddoni-Nezhad | Application of abductive ilp to learning metabolic network inhibition from temporal data[END_REF] a logical model for capturing the possible toxic effects of drugs in a cell has been developed within ALP and analyzed using the Progol5 system.

Our work can be seen to follow this line of approach, with an emphasis on providing tools with interactive interfaces to help the biologist as an automated scientific assistant. As the underlying network information increases, it is evident that we need to develop a better graphical interface of our system in the form of a map-like interface where the user can focus on the details of the pathways network that s/he is currently investigating. Similarly, new interactive interfaces are needed to facilitate the thought experimentation process by the user.

More recently, [START_REF] Synnaeve | Kinetic models and qualitative abstraction for relational learning in systems biology[END_REF] have developed an important methodology for qualitative logical modeling in systems biology that rests on underlying quantitative models for the chemical reactions in the signalling pathways. Our approach lacks this link to quantitative computational models and it would benefit from their integration in the logical model as black computational boxes. This work uses a probabilistic method to rank the multiple hypotheses found much in the same spirit as we do with the frequency charts of individual hypotheses over the set of explanations. They then go a step further to rank the full explanations. This is an extension that would be useful to consider in our approach.

The authors in [START_REF] Ray | Logic-based steady-state analysis and revision of metabolic networks with inhibition[END_REF] show how using the XHAIL system it is possible to allow abductive reasoning for the revision (deletion or addition of reactions) of the underlying pathways on which a logical model for metabolism is build. In our approach and system this is done semi-automatically by suggestions of the expert biologists in the context of possible thought experiments that they want to carry out for further investigation. It would then be useful to automate these type of thought experiments by incorporate the same type of use of abductive reasoning in our model.

Another piece of work that is relevant to our future work is that of [START_REF] Ray | Analyzing pathways using asp-based approaches[END_REF] where Answer Set Programming is used for the computation of processes of biochemical reaction networks that combines numerical weight information and logical inference. The use of ASP solvers for the computation of abductive reasoning could help improve the computational behavior of our system especially when the network of reaction pathways contains cycles.

Conclusions and Future Work

We have presented a methodology for building automated scientific assistants to help in the research effort of molecular biologists. This is based on logical modelling of the existing background knowledge of the phenomena studied and the automation of abductive reasoning to provide explanations for the observed empirical results of the experiments carried out by the biologists. The resulting tools could also help in assisting with the further development of the research program of the biologists by facilitating the scientific thinking carried out when decisions for the future direction of research are taken. This methodology and resulting automated assistant, called ApoCelSys, has been tested in a real life case of a research group that studies the chemoprevention of cancer.

The testing of the ApoCelSys system carried out so far provides encouraging results but further systematic experimentation with the system is needed. In particular, it is important to carry out a series of tests to understand better the capabilities of the system for facilitating thought experiments and what extra features and functionality would make it more suitable for this purpose.

Fig. 1 .

 1 Fig. 1. Apoptosis pathways linked to the Mitochondrial.

Fig. 3 .

 3 Fig. 3. System Interface of ApoCelSys and Propagation of an Explanation.

Fig. 4 .

 4 Fig. 4. Frequency Distribution across Explanations

Scientific modeling is inextricably linked to abductive reasoning. Abductive explanations for new observational data, that are based on the current form of


Toshiharu Sugawara

Task Allocation Strategy Based on Variances in Bids for Large-Scale Multi-Agent Systems

We propose a decentralized task allocation strategy by estimating the states of task loads in market-like negotiations based on an announcement-bidaward mechanism, such as contract net protocol (CNP), for an environment of large-scale multi-agent systems (LSMAS). CNP and their extensions are widely used in actual systems, but their characteristics in busy LSMAS are not well understood and thus we cannot use them lightly in larger application systems. We propose an award strategy in this paper that allows multiple bids by contractors but reduces the chances of simultaneous multiple awards to low-performance agents because this significantly degrades performance. We experimentally found that it could considerably improve overall efficiency.

Introduction

Recent technology in the Internet and ambient intelligence has enabled services that are incorporated into daily activities. These services consist of a number of tasks each of which has required capabilities and data, and should be done in agents meeting these requirements. Of course, vast numbers of services are required everywhere in the environment; thus, they are provided in a timely manner by a large number of cooperative agents on computers and sensors through mutual negotiations to appropriately allocate associated tasks among agents. It is, however, unrealistic for agents to know all the capabilities and data other agents have in open environments. Well-known and simple methods of allocating tasks without this information are market-like negotiation protocols, like the contact net protocol (CNP) [START_REF] Smith | The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver[END_REF].

However, its characteristics in a large-scale multi-agent system (LSMAS) is poorly understood. Understanding the efficiency of CNP in LSMAS is not easy because if many manager agents simultaneously try to allocate tasks, interference among agents occurs. For example, multiple simultaneous bids are not allowed in a naive CNP. However, this restriction may considerably degrade the efficiency in a busy LSMAS, because bid/allocation processes occur almost sequentially. We can allow multiple bids to enhance concurrency and actually in [START_REF] Smith | The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver[END_REF] it is also discussed the possibility of multiple bids. However, allowing multiple bids will result in simultaneous multiple awards begin given to contractors. We can consider two solutions to this situation. First, extra awarded tasks are canceled with certain penalties (e.g. [START_REF] Sandholm | Issues in automated negotiation and electronic commerce: Extending the contract net framework[END_REF]). However, we believe that this makes the task allocation protocol so complicated that it may degrade the overall efficiency of a busy LSMAS. The second approach is to execute all awarded tasks in the contracted agents. This is simpler, but awardees cannot complete the tasks within the contracted times, resulting in significant delays in executing tasks in busy environments.

There have been a number of studies on applying it to LSMASs by assuming multiple initiations and bids in CNP [START_REF] Aknine | An extended multi-agent negotiation protocol[END_REF][START_REF] Schillo | The Eager Bidder Problem: A Fundamental Problem of DAI and Selected Solutions[END_REF][START_REF] Sugawara | Effect of alternative distributed task allocation strategy based on local observations in contract net protocol[END_REF]. For example, in [START_REF] Schillo | The Eager Bidder Problem: A Fundamental Problem of DAI and Selected Solutions[END_REF] the authors addressed the issue of the eager-bidder problem occurring in a LSMAS, where a number of tasks were announced concurrently so that a CNP with certain levels of commitment did not work well. They also proposed a CNP extension based on statistical risk management. However, the types of resources and tasks considered in these papers were quite different, i.e., they focused on exclusive resources such as airplane seats. We focus on divisible resources such as CPUs or network bandwidth, so any number of tasks can be accepted simultaneously but with reduced quality. In [START_REF] Billington | Modelling and Analysing the Contract Net Protocol -Extension Using Coloured Petri Nets[END_REF] it was also discussed the extension of CNP to allow multiple initiations and bids based on colored Petri nets. There have been other extensions that have introduced brokers [START_REF] Kinnebrew | Efficient allocation of hierarchically-decomposable tasks in a sensor web contract net[END_REF] and personal agents [START_REF] Fan | An Extended Contract Net Protocol Based on the Personal Assistant[END_REF]. However, these studies have focused on reducing the communication overhead in LSMAS. In [START_REF] Sugawara | Effect of alternative distributed task allocation strategy based on local observations in contract net protocol[END_REF] it was proposed an award strategy in which two different strategies were alternatively selected by statistically analysing bid values to improve overall efficiency. However, as their method could only be applied to a set of tasks whose costs were in a certain limited range, its applicability was severely restricted.

We adopt a simpler approach for a busy LSMAS in which all awarded tasks are executed in the awardees. Instead, we reduce the probability of multiple awards given to lower-performance agents, by extending the method in [START_REF] Sugawara | Effect of alternative distributed task allocation strategy based on local observations in contract net protocol[END_REF], because multiple awards to these types of agents are the major reason for degraded performance. The negative effect of multiple awards on a system's efficiency is strongly affected by the busyness or task loads of LSMAS. If the environment has a low load, hardly any multiple awards occurs; thus, managers can award tasks to the best bidders without having to make careful selections. However, the chance of multiple awards also increases according to the increase in task loads and thus the simple strategy of making awards in which a manager selects the best bidder becomes inappropriate. Lower-performing agents may be identified as the best bidders by multiple managers, particularly in busier situations, and thus be awarded multiple tasks simultaneously; this will considerably reduce performance. We tried to reduce the probability of multiple awards in our approach when the chance of bids going to lower performing agents had increased. Managers have to select the awardees by carefully understanding the states of their local environment to achieve this. This paper is organized as follows. Section 2 describes the model and raises issues addressed in this paper. We then compare a naive award strategy with a probabilistic award in which non-best agents are selected to allocate tasks. We then propose a method with which managers decide the award strategies based on the statistical analysis only involving light computation. The experimental results revealed that the proposed method could perform well in a busy environment.

Problem Description

Overview and Issues

We define a simple extension of CNP in which simultaneous multiple initiations by different managers and multiple bids to different managers are allowed. First, let A = {1, . . . , n} be a set of agents and t be a task. A is the disjoint union of M = {m 1 , . . . , m Nm }, which is the set of managers who allocate tasks, and C = {c 1 , . . . , c Nc }, which is the set of contractors who execute the allocated tasks. Contracts have different capabilities which affect the time required to complete the assigned tasks. Let us assume that |A| is large (on the order of thousands) and the agents are widely distributed, like servers on the Internet. This also means that communications between agents incur some delay. For manager m ∈ M, we define the concept of the scope, S m , which is the set of agents that m knows, and m can announce tasks to all or a part of S m .

We have to consider a number of issues to avoid inefficiency due to multiple awards. First, task load affects the possibility of multiple awards. When an agent that has outstanding bids receives another task announcement, it will send its bid (multiple bids) and thus may receive multiple award messages. These multiple bids occur at quite a low rate if they are not busy. Even if they occur, multiple tasks are likely to be allocated to relatively efficient agents since efficient contractors are identified as the best bidders by managers, so no significant degradation to performance will occur. However, as the environment becomes busier, the chance of multiple awards being made to lowperforming agents increases and overall performance decreases. Therefore, we propose an award strategy that selects awardees to reduce the probability of multiple awards being made to lower-performing agents accomplished by identifying their task load.

Second, longer communication delay (or latency) also increases the chances of multiple awards. However, we will not discuss reduced latency, because this strongly depends on the environmental settings and agents cannot directly handle it. Instead, we focus on the managers' decisions about awardees by identifying situations in which multiple awards to low-performing agents are likely to occur, regardless of high or low latency environments.

Agents have a number of decision-making strategies that may affect overall performance besides the award strategy. First, manager m ∈ M having a task announces a call-for-bid message to contractors that are selected from its scope, S m , on the basis of an announcement strategy. Then, agents decide whether they should act on the received call-for-bid messages or not using a bid strategy. Here, we assume simple announcement and bid strategies, i.e., an announcement strategy is where m selects all or N agents from S m randomly, where N is a positive integer, and the bid strategy is where an agent always bids for call-for-bid messages if it can execute associated tasks. These strategies also play important roles in improving overall efficiency, such as restricting the numbers of multiple bids and announcement messages. However, we particularly focused on award strategies since we were concerned about the negotiations for task allocations to prevent multiple awards being made by appropriately selecting the awardees according to the received bid messages.

Because naive CNP involves a timeout basis to receive response messages from others, it is inefficient in large and busy environments. Thus, we made use of regret messages, which were sent in the award phase to contractors who were not awarded the contract, to prevent long waits for bids and award messages (as in [START_REF] Xu | The Evolution of the Contract Net Protocol[END_REF]).

Model of Agents and Tasks

For task t, let r t = {r1 t , . . . , r d t } be the set of required resources (or functions) to execute this, where r k t ≥ 0 is integer. Agent i is denoted by tuple,

(α i , loc i , S i , Q i ), where α i = (a 1 i , . . . , a d i )
is the agent's capabilities, and a h i corresponds to the h-th resource and a h i ≥ 0; a h i = 0 indicates agent i does not have the h-th resource. Element, loc i is the location of i, and Q i is a finite queue where the tasks allocated to i are temporarily stored. The set, S i (⊆ A), is i's scope.

We assume a discrete time for any time descriptions. A unit of time is called a tick. The execution time of t by i is:

γ i (t) = max 1≤h≤d r h t /a h i , (1)
where x denotes the ceiling function. The metric between the agents, δ(i, j), is based on their locations, loc i and loc j . It is only used to calculate communication delay; the time required for message transfer between agents i and j is δ(i, j)/D , where D is the speed factor for passing messages. Parameter L (≥ 0) is called the task load, meaning that L tasks on average are generated according to a Poisson distribution every tick. These are then randomly assigned to different managers.

Task Assignment

When manager m receives a task, t, it immediately initiates the CNP modified for LS-MAS: It first sends announcement messages to the contractors selected from its scope in accordance with the announcement strategy. Each of these contractors sends back a bid message with a certain bid value. The bid values might include parameters such as the price for executing the task, the quality of the result, or a combination of these values. We assume that their bid values contain the estimated times for completing t, because we are concerned with the efficiency of processing in LSMAS. This time is calculated as follows in contractor c:

γ c ( t) + ∑ t∈Qc γ c (t) + β, ( 2
)
where β is the execution time required for the task currently being executed. For multiple bids, c might have a number of outstanding bids. These bids are not considered to calculate the estimated required time because it is uncertain whether they will be accepted 1 . Then, m selects an awardee, on the basis of the award strategy and sends it an award message with the announced task, t.

When contractor c is awarded a task, it immediately executes it if it has no other tasks. If c is already executing a task, the new task is stored in Q c , and the tasks in Q c are executed in turn.

Performance Measures

We assumed that manager agents could observe the completion time for task t, which is the elapsed time from the time the award message is sent to the time the message indicating that t has been completed is received. The completion time thus includes the communication time in both directions, the queue time, and the execution time. We evaluated overall performance using the average completion time observed in all managers; this is denoted by ℘. A shorter average completion time is preferable.

Since the queue length of agent i is bounded, some allocated subtasks might be dropped. The numbers of dropped tasks are also another measure of performance. However, no dropped tasks occur unless the systems are overloaded so they can only be used in limited situations. Thus, we use them to identify upper limit of the performance for the entire system.

Awards to non-best bidders and its features

It is plausible for a manager to select the best bidder in the award phase. This strategy is called the best awardee strategy (BAS). However, multiple awards are likely to occur with the increase in task loads. A simple award strategy for alleviating multiple awards is to allocate some tasks to non-best contractors by introducing randomness to some degree in the award phase [START_REF] Sugawara | Effect of alternative distributed task allocation strategy based on local observations in contract net protocol[END_REF].

Let {c 1 , . . . , c p } be contractors that bid on the announced task. The estimated completion time in the bid message from c i is denoted by b ci . The probabilistic awardee selection strategy with the fluctuation factor, f (which is denoted by PAS f ) is the award strategy in which the manager selects the awardee according to the following probability:

Pr(c i ) = 1/(b ci ) f ∑ p j=1 1/(b cj ) f , (3)
where non-negative integer f is the fluctuation factor. A smaller value for f means less randomness when awardees are selected. We experimentally investigated the characteristics of BAS and PAS f with various task loads. We set |C| = 500 and |M| = 10, 000. Only one type of task, t 3000 , whose required resource r t3000 was {3000} (so d = 1) was used in this experiment (Exp. 1). For any c i ∈ C, a different capability was assigned to c i so that the values of 3000/a 1 ci would be uniformly distributed over the range of 25-120; thus, the values of a 1 ci ranged from 25 -120. We assumed that the manager agents could not do the tasks themselves forcing them to assign the tasks to agents who could. The agents were randomly placed on a 150 × 150 grid with a torus topology to which a Euclidean distance was introduced as its metric. Manager m's scope, S m , was the set of contractor agents whose distance from m was less than 10.0 because it was implausible to allocate tasks to distant agents. We also set f = 3 and D = 2.5. Thus, tasks maximally took five ticks to send messages to known contractors. We defined these values by assuming that a tick was around 1 ms. The number of announcement messages, N , and the queue length, |Q i |, were set to 20.

Figure 1 (a) plots the average completion times varying according to the values for task load, L. It indicates that average performance with BAS, ℘(BAS), is higher than that with PAS f , ℘(PAS f ), when task load was low or quite high but PAS f outperformed BAS, otherwise. Note that the vertical dotted line when L = 165 indicates the limit for the capability of the entire system. Actually, Fig. 1 (b), showing the numbers of dropped tasks per tick with BAS indicates that dropped tasks rapidly increased if L ≥ 165. 2To clearly see the differences between their performance, we define the performance ratio w.r.t. BAS as:

V(str) = ℘(BAS) -℘(str) ℘(BAS) × 100, (4)
where ℘(str) indicates the average completion times with the award strategy specified by the variable, str. Fig. 1 (c), expressing the relationship between V(PAS f ) and the task load, indicates that when L was low (L ≤ 70), V(PAS f ) was minus and performance with PAS f was maximally 40% lower than that with BAS. This tendency was also observed when the system was beyond the upper limit of all agents' capabilities (L ≥ 160). However, when it was moderately busy and near (but less than) the upper limit for the entire performance (80 ≤ L ≤ 160), performance with PAS f was maximally 20% higher than that with BAS. We believe that this is an important characteristic: when L is low, any simple strategy can result in acceptable performance and when it is beyond the upper limit for the system, no strategy can do all tasks within acceptable time limits.

The system must exert its full capabilities, especially near its upper limit. The variations in performance in Fig. 1 (c) were caused by the combination of the probabilities of multiple awards and awards to non-best bidders with PAS f . When L was low, multiple awards rarely occurred. However, as non-best bidders were awarded with PAS f , V(PAS f ) became minus. All contractors' queues, on the other hand, were almost full if L was beyond the system's limit. Thus, it was better to assign tasks to the best bidders, because (1) lower-performing agents were also so busy that there were no benefits by allowing some tasks to be shifted to these agents, and (2) there were so many tasks that the awards to non-best bidders resulted in other multiple bids in lowperforming agents. In contrast, when L was moderate and less than the upper limit, busy and unbusy agents co-existed, i.e., relatively high performing agents had a number of tasks in their queues but low performing agents had few assigned tasks. Thus, managers might assign tasks to low-performing agents, resulting in making simultaneous multiple awards to them. This degraded overall performance. However, managers with PAS f probabilistically awarded these agents to avoid multiple awards, to some degree.

Proposed Method

As PAS f could attain approximately 20% better performance than BAS in situations near the upper limit of the system, this improvement was not small. We want to emphasize that the system must exert its potential capabilities in busy situations, especially near its upper limit of task load, but achieving this is not easy. However, PAS f also drastically worsens performance in other situations. Thus, if managers could select an appropriate award strategy by estimating the current degrees of task loads in their local regions, they could take advantage of PAS f .

The variance and standard deviation (SD) of bid values from local contractors can provide the information to estimate task loads in local regions. We introduced phantom tasks to achieve this, which are announced by managers even though no contractors are awarded to them. Phantom tasks were proposed in [START_REF] Sugawara | Effect of alternative distributed task allocation strategy based on local observations in contract net protocol[END_REF], but their use was quite restricted. We used it more actively in our proposed strategy; when a manager announces a task, t, it also announces two phantom tasks. The first one requires much smaller resources, say 1/6, than those of t and this is denoted by p s t . The second requires identical to or slightly more resources than those of t and this is denoted by p l t . Then, the manager calculates the SDs of bid values for p s t and p l t received from local agents. These SDs for p s t and p l t correspond to σ s and σ l . We then investigated changes in the average values of σ l -σ s with variable task loads in an environment identical to that in Exp. 1. Since the task was t 3000 , the resources required for p l t3000 and p s t3000 were set to {3001} for the former and {500} for the latter. The results are plotted in Fig. 2 (a).

This graph shows that σ l > σ s in BAS when L is low or beyond the limit, but σ s > σ l , otherwise. We can explain this phenomenon as follows. When L is low, the distribution of bid values for p l t and p s t (see Figs. 2 (b-1) and (b-2), which illustrate the distributions of bid values) directly reflects the capabilities of contractors. Thus, σ l , the SD of bid values for p l t , is larger than σ s , which is the SD of bid values for p s t . However, in moderately busy situations (L is between 80 and 160) there are chances for lower-performing agents to be awarded, because only higher performing agents have a number of tasks being queued and executed (Fig. 2 (c-1)). Consequently, σ s > σ l held in this situation (cf. Figs. 2 (c-1) and (c-2)). When the system was over the upper limit, all contractors already had a number of tasks waiting in their queues, and their estimated completion times of the tasks at the end of the queues were quite similar. Thus, the estimated completion times for the new announced tasks again reflected the performance of contractors. In contrast, managers with PAS f allocated tasks with some fluctuations; thus, σ l > σ s was always positive as seen in Fig. 2(a).

From this discussion, we propose a novel award strategy in which BAS or PAS f is selected using the phantom tasks associated with the requesting task. For task t, we generate phantom tasks, p l t and p s t , whose required resources are r p l t = {r 1 t +α, . . . , r d t +α} and r p s t = {r 1 t /β, . . . , r d t /β}, where α is a small integer equal to or near 0 (in the experiments that follow, we set (α, β) = (1, 6)). Then, managers announce p l t and p s t as well as t. Because managers adopt an announcement strategy in which the announcement messages are sent to N agents randomly selected for individual scopes, these announcement messages are not sent to the same set of agents. However, we assumed that the task load states could be estimated by a survey of random sampling. 3 Then, contractors send back the bid messages for the received tasks. Because they cannot distinguish normal from phantom tasks, they adopt the same bid strategy in their decisions. Managers then calculate the SDs, σ l and σ s , and select BAS if σ l -σ s > 0 and PAS f if σ l -σ s ≤ 0, as the award strategy that is used to determine the awardee for t. The proposed method of selecting the award strategy is called award selection according to bid variances (ASBV).

Experimental Evaluation and Remarks

We experimentally evaluated ASBV. The experimental setting for this experiment (Exp. 2) was identical to that of Exp. 1. The performance ratios w.r.t. the BAS of ASBV, ℘(ASBV), are plotted in Fig. 3 (a).

This graph indicates that ASBV outperformed the selected strategy ratios with BAS when L ≥ 70 and those with PAS f near the upper limit for the system (around L = 150 to 165). As was previously mentioned, this feature of ASBV is important for all agents in LSMAS to exert all their capabilities.

We also examined the ratios of selected strategies (RSS), i.e., the number of managers that selected BAS to that of managers that selected PAS f . The results are plotted in Fig. 3 (b), which indicates that when task load was low, managers only selected BAS. Then, they increased the chance of selecting PAS f according to the increase in the task load. However, the selections of BAS and PAS f in managers balanced at certain ratios to keep the values of σ l -σ s positive. We think that this balanced selection by local autonomous decisions by managers could improve overall performance near the upper limit for the system (around L = 160). Fig. 3 (a) indicates that ASBV performed slightly worse when L was low although all managers adopted BAS: The manager selected the awardee in ASBV after all bids for t, p l t , and p s t had arrived. Therefore, it took slightly longer than that in BAS and PAS f .

We investigated influences with resources required by tasks, the fluctuation factor in PAS f , and communication delay on overall performance with ASBV. We conducted a number of experiments to do this. The generated tasks were t 5000 (so their required resources were r t5000 = {5000}. The resources required by tasks are denoted by subscripts, such as t 5000 , after this) in Exp. 3 whose results are plotted in Figs. 4 (a) and (b). Five different tasks, t 2000 , t 3000 , t 4000 , t 5000 , and t 6000 were randomly generated in Exp. 4 whose results are plotted in Fig. 4 (c). The generated tasks in Exps. Figures 4 (a) and (c) indicate that ASBV could also perform better near (but less than) the upper limits of the entire capabilities for tasks that required different resources and for mixtures of different tasks. Note that the upper limits for task loads are approximately 100 and 125 in Exps. 3 and 4. The curves for improvement ratios in these figures are similar to that in Exp. 2. Figure 4 (b) has the values of RSS in Exp. 3 and these are also quite similar to that in Exp. 2. Note that we omitted the figure for RSS in Exp. 4 because it was almost identical to that in Exp. 3.

The length of communication delay affected improvements to the proposed method, because it also affected the chances of simultaneous multiple awards being made. When it was long (D = 1.25), the improvement ratios increased more than those in Exp. 2 (cf. Figs. 4 (d) and 3 (a)). Here, as multiple awards occurred more frequently, performance with PAS was degraded more significantly. However, as managers with ASBV selected non-best bidders, improvements with ASBV increased. Of course, when communication delay was short, the improvement ratios decreased as we can see from Fig. 4 (e). the managers with ASBV adopted PAS f more as award strategy to reduce the chance of multiple awards being made. These experimental results suggest that the proposed strategy is more useful in LSMAS that are widely distributed where their communication delay is significant.

The effect of fluctuation factors also yielded interesting features. If we compare the graphs in Figs. 3 (a), 4 (g), and (h), improvements in their performance when L was between 80 and 165 were almost similar. However, when L was beyond the limit of capabilities, performance was slightly lower when fluctuation factor f was two (therefore, the degree of randomness was high). Only a small amount of randomness was appropriate in the latter situations but condition f = 2 provided too much randomness to awardee decisions even if RSS was larger. However, when L was between 80 and 165, the proposed strategy could control the values of RSS as shown in Fig. 4 (h); actually, managers with ASBV could adaptively change the values of RSS according to the degrees of randomness provided by PAS f (f = 2, 3, or 4) only when randomness was necessary. Note that the values of RSS always differed according to the values of speed factor in Fig. 4 (f) since communication delay always existed regardless of the task loads. These experiments indicate that ASBV adaptively introduced a degree of randomness, since its selection of award strategy was based on the observed real-time data.

Conclusion

We proposed an award strategy called award selection according to bid variances, for CNP-like negotiation protocols, in which two award strategies were alternatively selected by estimating local task loads around individual managers based on the statistical analysis of received bid messages for phantom tasks. We then experimentally evaluated and investigated the proposed strategy in various environments. The results indicated that it could outperform naive and probabilistic methods, especially near the upper limits of capabilities for the entire system. This is quite an important characteristic of actual applications as it can exert potential capabilities when really required. It also performed better in wide-area distributed systems in which communication delay was not short. We plan to conduct theoretical analysis to understand the phenomena described in this paper.

Fig. 1 .

 1 Fig. 1. Results of preliminary experiment (Exp. 1).

Fig. 2 .

 2 Fig. 2. Bid values in unbusy and moderately busy states.

Fig. 3 .

 3 Fig. 3. Performance and selected strategy ratios in Exp. 2.

  5 and 6 are identical to those in Exp. 2, but the speed factor for message passing, D, was set to 1.25 and 5 in Exp. 5. Further, fluctuation factor f was set to two and four in Exp. 6. The results for Exp 5 are plotted in Figs. 4 (d) (e) and (f) and those for Exp. 6 are plotted in Figs. 4 (g) (h) and (i).

Figure 4 (Fig. 4 .

 44 Fig. 4. Performance ratios and RSS in Exps. 3 to 7.

Actually, we also examined a case in which agents considered the expected values of execution times for outstanding bids; however no significant differences were observed.

We plotted the numbers of dropped tasks only with BAS in Fig.1 (b), but they were almost identical to those with PAS f .

Of course, we allowed multiple bids, where managers could send the same set of agents for these three tasks. The proposed method could slightly reduce the overhead for processing the messages for phantom tasks.

Acknowledgement This work was in part supported by JSPS KAKENHI Grant Numbers 23650075 and 22300056.


Falilat Jimoh
email: falilat.jimoh@hud.ac.uk

Lukáš Chrpa
email: l.chrpa@hud.ac.uk

Mauro Vallati
email: m.vallati@hud.ac.uk

Autonomic System Architecture: an Automated Planning Perspective

Keywords: automated planning, urban traffic control, autonomic systems

Control systems embodying artificial intelligence (AI) techniques tend to be "reactive" rather than "deliberative" in many application areas. There arises a need for systems that can sense, interpret and deliberate with their actions and goals to be achieved, taking into consideration continuous changes in state, required service level and environmental constraints. The requirement of such systems is that they can plan and act effectively after such deliberation, so that behaviourally they appear self-aware. In this paper, we focus on designing a generic architecture for autonomic systems which is inspired by the Human Autonomic Nervous System. Our architecture consists of four main components which are discussed in the context of the Urban Traffic Control Domain. We also highlight the role of AI planning in enabling selfmanagement property of autonomic systems. We believe that creating a generic architecture that enables control systems to automatically reason with knowledge of their environment and their controls, in order to generate plans and schedules to manage themselves, would be a significant step forward in the field of autonomic systems.

Introduction

Autonomic systems (AS) are required to have an ability to learn process patterns from the past and adopt, discard or generate new plans to improve the process control. The ability to identify the task is the most important aspect of any AS element, this enables AS to select the appropriate action when healing, optimising, configuring or protecting itself. Advanced control systems should be able to reason with their surrounding environment and take decision with respect to their current situation and their desired service level. This could be achieved by embedding situational awareness into them and given the ability to generates necessary plans to solve their problem themselves with little or no human intervention -we believe this is the key to embody autonomic properties in systems. Our autonomic system architecture is inspired by the functionality of the Human Autonomic Nervous System (HANS) that handles complexity and uncertainty with the aim to realise computing systems and applications capable of managing themselves with minimum human intervention.

The need for planning and execution frameworks has increased interests in designing and developing system architectures which use state-of-the-art plan generation techniques, plan execution, monitoring and recovery in order to address complex tasks in real-world environments [START_REF] Myers | Towards a framework for continuous planning and execution[END_REF]. An example of such an architecture is T-Rex (Teleo-Reactive EXecutive): a goal oriented system architecture with embedded automated planning for on-board planning and execution for autonomous underwater vehicles to enhance ocean science [START_REF] Mcgann | A Deliberative Architecture for AUV Control[END_REF][START_REF] Pinto | Experiments with Deliberative Planning on Autonomous Underwater Vehicles[END_REF]. Another recent planning architecture, PELEA (Planning and Execution LEarning Architecture), is a flexible modular architecture that incorporates sensing, planning, executing, monitoring, replanning and even learning from past experiences [START_REF] Jimènez | Integrating planning, execution, and learning to improve plan execution[END_REF]. The list of system architectures incorporating automated planning is, of course, longer, however, many architectures are designed as domain-specific.

In our previous work, we introduced the problem of self-management of a road traffic network as a temporal planning problem in order to effectively navigate cars throughout a road network. We demonstrated the feasibility of such a concept and discuss our evaluation in order to identify strengths and weaknesses of our approach and point to some promising directions of future research [START_REF] Shah | Modelling road traffic incident management problems for automated planning[END_REF][START_REF] Jimoh | Enabling autonomic properties in road transport system[END_REF]. In this paper, we propose an architecture inspired by Human Autonomic Nervous System (HANS) which embodies AI planning in order to enable autonomic properties such as self-management. This architecture is explained on the example of Urban Traffic Control domain.

Urban Traffic Control

The existing urban traffic control (UTC) approaches are still not completely optimal during unforeseen situations such as road incidents when changes in traffic are requested in a short time interval [START_REF] Roozemond | Using intelligent agents for pro-active, real-time urban intersection control[END_REF][START_REF] De Oliveira | Multiagent learning on traffic lights control: Effects of using shared information[END_REF]. This increases the need for autonomy in urban traffic control [START_REF] Yang | Intelligent cooperation control of urban traffic networks[END_REF][START_REF] Bazzan | A distributed approach for coordination of traffic signal agents[END_REF][START_REF] Dusparic | Autonomic multi-policy optimization in pervasive systems: Overview and evaluation[END_REF]. To create such a platform, an AS system needs to be able to consider the factors affecting the situation at hand: the road network, the state of traffic flows, the road capacity limit, accessibility or availability of roads within the network etc. All these factors will be peculiar to the particular set of circumstances causing the problem [START_REF] Jimoh | Enabling autonomic properties in road transport system[END_REF]. Hence, there is a need for a system that can reason with the capabilities of the control assets, and the situation parameters as sensed by road sensors and generate a set of actions or decisions that can be taken to alleviate the situation. Therefore, we need systems that can plan and act effectively in order to restore an unexpected road traffic situation into a normal order. A significant step towards this is exploiting Automated Planning techniques which can reason about unforeseen situations in the road network and come up with plans (sequences of actions) achieving a desired traffic situation.

Role of AI Planning in Urban Traffic Control

The field of Artificial Intelligence Planning, or AI Planning, has evidenced a significant advancement in planning techniques, which has led to development of efficient planning systems [START_REF] Gerevini | An approach to temporal planning and scheduling in domains with predictable exogenous events[END_REF][START_REF] Coles | Planning with problems requiring temporal coordination[END_REF][START_REF] Penna | Upmurphi: a tool for universal planning on pddl+ problems[END_REF][START_REF] Eyerich | Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning[END_REF] that can input expressive models of applications. The existence of these general planning tools has motivated engineers in designing and developing complex application models which closely approximate real world problems. Thus, it is now possible to deploy deliberative reasoning to real-time control applications [START_REF] Löhr | A planning based framework for controlling hybrid systems[END_REF][START_REF] Ferber | On modeling the tactical planning of oil pipeline networks[END_REF][START_REF] Burns | Anticipatory on-line planning[END_REF]. Consequently, AI Planning now has a growing role in realisation of autonomic in control systems and this architecture is a leap towards the realisation of such goal. The main difference between traditional and our autonomic control architecture is depicted in Figure 1. Traditionally, a control loop consists of three steps: sense, interpret and act [START_REF] Gopal | Control systems: principles and design[END_REF]. In other words, data are gathered from the environment with the use of sensors, the system interprets information from these sensors as the state of the environment. The system acts by taking necessary actions which is feedback into the system in other to keep the environment in desirable state. Introducing deliberation in the control loop allows the system to reason and generate effective plans in order to achieve desirable goals. Enabling deliberative reasoning in UTC systems is important because of its ability to handle unforeseen situations which has not been previously learnt nor hard-coded into a UTC. This helps to reduce traffic congestion and carbon emissions. 3 Automated Planning AI Planning deals with the problem of finding a totally or partially ordered sequence of actions whose execution leads from a particular initial state to a state in which a goal condition is satisfied [START_REF] Nau | Automated Planning: Theory & Practice[END_REF]. Actions in plans are ordered in such a way that executability of every action is guaranteed [START_REF] Fox | PDDL2.1: An extension of PDDL for expressing temporal planning domains[END_REF]. Hence, an agent is able to transform the environment from an initial state into a desired goal state [START_REF] Gupta | IMACS: A case study in real-world planning[END_REF][START_REF] Garrido | A temporal planning system for timeoptimal planning[END_REF]. A planning problem thus involves deciding "what" actions to do, and "when" to do them [START_REF] Gerevini | Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners[END_REF][START_REF] Hoffmann | The FF planning system: Fast plan generation through heuristic search[END_REF].

In general, state space of AI planning tasks can be defined as a statetransition system specified by 4-tuple (S, A, E, γ) where:

-S is a set of states -A is a set of actions -E is a set of events -γ : S × (A ∪ E) → 2 S is a transition function
Actions and events can modify the environment (a state is changed after an action or event is triggered). However, the difference between them is that actions are executed by the agent while events are triggered regardless of agent's intentions. Application of an action a (or an event) in some state s results in a state in γ(s, a) (γ(s, a) contains a set of states). It refers to non-deterministic effects of actions (events).

Classical planning is the simplest form of AI planning in which the set of events E is empty and the transition function γ is deterministic (i.e. γ : S × A → S). Hence, the environment is static and fully observable. Also, in classical planning actions have instantaneous effects.

Temporal planning extends classical planning by considering time. Actions have durative effects which means that executing an action takes some time and effects of the action are not instantaneous. Temporal planning, in fact, combines classical planning and scheduling.

Conformant planning considers partially observable environments and actions with non-deterministic effects. Therefore, the transition function γ is nondeterministic (i.e. γ : S × A → 2 S ). The set of events E is also empty.

For describing classical and temporal planning domain and problem models, we can use PDDL [START_REF] Mcdermott | PDDL-the planning domain definition language[END_REF], a language which is supported by the most of planning engines. For describing conformant planning domain and problem models, we can use PPDDL [START_REF] Younes | The First Probabilistic Track of the International Planning Competition[END_REF] (an extension of PDDL) or RDDL [START_REF] Sanner | Relational dynamic influence diagram language (RDDL): Language description[END_REF], languages which are supported by many conformant planning engines. Our architecture can generally support all the above kinds of planning.

Autonomic Computing Paradigm

We use the term "autonomic system" rather than autonomic computing to emphasise the idea that we are dealing with a heterogeneous system containing hardware and software. Sensors and effectors are the main component of this type of autonomic system architecture [START_REF] Ganek | The dawning of the autonomic computing era[END_REF]. AS needs sensors to sense the environment and executes actions through effectors. In most cases, a control loop is created: the system processes information retrieved from the sensors in order to be aware of its effect and its environment; it takes necessary decisions using its existing knowledge from its domain, generates effective plans and executes those plans using effectors. Autonomic systems typically execute a cycle of monitoring, analysing, planning and execution [START_REF] Lightstone | Seven software engineering principles for autonomic computing development[END_REF].

System architecture elements are self-managed by monitoring, behaviour analysing and the response is used to plan and execute actions that move or keep the system in desired state. Overall self-management of a system is about doing self-assessment, protection, healing, optimisation, maintenance and other overlapping terms [START_REF] Ganek | The dawning of the autonomic computing era[END_REF]. It is important to stress that these properties are interwoven. The existence of one might require the existence of the others to effectively operate. For instance, a self-optimisation process might not be complete until the system is able to self-configure itself. Likewise, an aspect of a proactive selfhealing is an ability of the system to self-protect itself. Any system that is meant to satisfy the above objectives will need to have the following attributes:

-Self-awareness of both internal and external features, processes resources, and constrains -Self-monitoring it existing state and processes and -Self-adjustment and control of itself to the desirable/required state -Heterogeneity across numerous hardware and software architectures

Case Study of Human Autonomic Nervous System

Human breathing, heartbeat, temperature, immune system, repair mechanisms are all to a great extent controlled by our body without our conscious management. For instance, when we are anxious, frightened, ill or injured, all our bodily functions evolves to react appropriately. The autonomic nervous system has all the organs of the body connected to the body central nervous system which takes decisions in order to optimise the effective functioning of other organs in the body. The sensory cells, senses the state of each organs in relation to the dynamically changing internal and external environment. This information is sent to the brain for interpretation and decision making. The execution of relevant action is sent back to the organs via the linking nerves in real time. This process is repeated trillions of time in seconds within the human body system.

System Architecture

Our system architecture is divided into four main blocks. Description of each block is given in the subsequent subsections, however, due to space constraints we cannot go into very details. The entire architecture comprises of a declarative description of the system under study; the individual components that make up such system; the dynamic environment that can influence the performance of such system ; its sensing and controlling capabilities and it ability to reasoning and deliberate.

Our system architecture consists of four main blocks:

-The System Description Block (SD)

The System Description Block (SD)

The system description block stores the information about the environment. Formally, the system description block is a triple D, X, S where -D is a finite set of system components -X is a finite set of artefacts -S is a set of states, where each state s i ∈ S is a set of assignments f k (y l ) = v m where y l ∈ D ∪ X and v m is a value of y l System components are parts of the system which are fully controlled by the system. In human body, components are, for example, legs, kidney, hands, lungs etc. Artefacts refer to external objects which are in the environment where the system operates. In analogy to human body, artefacts are objects the human body can interact with. States of the system capture states of all the components and artefacts which are considered. For example, a stomach can be empty or full, water in a glass can be cold or hot etc. In Urban Traffic Control (UTC) domain, for instance, SD consists of a declarative description of the road network of an area that need to be controlled while optimising traffic flow pattern. The components are all the objects that can be controlled by the system, for example, traffic control signal heads, variable message signs(VMS) and traffic cameras. The artefacts, objects which cannot be directly controlled by the system such as roads layout and infrastructures.

The Sensor and Effector Block (SE)

A human body monitors a state of its components (organs), where one can feel pain, hunger, cold etc., and states of artefacts (external objects) with sensors such as skin, eyes, nose etc. SE is responsible for sensing in order to determine a current state of the system (environment) which is stored in SD. Different sensors can provide an information about states of the system components and artefacts. Since the outputs of the sensors might not directly correspond with the representation of states. Formally, we can define a function η : O → S which can transform a vector of outputs of different sensors (O is the set of all such possible vectors) to a state of the system (S is a set of all possible states of the system). For example, in the UTC domain, sensing can be done by road sensors and CCTV cameras.

SE is also responsible for executing plans (sequences of actions) given by the Planning and Action block in Figure 2. Executing actions is done via system components which indirectly affect artefacts as well. In the UTC domain, a plan to change a traffic light from red to green would cause vehicles to start moving through the intersection. Since we have to consider uncertainty, after executing a sequence of actions, the sensors sense the current state, and if the current state is different from the expected one, the information is propagated to the Planning and Action block which provides a new plan.

The Service Level Checker (SLC)

The service level checker, as the name implies, repeatedly checks the service level of the entire system to see if the system is in a 'good condition'. It gets the current state of the system from SE and compare it with the 'ideal' service level. If the current state is far from being 'ideal', then the system should act in order to recover its state to a 'good condition'. In analogy to a human body, if it is infected by some virus, the body cells detect this anomalies and start acting against the virus. Formally, we can define an error function : S → R + 0 which determines how far the current state of the system is from being 'ideal'. (s) = 0 means that s is an 'ideal' state. If a value of the error function in the current state is greater than a given threshold, then SLC generates goals (desired states of a given components and/or artefacts) and passes them to the Planning and Actions block (see below).

An example of this in UTC domain can be seen in an accident scene at a junction. The 'ideal' service level for such a junction is to maximise traffic flow from the junction to neighbouring routes. The present state of the system shows that the traffic at that junction is now static with road sensors indicating static vehicles. This situation is not 'ideal', the error function in such a state is high, hence, new goals are generated by SLC to re-route incoming traffic flowing towards such intersection. It is also possible to alter the error function by an external system controller. For instance, an autonomic UTC system can also accept inputs from the traffic controller (Motoring Agencies). This means that the system behaviour can be altered by the user if needed. This gives the user a superior autonomy over the entire autonomic system. For instance, despite the human body system having the capacity to fight virus (as mentioned before), an expert (doctor) still may have control, so he can, for instance, prescribe anesthetic to reduce the way the body response to pains. This anesthetic act on the brain or peripheral nervous system in to suppress responses to sensory stimulation. Our architecture is thus designed to have autonomy over it entire component and artefacts and robust enough to accommodate sovereign external user control.

The Planning and Action Block (PA)

PA can be understood as a core of deliberative reasoning and decision making in the system. This is 'the brain' of our architecture. PA receives the current state of the system from SE, and goals from SLC. Then produces a plan which is then passed to SE for execution. However, it is well known from planning and execution systems [START_REF] Fox | Plan-based policy-learning for autonomous feature tracking[END_REF] that producing a plan given a planning problem does not guarantee its successful execution. As indicated before SE, which is responsible for plan execution, verifies whether executing an action provided a desired outcome. If the outcome is different (from some reason), then this outcome is passed back to PA which re-plans. It is well known that even classical planning is intractable (PSPACE-complete). Therefore, PA might not guarantee generating plans in a reasonable time. Especially, in a dynamic environment a system must be able to react quickly to avoid imminent danger. Therefore, SLC generates goals which are easy to achieve when the time is crucial.

In analogy to human beings, if hungry they, for instance, have to plan how to obtain food (go shopping). This might not be a very time critical task such as if one is standing on the road and there is a car going fast against him he has to act quickly to avoid a (fatal) collision.

In the UTC domain, if some road is congested, then the traffic is navigated through alternative routes. Hence, PA is responsible for producing a plan which may consist of showing information about such alternative routes on variable message signs and optimising signal heads towards such route.

Conclusion

In this work, we have describe our vision of self-management at the architectural level, where autonomy is the ability of the system components to configure their interaction in order for the entire system to achieve a set service level. We created an architecture that mimics Human Autonomic Nervous System (HANS). Our architecture is basically made of four main blocks which are discussed in the context of the Urban Traffic Control Domain. We describe the functionality of each block, highlighting their relationship with one another. We also highlight the role of AI planning in enabling self-management property in an autonomic systems architecture. We believe that, creating a generic architecture that enables control systems to automatically reason with knowledge of their environment and their controls, in order to generate plans and schedules to manage themselves, would be a significant step forward in the field of autonomic systems.

In a real-world scenario data such as road queues are uploaded in realtime from road sensors with traffic signals connected to a planner, we believe that our approach can optimise road traffic with little or no human intervention. In future we plan to embed our architecture into a road traffic simulation platform. We also plan to provide a deeper evaluation of our approach, especially to compare it with traditional traffic control methods, and assess the effort and challenges required to embody such technology within a real-world environment. Other aspects of improvement would include: incorporating learning into our architecture which will store plans for the purpose of re-using valid plans and save the cost of re-planing at every instance.

Fig. 1 .

 1 Fig. 1. Illustration of Autonomic System Architecture in Urban Traffic Control

Fig. 2 .

 2 Fig. 2. Diagram of our autonomic system architecture illustrating the relationship between the four main blocks