Stephen Akuma
email: akumas@uni.coventry.ac.uk

Chrisina Jayne

Rahat Iqbal

Faiyaz Doctor

Implicit Predictive Indicators: Mouse Activity and Dwell Time

Keywords: Implicit indicators, explicit rating, mouse activity, dwell time

Humans vary in their learning behaviour. It is difficult to predict the actual needs of learners through their search activity. It is also difficult to predict accurately the level of satisfaction after the learner finds a perceived relevant document. This research is a preliminary study to examine the predictive strength of some implicit indicators on web documents. An automated study was carried out and 13 participants were given 15 short documents to read and rate according to their perception of relevance to a given topic area. An investigation was carried out to examine if there exists a correlation between user generated implicit indicators and the explicit ratings. The findings show that there is a positive correlation between the dwell time and user explicit ratings. Although there was no significant correlation between mouse movement/distance and user explicit rating, there was a relationship between the homogeneous clusters of the implicit indicators and the user ratings.

Introduction

Information is constantly increasing on the internet leading to information overload.

The process of accessing relevant information is not only difficult and time consuming but also cognitively demanding [START_REF] Brusilovsky | Preface to special issue on user modeling for Web information retrieval[END_REF]. In order to support users in their search activities, search engine optimisation is required [START_REF] Grzywaczewski | Task-Specific Information Retrieval Systems for Software Engineers[END_REF]. Implicit feedback and explicit feedback are broadly used to achieve this [START_REF] Grzywaczewski | Task-Specific Information Retrieval Systems for Software Engineers[END_REF]. Both approaches focus on understanding users' behaviour and interest. In order for users to have recommended information based on their interest, a system must rate every actions of the user. In explicit feedback approach, the most common rating criterion is explicit rating -where users suggest to the system what they think about a given document or information [START_REF] Claypool | Implicit interest indicators[END_REF]. Predicting users' interest explicitly can be done by users' preference information [START_REF] Takano | An adaptive personalized recommender based on web-browsing behavior learning[END_REF]. Although explicit rating is said to be the most consistent approach in information retrieval, however, its limitation is that it can alter reading and browsing patterns [START_REF] Claypool | Implicit interest indicators[END_REF]. The implicit approach is therefore more feasible and objective measure. Implicit feedback systems understand the users' interest through the user behaviour. This saves the user the cost of providing feedback [START_REF] Zhang | Survey of user behaviors as implicit feedback[END_REF]. If the implementation of an implicit feedback system is successful, it can be as good as explicit feedback. The advantages of implicit feedback over explicit feedback include:

─ Large amount of data can be gathered with no extra cost to the searcher. ─ The interaction between a user and the system can be captured at any time. ─ With implicit feedback, users need not examine and rate items.

The adaptive engine of most feedback systems uses server-side data like page visited and link selected as its source of implicit data. The challenge in this approach is that the relevancy of a document to be recommended is simply judged by user visit and not by his/her interest on the documents. Client-side or browser approach to data (key, mouse and dwell time) collection provides an efficient alternative for accurately predicting relevant web documents [START_REF] Hauger | Using browser interaction data to determine page reading behavior[END_REF]. The aim of interpreting this usage data is to predict user's perceived relevance of a document [START_REF] Buscher | Segment-level display time as implicit feedback: A comparison to eye tracking[END_REF]. Client-side data have become common due to the fact that most browsers use JavaScript as their common technology. Claypool et al. [START_REF] Claypool | Implicit interest indicators[END_REF] used "The Curious Browser" to examine promising implicit indicators that can predict relevant web documents. They found out that time spent on a page is a good indicator that signifies user's interest on a page. Kim et al [START_REF] Kim | Implicit indicators for interesting Web pages[END_REF] also supported this assertion with a focus on user active time on a page and they added that duration on a page is closely related to user's interest. The concept of contextualization was not examined by [START_REF] Claypool | Implicit interest indicators[END_REF][START_REF] Kim | Implicit indicators for interesting Web pages[END_REF].

In this work, we attempt to examine and correlate some implicit indicators with user explicit ratings based on 15 web documents. We juxtaposed user's interaction on 15 web documents and their explicit ratings of how relevant the documents are to the specific task. We used mouse activity and dwell time to represent the user's interest.

The remaining part of the paper is organized as follows: Section 2 presents a review of related work. Section 3 describes in detail the implicit indicators studied. Section 4 is on the approach used for the study. Section 5 presents and analyse the results. Section 6 is the discussion. Section 7 is the conclusion and future work.

Related work

Morita and Shinoda [START_REF] Morita | Information Filtering Based on User Behaviour Analysis and Best MatchText Retrieval[END_REF] used implicit approach to transparently capture data. They investigated if the time a reader spends reading Usenet news article can be an important source for measuring relevance. They infer that the longer a user spends reading an article, the more interesting it is to the user. Nichols [START_REF] Nichols | Implicit Rating and Filtering[END_REF] discussed the benefits of implicit feedback and he listed some behavioural characteristics that can be used as a source for implicit feedback. He however did not conduct any experiment to examine and validate the efficacy of the implicit indicators listed. Oard et al [START_REF] Oard | Implicit feedback for recommender systems[END_REF] studied how implicit indicators can be used in place of explicit ratings for a recommender system. They centred their observation on three broad categories of retention, examination and reference as useful criteria for making prediction. They also found that reading time is a good indicator for measuring relevance. This assertion was affirmed by [START_REF] Huai | Study on ontology-based personalized user modeling techniques in intelligent information retrievals[END_REF][START_REF] Kellar | Effect of task on time spent reading as an implicit measure of interest[END_REF][START_REF] Zhang | Survey of user behaviors as implicit feedback[END_REF]. Claypool et al. [START_REF] Claypool | Implicit interest indicators[END_REF] studied the relationship that exists between different implicit ratings and explicit ratings on a particular webpage. They developed a web browser ("The Curious Browser") to capture the following implicit indicators: mouse move-ment, mouse click, scrolling and the time spent on a particular page. The main goal of their study was to collect some implicit indicators that are promising. They found out that although time spent on a particular webpage is a good indicator to predict user interest, a combination of time and scrolling activity gave a better prediction. Joachims [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF] study focused on the use of click through as an implicit indicator for measuring relevance. They found out that click through closely follows relevant judgment and can use Ranked SVM algorithm to learn a ranking function. These studies [START_REF] Claypool | Implicit interest indicators[END_REF], [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF] argues that click through by itself is not a significant indicator to measure user interest.

Kim and Chan [START_REF] Kim | Implicit indicators for interesting Web pages[END_REF] used experimental measures to examine [START_REF] Nichols | Implicit Rating and Filtering[END_REF] list of promising indicators. Their focus was to know whether the time spent on a page signifies relevance. 11 students' behavioural characteristics were captured as they search the internet for 2 hours. Their findings suggest that the dwell time and distance of mouse movement are more reliable in predicting user interest than other indicators examined.

Buscher et al [START_REF] Buscher | Attentive Documents: Eye Tracking as Implicit Feedback for Information Retrieval and Beyond[END_REF] examined the correlation between user reading behaviour and user explicit judgment. In the experimentation, participants were given 16 documents to read and rank them in relation to a given task area. An eye tracker was used to measure users' gaze traces on each of the documents. They found out that readers are induced in some way to documents that are of topical relevance. This research is somewhat similar to that of [START_REF] Buscher | Attentive Documents: Eye Tracking as Implicit Feedback for Information Retrieval and Beyond[END_REF]. It however captures user's interest through mouse activity and dwell time.

Implicit feedback indicators

In this study, a number of implicit indicators were used to capture participant's interest on the given web documents. The implicit behaviour captured by the automated software includes:

 Active Time Spent on the Document (TS)

Since users can open multiple browsers and run several applications, it is imperative to note that the active time on a particular window is the period at which the window or web document is in focus. The Active Time Spent (TS) also called Dwell time is the accumulated time spent by a user on an active page during browsing. It starts counting immediately the page is open and stops when focus is moved away from the page or when the page is closed.

Hypothesis

The more the time the page is active, the more it is interesting, informative and of topical relevance [START_REF] Brusilovsky | Preface to special issue on user modeling for Web information retrieval[END_REF], [START_REF] Claypool | Implicit interest indicators[END_REF], [START_REF] Guo | Beyond dwell time: Estimating document relevance from cursor movements and other post-click searcher behavior[END_REF], [START_REF] Kellar | Effect of task on time spent reading as an implicit measure of interest[END_REF][START_REF] Kim | Implicit indicators for interesting Web pages[END_REF][START_REF] Lee | A time-based approach to effective recommender systems using implicit feedback[END_REF][START_REF] Morita | Information Filtering Based on User Behaviour Analysis and Best MatchText Retrieval[END_REF], [START_REF] Zhu | User interest modeling based on access behavior and its application in personalized information retrieval[END_REF]. Display time can be used as a substitute for eye tracker for a sophisticated feedback mechanism [START_REF] Buscher | Segment-level display time as implicit feedback: A comparison to eye tracking[END_REF].

Mouse Activities

Most people move the mouse when they read a web document. A user may move the mouse more frequently when viewing a document of interest. The mouse activities are captured only when the current document is in focus. When a user views another application or documents that are not related to the task, the mouse activities are not captured.

 Distance of Mouse Movement (DMM)

The distance of mouse movement is calculated by its x and y coordinates on the monitor. The formula is given as:

DMM = ∑ √ (1)
Where x and y are the mouse location along the x and y coordinates of the monitor screen.

Hypothesis

The more the distance the mouse move, the more interesting is the page to the user [START_REF] Claypool | Implicit interest indicators[END_REF], [START_REF] Jung | Modeling web user interest with implicit indicators[END_REF], [START_REF] Kim | Implicit indicators for interesting Web pages[END_REF], [START_REF] Zemirli | WebCap: Inferring the user's interests based on a real-time implicit feedback[END_REF].

 Total Mouse Movement (TMM)

This is the total mouse movement calculated by its x and y coordinates on the monitor. count increment as the mouse hovers on the document.

Hypothesis

The more the mouse hovers on a page, the more interesting the page. Cursor movement complements dwell time information [START_REF] Guo | Beyond dwell time: Estimating document relevance from cursor movements and other post-click searcher behavior[END_REF].

 Total Mouse Velocity (TMV)

This is the total speed covered by the mouse on the monitor. It is given as:

TMV = ∑ √ (2)
Where x and y are the mouse location along the x and y coordinates. And t is the time of the mouse distance in an interval of 100ms.

Hypothesis

When the mouse speed is low, it shows that the reader is actually reading the document and not skimming it. Therefore, the more the mouse speed the less the user's interest on the page. Cursor movement and cursor speed especially along the vertical axis of a Search Engine Result Page are good predictive indicators of document relevance [START_REF] Guo | Beyond dwell time: Estimating document relevance from cursor movements and other post-click searcher behavior[END_REF].

 Explicit Ratings (ER)

This is the actual user judgement of the visited documents. The buttons for explicit rating was attached on top of each document on a 0 to 5 rating scale. After reading a web document, the user rated the document according to his/her interest and topical relevance.

Study design

The main aim of the study was to capture participant's interest on web documents via some implicit indicators and to correlate the user's interest against their explicit ratings of the given documents. The participants were 4 PhD students, 1 Research assistant, 6 MSc students and 2 undergraduate students. Data for this research was collected by our own automated software developed with JavaScript. The software was injected in 15 web documents to record users' mouse activity, dwell time and explicit rating. Participants were given a task brief to read and a consent form to complete, after which they were allowed to perform the experiment at their convenient time.

They were to login into a website containing links to the 15 web documents and read the documents. The implicit data was captured unobtrusively as the participants read through the documents and then sent to MySQL database when they rated the document by clicking on any of the buttons on the rating scale as shown in fig 2 . The task ended after the participants read rated the 15 documents. Step to step schema of the task process

User task

The same task was given to all the participants. They were asked to prepare a presentation on the topic -Ethical issues in Big Data. We provided them with 15 documents of equal length containing 350 words with a font size of 20px and a font type of Arial, making the documents one screen view. The documents were created from web articles on ethical issues in Big Data. Two of the documents were however not related to the topic. The participants were asked to read each of the 15 documents and rate them according to how relevant the documents are to the task related topic. The rating was on a scale of 0 -5. Six buttons were attached on top of the documents and labelled 0 to 5 for explicit rating of the documents: The experiment was given a realistic feel by creating a second phase of the task which we called the presentation writing phase. The participants were told that documents will be presented to them according to how they rated them for later use in the presentation writing phase. To avoid Hawthorne effect (the alteration of behaviour by the subjects of a study due to their awareness of being observed), participants were told to do the experiment when and where they are most comfortable. The participants did not actually perform the second phase of the experiment (the presentation writing phase). Fig. 2 shows the user interface of the automated software.

Results

This section analyses the data collected from the participants. The analysis is as follows:

Implicit/Explicit Relationship

Each of the participant's data was analysed separately and as a group. Pearson Correlation Coefficient was used to correlate the parameters of active time, total mouse distance, average mouse velocity, total mouse movement along the x and y axis with user explicit rating. We obtain a correlation coefficient of 0.21 between the user rating and the dwell time. We then ranked the implicit indicators by their predictive strength, using stepwise linear regression to obtain the most promising predictive indicators. The indictors that showed much prominence in relation to the explicit ratings were the dwell time and mouse movement along the x-axis. The result from the experiment shows a positive correlation between the explicit rating and the dwell time. The dwell time also has a positive correlation with the mouse movement/mouse distance. Fig. 3 shows a Box plot of varying median of the user explicit rating and the dwell time of the participants, and it shows that the values of the ratings for 3 and 4 is the most consistent. The inconsistencies in the other values might be due to noise in the data. The Kruskal-Wallis test on the median for each of the explicit ratings rejected the null hypothesis, meaning that the median values are not the same. We also found out that although users vary in their reading behaviour, some of them have similar behavioural pattern. We analysed the first two participants' data separately to find out the extent of individual differences. We discovered that they have a relatively similar pattern in dwell time and mouse activity on the documents visited as shown in Fig. 4. In order to regroup the user ratings, the five levels of ratings were then reduced into two levels -Relevant and Non-relevant. The user ratings from 0 to 2 were merged together and represented as 0 (Non-relevant) while the ratings from 3 to 5 were represented as 1 (Relevant). A Multilayer Perceptron was used to conduct further analysis on the primary data set (mouse movement along the x and y axis, dwell time and mouse velocity time count) to predict relevant and non-relevant user rating. We obtained a 65% successful mapping with the user ratings after testing the trained data set. Table 1 shows the training and testing of the observed samples.

Discussion

The most promising indicator in the measure of perceived relevance is the active time.

Participants spent more time on documents perceived to be of topical relevance. We also found some individual behavioural differences among the participants while reading. The correlation of mouse activity with the explicit rating is relative low probably because of the length of the documents which were of 350 words and could be mostly viewed on screen at once. There is however evidence of a positive relationship between dwell time and explicit user rating. This conclusion is in line with previous research conducted in relation to implicit feedback [START_REF] Akuma | Investigating the Effect of Implicit Browsing Behaviour on Students' Performance in a Task Specific Context[END_REF], [START_REF] Kellar | Effect of task on time spent reading as an implicit measure of interest[END_REF][START_REF] Kim | Implicit indicators for interesting Web pages[END_REF][START_REF] Lee | A time-based approach to effective recommender systems using implicit feedback[END_REF][START_REF] Morita | Information Filtering Based on User Behaviour Analysis and Best MatchText Retrieval[END_REF], [START_REF] Núñez-Valdéz | Implicit feedback techniques on recommender systems applied to electronic books[END_REF], [START_REF] Zhu | User interest modeling based on access behavior and its application in personalized information retrieval[END_REF]. The mouse distance/ movement are closely related to the dwell time. We can substitute in some way the dwell time by mouse movement or mouse distance in an implicit system. We can also infer that learners dwell more on documents that are of topical importance and interest to their current activity. The effect of the concept of prior knowledge and cognition on the reader's behaviour was not examined. We assumed that the selected participants barely had knowledge of the task domain. We also observed some individual behavioural differences among the participants. To examine the variety in reading behaviour, we took a closer look at the data for two of the participants (Participants 1&2) and we discovered some level of similarity in their behaviour in terms of dwell time and mouse activity.

Multilayer Perceptron was used to further analyse the primary data set, with user rating as the dependent variable. We obtained a fair result of 65% mapping after training the data set. This suggests a relationship between the user behaviour and their explicit ratings.

Since the experiment was not closely monitored in a controlled environment, we did not get a significant correlation between the user ratings and the mouse activities as hypothesized; we suspect that some of the participants did not follow the instructions carefully as stipulated for the task. This probably added some noise to the data collected.

Conclusion and future work

Implicit data can be used to predict user's interest on a web documents. When users give explicit feedback, it affects their normal reading or browsing pattern [START_REF] Claypool | Implicit interest indicators[END_REF]. Implicit methods are a cost effective and objective approach of rating user's interest. This study shows that dwell time on a document is influenced by user perceived relevance and topicality. We also found a relationship between homogenous clusters of user reading behaviour and their explicit ratings.

The next phase of this research is to develop an add-on that will implicitly capture user data on the web as they browse. Additional implicit indicators like copy and paste [START_REF] Grzywaczewski | Task-Specific Information Retrieval Systems for Software Engineers[END_REF], amount of scroll and keystroke will be examined. The data analysis will be centred on aggregating the most promising indicators and developing a model for effective personalization of relevant documents to learners based on their interest. The effect of document familiarity will also be examined.

  Fig 1 shows a step to step schema of the task process.

Fig. 1 .

 1 Fig. 1. Step to step schema of the task process

Fig. 2 .

 2 Fig. 2. Login page, Index page with links to the 15 documents and document page with explicit rating buttons

Fig. 3 .

 3 Fig. 3. Graph showing the Boxplot for the combination all the participant's time/explicit rating relationship

Fig. 4 .

 4 Fig. 4. Graph showing participant 1 and 2 dwell time, mouse distance and average speed on the documents.

Table 1 .

 1 Multilayer Perceptron cluster analysis


Georgios Papadimitriou
email: gpapadimitriou@isc.tuc.gr

Nikolaos I Spanoudakis
email: nispanoudakis@isc.tuc.gr

Michail G Lagoudakis
email: lagoudakis@isc.tuc.gr

Extending the Kouretes Statechart Editor for Generic Agent Behavior Development

Keywords: agents, robotics, model-based development, CASE

The development of high-level behavior for autonomous robots is a time-consuming task even for experts. The Kouretes Statechart Editor (KSE) is a Computer-Aided Software Engineering (CASE) tool, which allows to easily specify a desired robot behavior as a statechart model utilizing a variety of base robot functionalities (vision, localization, locomotion, motion skills, communication) for the Monas robotic software architecture framework. This paper presents an extension to KSE, which allows defining generic agent behaviors using automatic framework-independent code generation, as long as the underlying framework is written in C++. This way a user can program physical (robots) or software agents that can be executed on any platform using any compatible software framework. This paper demonstrates the transparent use of the extended KSE in the SimSpark 3D soccer simulation and the Wumpus world.

Introduction

The Kouretes Statechart Editor (KSE) [START_REF] Paraschos | Model-driven behavior specification for robotic teams[END_REF][START_REF] Topalidou-Kyniazopoulou | A CASE tool for robot behavior development[END_REF] is a graphical Computer-Aided Software Engineering (CASE) tool, which allows a software developer to define the behavior of an agent (software or physical) using a graphical model and automatic code generation. The graphical model is a statechart, a platformindependent model, modeling the control of the different agent capabilities. A complete statechart is automatically converted by KSE to source code, which can be compiled, linked with the base capabilities, and executed on the target platform. KSE follows ASEME, a model-driven software engineering methodology from the Agent-Oriented Software Engineering (AOSE) domain [START_REF] Spanoudakis | Using ASEME methodology for model-driven agent systems development[END_REF]. An advantage of KSE is the analysis tool, which enables the user to abstractly and compactly define the desired behavior using liveness formulas. A small set of liveness formulas can lead to a large statechart model (design phase), therefore the user can save a lot of time by seeding the design through the analysis tool.

In our recent work, we used KSE extensively for developing the behavior of the Aldebaran Nao humanoid robots of our team Kouretes [www.kouretes.gr] competing in the RoboCup Standard Platform League (SPL). Besides robotic behavior development, KSE has also been used for developing the behavior of software agents for the popular Java-based JADE framework [jade.tilab.com].

The motivation behind the work presented in this paper is the need for using a simulator, when modeling a robotic team behavior. Regularly testing new features on the real robots has several shortcomings, i.e. the robots need maintenance after some hours, a number of people are needed in order to set up an experiment with the robotic team in the lab, and the experiments themselves tend to take quite long to setup and demonstrate. Thus, we decided that we needed to use a simulator for modeling and testing team behavior and, when the simulation proved successful, then move to field tests with the real robots. The SimSpark simulation environment, which is also used for the RoboCup 3D soccer simulation league, was the ideal candidate for our goals. However, the SimSpark platform was not compatible with our Monas robotic software architecture framework [START_REF] Paraschos | Monas: A Flexible Software Architecture for Robotic Agents[END_REF], which we use for deploying behaviors on the Nao robots. Thus, we decided to develop a platform-independent code generation component for the KSE tool. To this end, we added a few platform-specific parameterization features within code generation. By adopting this parametric approach and providing the correct parameters for the underlying platform, we can now use the KSE tool for deploying platform-independent agents on any platform by exporting the generated code directly in the C++ programming language using the specification provided by the parameters.

This paper focuses on describing the extensions of KSE and demonstrates its practicality on two diverse domains: the SimSpark1 simulation platform for 3D robot soccer and the Wumpus World2 simulator, a classical testbed for prototyping Artificial Intelligence programs. In the rest of the paper, after examining the background technologies in Section 2, we present the main features of KSE, focusing on new additions and extensions, in Section 3. Subsequently, we present the results of our application and evaluation on the two aforementioned domains in Section 4. Finally, we outline our findings and future work in Section 5.

Background

ASEME [START_REF] Spanoudakis | Using ASEME methodology for model-driven agent systems development[END_REF] is an Agent-Oriented Software Engineering Methodology that supports a modular agent design approach and introduces the concepts of intraand inter-agent control. The former defines the agents behavior by coordinating the different modules that implement its own capabilities, while the latter defines the protocols that govern the coordination of the society of the agents. ASEME follows the Model-Driven Engineering (MDE) paradigm, where software development is driven by instantiating the appropriate models at each phase.

The transition from one development phase to another is assisted by automatic model transformation leading from requirements to computer programs. The ASEME platform-independent model, which is the output of the design phase, is a statechart [START_REF] Harel | The Statemate semantics of statecharts[END_REF], and is referred to as the Intra-Agent Control (IAC) model. KSE adopts the ASEME methodology and assists the developer from the analysis phase to the design and code generation phases. More specifically, KSE supports (a) the automatic generation of the initial abstract statechart model using compact liveness formulas, (b) the graphical editing of the statechart model and the addition of the required transition expressions, and (c) the automatic source code generation for compilation and execution on the robot. KSE has been developed using the Eclipse Modeling Project [www.eclipse.org/modeling] technologies and has been integrated with the Monas software architecture [START_REF] Paraschos | Monas: A Flexible Software Architecture for Robotic Agents[END_REF], which provides the base functionalities.

Monas modules focus on specific functionalities (vision, motion, etc.) and each one of them is executed independently at any desired frequency completing a series of activities at each execution. Statechart modules are executed using a generic multi-threaded statechart engine, which was built on top of existing open-source projects, provided the required concurrency, and met the real-time requirements of the activities on robots. Code generation in KSE initially targeted specifically the Monas framework.

The KSE Generic C++ Generator

The KSE Generic C++ Generator (referred to as GGenerator in the rest of the paper) is a tool that extends KSE in order to give the developer the ability to create behaviors for agents, which are automatically transformed to generated C++ code ready to be compiled with the underlying software architecture (assumed to be also in C++) without any additional dependencies. Thus, GGenerator enables the user to create agent behaviors for different platforms and different environments, with the only prerequisite that the underlying software framework accepts C++ code.

We achieve this (a) by enhancing the statechart engine used in KSE with a generic blackboard [START_REF] Hayes-Roth | A blackboard architecture for control[END_REF] interface, (b) with a new generic grammar for specifying transition expressions, and, (c) by creating a new source code generator for the extended tool.

The blackboard interface is generated automatically by GGenerator during the source code generation phase and can target any C++ framework, according to its initialization and the parameters given. This interface is used to bind our statechart model with any user-specified framework. This way the user is not concerned with model-framework compatibility issues, because the created blackboard interface serves as a middleware between the statechart model and the target environment and handles their communication. This interface, along with our generator, is integrated in KSE.

The initialization of the blackboard interface depends on the properties files, which are defined by the user only once during the early stages of the be-havior development process. These files are named include classes.txt and instances.txt. Both files are given in plain text format, they are parsed by the KSE GGenerator tool, and provide the required information for generating and setting up correctly a blackboard interface that targets a specific framework. In these files we add functions, variables, and header files needed for the communication between our statechart model and the target environment. The former file lists the C++ header files we need to include, while the latter lists the functions and the variable instances we need to access.

The creation of the properties files requires some knowledge about the framework we target. Prior to generating our blackboard interface, we have to point out the framework's modules and structures that supply the information needed for correct communication between our statechart model and the environment. In most cases, the information needed for creating an agent behavior includes the updated state of the target environment or an updated set of readings from the agent's sensors, without being limited to these examples, since we can always accept any kind of information the framework provides. The properties files are easily created, once the required information has been identified and located in the target framework. In the next section we give two examples of how to create the properties files for two different platforms.

We also allow the user to register user-defined variables in the same blackboard interface using the graphical editing interface of KSE. These variables can be of any type, can be updated in any node of the statechart, and can be used in transition expressions anywhere in the statechart, along with any frameworkprovided variables. This ability allows the behavior module itself to maintain its own internal memory.

Finally, to execute the generated behavior on the target framework, we need to register our generic blackboard interface along with our statechart model for execution on the target framework. This is the last stage of our behavior development process and needs to be done only once for a target framework; any number of generated behaviors can be tested afterwards on that framework.

As already mentioned, within the KSE tool, the definition of a statechart can be assisted by the use of liveness formulas as a seed. The liveness formula [START_REF] Wooldridge | The Gaia methodology for agentoriented analysis and design[END_REF] is a process model that connects activities using the Gaia operators. Briefly, A.B means that activity B is executed after activity A, A* means that A is executed zero or more times, A+ means that A is executed one or more times, A∼ means that A is executed indefinitely (it resumes as soon as it finishes), A|B means that either A or B is executed exclusively, A||B means that A and B are executed concurrently, and [A] means that A is optional. Liveness formulas are automatically converted to a base graphical statechart model.

Every statechart model we create to describe an agent behavior must contain transition expressions, which are responsible for the correct execution of the statechart. These expressions are inserted manually by the user during behavior specification for controlling the statecharts execution. In transition expressions, the user can optionally define events and conditions, as well as multiple actions, if desired, using any framework-specific or user-defined variables. In any case, these variables must be registered in the blackboard's interface for transition expressions to work properly. Note that the user is provided with the ability to create any kind of variables he/she finds necessary for the transition expressions during the graphical editing of the statechart model. Since we modified the statechart engine used to execute KSE-created statecharts by adding a generic blackboard interface, we also needed a new C++ code generator different from the existing one, which was customized for the Monas framework. At this point, we also changed the transition expressions grammar to be equally generic. The new statechart engine supports a more abstract transition expression grammar compared to the one used for the Monas architecture [START_REF] Paraschos | Model-driven behavior specification for robotic teams[END_REF]. This means that it should be relatively easy for a user to edit them, even without having complete knowledge of the underlying framework he/she works with. The new grammar is independent of the underlying platform, and uses common syntactic rules for expressions. It is shown in EBNF format in Figure 1. We created the new C++ generator for our extended statechart engine using the Eclipse Modeling Framework (EMF3 ) along with Xpand4 . We fully integrated our GGenerator extension in KSE, so that the generated behavior can be easily tested on the user-specified framework.

Applications

We use GGenerator to create behaviors for agents in two target different frameworks, mainly to demonstrate the platform-independence property. The two C++-based frameworks we use for our examples are: (a) Simple Soccer Agent The two simulation environments have many differences, shown in Table 1.

Creating a Behavior for the SimSpark 3D Soccer Simulator

In this example, we use GGenerator to create a behavior for an agent that plays soccer. Our simple behavior can be described as follows: The agent searches for the ball in the soccer field and, if the ball is found, the robot walks towards the ball and takes it in possession. If the game is over, the robot pauses. Our purpose is to work only at the high level of agent programming (game strategy) and not at the low level (Walk, Kick, and other actions) or with agent-simulator technical aspects (e.g. communication with the simulator). The underlying framework we chose is based on the software release of the RoboCup team Berlin United -Nao Team Humboldt [START_REF] Hafner | Berlin United -Nao Team Humboldt[END_REF]; it is written in C++ and provides basic activities, such as Walk, Turn Left, Scan For Ball or Stand Up. The first step is to create the properties files; these files are shown below. In fact, we just need to include the appropriate header files to gain access to those framework-provided variables that allow the user (and the statechart) to gain information about the game and the perception of the ball, but also request the execution of a motion. The next step is to use the KSE graphical interface to create our behavior. We start by providing the liveness formulas that describe our agent behavior abstractly:

LogicalAgent = Init . ( Play | NoPlay )+ Play = [ StandUp ] . ( PlayBall | ScanBall ) PlayBall = Turn | Walk
The first formula indicates that our behavior (LogicalAgent) will execute Init (for initialization of the player) and then will choose one or more times between Play or NoPlay exclusively (depending on the current game state). The second formula suggests that our behavior may execute StandUp (if needed) and then will choose between PlayBall or ScanBall exclusively (depending on whether the ball is visible or not). Finally, the third formula indicates that our agent will choose between Turn or Walk exclusively (depending on where the ball is seen). As soon as we provide the KSE GGenerator with the liveness formulas, the initial statechart model is generated and the user has to associate it to a source code repository that provides the code for the basic agent activities (Walk, Scan, etc.). If the framework does not provide some activity, our tool generates the corresponding skeleton code and the user is asked to provide the corresponding C++ code using the built-in editor in KSE. Note that the abstract behavior specification of the liveness formula specifies what activities are included in the desired behavior, but gives no information on when execution switches from one activity to another. It is the execution of transition expressions that makes this switching between activities possible. After the statechart is created, we use the KSE tool to add the necessary variables we are about to use in the transition expressions. In our case these are: myInertialSens, ballFound, and horizontalAngle. The first variable is of type class and holds information about the posture of the robot. The second one is of type bool and is true, if the ball is seen by the robot and false otherwise. The last one is of type double and holds information about the horizontal angle between the robot and the ball. These are user-defined variables, which are updated from the framework-provided variables inside the statechart, and are used in our transition expressions for controlling the statechart execution. They are added in the blackboard interface using the editing tool provided by KSE.

The next step is to fill in the transition expressions, according to the grammar in Figure 1, using the KSE editor. For example, the transition expression:

[ (ballfound == true) && (horizontalAngle < 0.1) ] states the conditions (ball is visible straight-ahead) under which the robot will execute the Walk activity within the PlayBall state. The final statechart model with all the transition expressions is shown in Figure 2.

The last step of our procedure is to use GGenerator to produce the C++ code for this statechart model and transfer the generated files to the source folder of the framework, so that it is compiled and used in the target framework.

To execute the generated agent behavior we have to instantiate it within the target framework. This is a framework-specific step and depends on the requirements set by the framework itself. In the present example, it amounts to simply adding a couple of C++ lines in the configuration files of the framework to register the generated behavior as a new module within the framework. This is the only handwritten C++ code during our behavior generation procedure and is done only once, since any updates to the statechart simply modify the behavior, which remains registered in the framework. In Figure 3 we show three screenshots from the execution of the LogicalAgent behavior. Initially, the agent searches for the ball (left), when it finds the ball it walks towards it (middle), and, finally it takes possession of the ball (right).

Creating a behavior for the Wumpus World Simulator

In this example, we create a behavior for the Wumpus world: the agent tries to find the gold in the maze and escape alive. Our goal is not to solve the maze, but to simply demonstrate how easy it is to create a behavior for this environment using GGenerator. To connect our statechart to the Wumpus World platform we first define the properties files, as shown below. The first formula indicates that our behavior (Wumpie) will execute Init and then will sense the world and act one or more times (Sense capability). The second formula suggests that our behavior will execute percept and then choose between Play or NoPlay exclusively. Finally, the third formula extends the Play capability and indicates that our agent will choose one of the moves forward, turnLeft, turnRight, grab, shoot, climb (depending on the information gathered so far). From these liveness formulas, the initial statechart model is generated and the user has to associate it to a source code repository that provides the code for basic agent activities (forward, percept, init, etc.).

In the next step, we use the KSE tool to add the necessary variables we are about to use in the transition expressions of the statechart. In this case these are: glitter, stench, breeze, turnedRight, turnedLeft, scream, gold, arrow, posX, posY. These are user-defined variables that are registered in the blackboard during the code generation. Once we add the transition expressions according to the grammar rules, we are ready to generate code for our behavior. Once we register the statechart in the Wumpus framework again by adding a couple of C++ lines in the Wumpsim class, we can execute and test our behavior. Figure 4 shows the final statechart for Wumpie.

Discussion and Conclusion

In this paper, we presented an extension to KSE that allows to specify statechartbased agent behaviors independently of the underlying software framework, relying on the C++ programming language, as the common code base. The extended KSE tool still supports the C++-based Monas framework for which it was originally customized, but now is open to any other C++-based framework, such as the popular ROS [www.ros.org] framework. Thus, GGenerator increases the added value of the KSE CASE tool. Its main advantages compared to other similar products, noted also in the past [START_REF] Topalidou-Kyniazopoulou | A CASE tool for robot behavior development[END_REF], include (a) the use of liveness formulas that aid and accelerate the initial statechart generation, and, (b) the option to define the code generation component as an add-on, aiming any target language.

Our future plan, which also motivated this work, is to automatically and massively generate team behaviors for RoboCup using our statechart tools and test them in simulation within an evolutionary framework for discovering suitable

  transExpression = [ event ] [ "[" condition "]" ] [ "/" actions ] event = string condition = "(" condition ")" | condition operator condition | operand operator condition | operand operator operand operator = ">" | "<" | ">=" | "<=" | "==" | "!=" | "&&" | "||" operand = constant | variable variable = letter string | letter string "." variable actions = timeoutAction | action timeoutAction = TimeoutAction "." letter+ "." number action = variable actionOp variable | action ";" action actionOp = "=" constant = number | string number = digit | digit number string = character | character string character = letter | digit letter = "a" | "A" | "b" | "B" | "c" | "C" | ... digit = "0" | "1" | "2" | "3" | ...

Fig. 1 .

 1 Fig. 1. Transition expression grammar in EBNF format.

Fig. 2 .

 2 Fig. 2. The complete LogicalAgent statechart within the KSE graphical environment.

Fig. 3 .

 3 Fig. 3. Three successive screenshots from the execution of the LogicalAgent.

  Then, we create the liveness formulas that describe the behavior abstractly: Wumpie = init . Sense+ Sense = percept . ( Play | NoPlay ) Play = forward | turnLeft | turnRight | grab | shoot | climb

Fig. 4 .

 4 Fig. 4. The complete Wumpie statechart for the Wumpus World.

  soccer team behaviors. We also plan to develop additional code generators to support other programming languages, thus expand the range of frameworks compatible with KSE, such as the Python-based Pyro [pyrorobotics.com].

Table 1 .

 1 Comparison of the two different target platforms.

	SimSpark 3D Soccer Simulator	Wumpus World Simulator
	Partially Observable	Fully Observable
	Stochastic	Deterministic
	Dynamic	Static
	Physical representation of the agent	No physical representation of the agent
	Uncertainty	No uncertainty
	Sequential	Episodic
	Continuous	Discrete
	Multi-agent	Single-agent
	Competitive, Cooperative	non-Competitive, non-Cooperative
	framework, which interacts with the Simspark 3D Robot Soccer Simulator, and
	(b) WumpSim framework, which interacts with the Wumpus World Simulator.

SimSpark is a generic simulator for various multi-agent environments. It supports developing physical simulations for AI and robotics research with an open-source application framework. [simspark.sourceforge.net]

The Wumpus World simulator is a simple C++ framework for simulating the Wumpus World described in Russell and Norvig's classic text book "Artificial Intelligence: A Modern Approach". [www.eecs.wsu.edu/ ~holder/courses/AI/wumpus]

The EMF project is a modeling framework and code generation facility for building tools and other applications based on a structured data model.

Xpand is a language specialized on code generation based on EMF models.


Keywords: Autonomous agent, Fuzzy logic, Virtual kinematic model, Intelligent Systems, Hierarchic Fuzzy

The development of a controller architecture based on hierarchic fuzzy logic to create the trajectory of a mobile agent in a virtual environment is initially used. The objective of the low cost controller is to regulate an opensource autonomous explorer robot, which moves between two pre-established points. The system establishes a viable route in a scenario with obstacles. Simulations in virtual environment are used to ensure the autonomy of the developed controller. Initial results demonstrate the success of this proposal.

Hierarchic Fuzzy Approach Applied in the Development of an Autonomous Architecture for Mobile Agents

Márcio Mendonça 1 , Esdras Salgado da Silva 1 , Karina Assolari Takano 1 , Mauricio Iwama Takano 1 , Lúcia Valéria Ramos de Arruda 2

Introduction

Researches about mobile autonomous robots are becoming more important due to technological evolution and high processing computers. Some technological evolutions that can bear witness to are the development of intelligent computational techniques, such as fuzzy logic, artificial neural network, intelligent agents, and others.

A number of challenging problems must be solved for mobile autonomous navigation. The problems can depend on different domains like perception, localization, environment modeling, and decision making, control etc. [START_REF] Shaikh | The state-of-the-art intelligent navigational system for monitoring in mobile autonomous robot[END_REF].

Autonomous robots can be used in different fields for instance in high risk areas (to avoid risky situations for humans), in exploration of unattainable places of difficult access or hazardous environment, and in service robots which makes this an emergent field of research and application, as presented by [2, 3, and 4].

Explorer robots or agents can be virtually controlled by humans; this however demands communication systems, cameras and operators. A solution for this is the use of intelligent computational systems which can be applied in the development of robots with the ability of adaptation in different environments by reading signals from low level sensors such as ultrasound sensors [START_REF] Mendonça | Autonomous navigation system using Event Driven-Fuzzy Cognitive Maps[END_REF]. This can be helpful in cases such as the exploration of natural environment (inhospitable) when autonomous decisions are required [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF][START_REF] Calvo | A Hierarchical self-organizing controller for navigation of mobile robots[END_REF][START_REF] Broggi | Intelligent vehicles[END_REF].

The environment exploration has some difficulties to be solved for example uncertainties, inaccuracies and sequential errors. The complexity involved in creating an efficient path is known to be high due to sequential dynamic decisions that have to be made (a wrong decision can compromise the next steps). The navigation tasks are initiated by informing an objective. During the exploration the agent needs to have the ability to deal with unpredictable events like mobile and/or unexpected obstacles [START_REF] Bakambu | Integrated autonomous system for exploration and navigation in underground mines[END_REF].

According to Khodayari [START_REF] Khodayari | A historical review on lateral and longitudinal control of autonomous vehicle motions[END_REF] there are two main strategies to develop autonomous agents. The first one is related to heuristic knowledge and is represented in this paper by fuzzy logic as presented in [START_REF] Chiang | Longitudinal and lateral fuzzy control systems design for intelligent vehicles[END_REF][START_REF] Yang | An expert fuzzy controller for vehicle lateral control[END_REF][START_REF] Cai | An intelligent longitudinal controller for application semiautonomous vehicles[END_REF], and adapted to the model used. The second one is based in the control theory, subdivided in linear control theory and nonlinear control theory.

In past decades, researches have developed many obstacle avoidance navigation algorithms. These methods can be divided into the following categories: model-based method [START_REF] Lim | Sonar based systematic exploration method for an autonomous mobile robot operating in an unknown environment[END_REF][START_REF] Krishna | Perception and remembrance of the environment during realtime navigation of a mobile robot[END_REF][START_REF] Maaref | Sensor-based navigation of a mobile robot in an indoor environment[END_REF][START_REF] Chatterjee | Use of single side reex for autonomous navigation of mobile robots in unknown environments[END_REF][START_REF] Ge | Boundary following and globally convergent path planning using instant goals[END_REF][START_REF] Toibero | Switching Control of Mobile Robots for Autonomous Navigation in Unknown Environments[END_REF], fuzzy logic method [START_REF] Xu | Sensor-based fuzzy reactive navigation of a mobile robot through local target switching[END_REF][START_REF] John | Evolution of a Negative-Rule Fuzzy Obstacle Avoidance Controller for an Autonomous Vehicle[END_REF][START_REF] Chao | Fuzzy Target Tracking and Obstacle Avoidance of Mobile Robots with a Stereo Vision System[END_REF][START_REF] Abiyev | Navigation of mobile robots in the presence of obstacles[END_REF] and reactive method based on neural network [START_REF] Phinni | Obstacle Avoidance of a wheeled mobile robot: A Genetic-neuro-fuzzy approach[END_REF][START_REF] Zhu | Neurofuzzy-Based Approach to Mobile Robot Navigation in Unknown Environments[END_REF]. Of all the methods, the obstacle avoidance method based on fuzzy logic reacts quicker and is less susceptible to sensor measuring errors for the robot's reaction has come from qualitative reasoning of different categories in the fuzzy logic method, so the algorithm proposed in this paper is based on fuzzy logic principles. The difference is the fact that the hierarchical fuzzy quantitatively simplify solving the problem by organizing rules with one fuzzy used for each objective.

The objective of this paper is to develop an autonomous explorer agent (robot) based in a low cost and open source platform with the ability to learn navigation strategies by environment interaction. The development proposal adopted is inspired by Braitenberg [START_REF] Braitenberg | Vehicles: Experiments in Synthetic Psychology[END_REF], who suggests the application of intelligent computational techniques starting up with a simple model with one or only a few functionalities, and gradually adding new objectives to improve the exploration capability of the agent, such as manage the battery charge and navigate back to the recharging spot. In this paper, the agent will have initially the ability to navigate through two pre-established points in a surface. The second objective is to add the ability to deviate from any obstacles that are found in the proposed initial path.

This paper is organized as follows: section 2 briefly describes the fuzzy logic concept; section 3 presents the development of this work (kinematic model for the robot position and controller); sections 4 and 5 show the results and conclusions.

Fuzzy Logic Fundamentals

Fuzzy systems according to Zadeh [START_REF] Zadeh | Fuzzy algorithms[END_REF] is a set of methods based in the linguistic terms, multivalued logic, systems based in rules that aim to work with failure tolerance, inaccuracy and uncertainty in real systems. These methods and linguist terms proposes the concept of the fuzzy logic which consists of the combination of these theories, allowing the modeling of complex processes (based on inaccurate or approximate information) expressing control rules in linguistic terms. Different areas of knowledge use this technique as a solution for control applications, pattern recognition and function approximation, especially when there is little or no knowledge of the mathematical models.

A fuzzy system consists of three main components: input and output, set of rules and inference mechanisms [START_REF] Passino | Fuzzy control[END_REF][START_REF] Kasabov | Foundations of Neural Networks, Fuzzy Systems, and Knowledge Engineering[END_REF]. A difficulty to implement simple Fuzzy logic is that as you increase the number of variables involved, the number of rules grow exponentially. One possible solution is the development of a fuzzy hierarchical structure in which different rule bases are used to address each goal [START_REF] Wang | Analysis and design of hierarchical fuzzy systems[END_REF].

Development

Kinematic model for the robot position

There are two ways of representing the robots: kinematic or dynamic. The kinematic models are used to represent the robots according to the velocity and orientation of the wheels, and the dynamic models according to the generalized forces applied by the actuators. There are two kinematic models used to represent the agents: position model and configuration model. The first of them considers only the position and the orientation of the robot, while the second one also considers other internal variables (for example angular movement of the wheels). The position model fulfills the needs of the position control and spatial orientation of the robot. Most of the researches reported in the literature describe the robot according to Cartesian coordinates using just a position kinematic model [31, 32, and 33].

The robot used as a model in this paper consists of three wheels, one of which is mobile (in the front part of the robot) and the other two stationary on the sides (each of them connected to a motor); three ultrasonic sensors placed to collect signals that identify possible obstacles in the path. The physical model of this agent is shown in Fig. 1 (a), and the schematic model in Fig. 1 (b).

Hierarchical Fuzzy Approach

In some situations fuzzy logic using just a set of rules can control processes in different situations, during start up and course of operations with the proper activation of the rules. However when there are different objectives in the same controller, it is necessary to apply a set of rules for each objective. Summarized when the fuzzy controller requires more complexity to achieve the desired goal, a common strategy is to decompose the controller problem hierarchically, using low-dimensional fuzzy systems. A priority is defined between the fuzzy systems adopted [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF]. It is called Fuzzy hierarchical system using more than one fuzzy and establishes a hierarchy between them.

A hierarchical fuzzy architecture based in cognitive architecture [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF] especially the subsumption [START_REF] Coppin | Artificial Intelligence Illuminated[END_REF], was developed to work with hierarchical decision making and this is due to the need of two opposite main targets for example reach a target and deviate from obstacles in the trajectory.

The subsumption fuzzy architecture proposed has two sets of rules which work independently and with different and hierarchical competence levels. When certain competence level is enabled all other levels are disabled. Thereby the fuzzy controller coordinates the competence levels prioritizing the higher levels (deviate from obstacles is a higher level than reaching the target) [START_REF] Goerick | Towards an understanding of hierarchical architectures[END_REF]. In other words, when the autonomous agent is deviating from an obstacle it stops going after the target, this demands an implemented switching mechanism. In Fig. 2 it is shown the hierarchical fuzzy architecture developed. Fuzzy I, the initial objective of this paper, uses a decision-making system based in heuristic methods. This step has the objective of determining the shortest route between the initial point and the target. This set of rules was implemented from observations of the dynamic behavior of the agent in virtual scenarios.

1. If (LatDist is farLeft) and (FrontDist is farF) then (LeftPulse is medium)(RightPulse is high)

2. If (LatDist is farLeft) and (FrontDist is mediumF) then (LeftPulse is slow)( RightPulse is high)

3. If (LatDist is farLeft) and (FrontDist is closeF) then (LeftPulse is high)

Table 1. Example of fuzzy rules I

This strategy consists in abstracting the input data (of mathematical simulations of the lateral and frontal distances) and converting them in linguistic variables (sets of rules) and then generating a response (pulses to the motors linked to the left and right wheels).

In Fig. 3 are presented the control surfaces of the fuzzy I corresponding to the left (Fig. 3a) and right (Fig. 3b) wheels. The x-axis represents the lateral distance between the robot and the target (DSx), the y-axis, the front distance (DSy) and the z-axis, the pulses wheels: right to left in Fig. 3a and Fig. 3b.Whenever the sensors detect an obstacle, the hierarchical fuzzy controller prioritizes the deviation of the obstacles using the fuzzy II set of rules. When no obstacle is detected, the agent will keep going after the target using the fuzzy I set of rules. Some of the rules used in fuzzy II are shown in table 2: 1. If (sensor_L is far) and (sensor_F is far) then (LeftPulse is medium) 2. If (sensor_L is far) and (sensor_F is medium) then (LeftPulse is high) 3. If (sensor_L is far) and (sensor_F is close) then (LeftPulse is high)

Table 2. Example of fuzzy rules II

The control surfaces related to the second fuzzy are presented in Fig. 4. Fig. 4a refers to the influence of both left and frontal sensors on the left wheel. Fig. 4b refers to the influence of both right and frontal sensors on the left wheel. In Fig. 4b, "we" represents the pulses on the left wheel with range [0.14 0.19] because when we have obstacles on the right hand front of the robot, it has to turn to left. Therefore there is a low pulse in left wheel. The rules are symmetric, which means the results are the same for the right wheel. A two dimensional simulator was implemented in Matlab to study the dynamic behavior of the mobile agent. The scale used for both the prototype and the scenario is 1:100.

Russel and Norvig [06] suggest that in order to consider an autonomous agent, it is necessary to succeed in at least three different simulations. Therefore the arrangement of the obstacles, the initial position of the mobile agent and the target are adjustable in the Matlab program, allowing the construction of different scenarios.

In the simulator developed, the sensors were calibrated to send the signals at a maximum distance of 15 cm.

Results

For each scenario simulated, three situations where considered (except 4): scenario with obstacles; rearrangement of these obstacles; and scenario with noise of five percent on the sensors signals. The noise added in the sensors signals represents the uncertainty of the data acquisition, characteristic of real scenarios due to different behavior of the sound wave reflection in different materials.

In the following subsections are presented the simulated scenarios. In the following images, items (a) and (b) indicate tests in obstacles arranged in two different ways, and item (c) indicates the response to noises.

Scenario 01

In this scenario (Fig. 5) the initial position for the prototype is (0,0), at an angle of zero degrees with the X-axis, and the target is located in position (50,70).

Scenario 02

In this scenario (Fig. 6) the initial position for the prototype is [START_REF] Wang | Analysis and design of hierarchical fuzzy systems[END_REF][START_REF] Zhu | Neurofuzzy-Based Approach to Mobile Robot Navigation in Unknown Environments[END_REF], at an angle of 45 degrees with the X-axis, and the target is located in position (-50, 80).

Scenario 03

In this scenario (Fig. 7) the initial position for the prototype is (-80,75), at an angle of zero degrees with the X-axis, and the target is located in position [START_REF] Coppin | Artificial Intelligence Illuminated[END_REF]75).

Scenario 04

In this scenario (Fig. 8) the initial position for the prototype is (-50,-90), at an angle of zero degrees with the X axis, and the target is located in position (0,0). In this simulation was considered the complexity of a spiral scenario. In this scenario situation (b) was not considered.

Conclusion

The initial results obtained from the simulations were convincing, because the mobile agent accomplished the goal of reaching the target with a maximum error of one centimeter deviating from obstacles.

It is possible to reduce the error. However, it would make the robot moves more than necessary if an obstacle is located at about ten centimeters of the target. This happens because of the sensors that identify the obstacle and do not allow the agent to reach the target, as the hierarchy prioritizes the deviation of the obstacles.

Seven different scenarios were successfully simulated. This implies the autonomy of the proposed fuzzy control. The simulations with uncertainties also imply a robust system, because they approach simulations to real environment where data input from the sensors may have noise and errors. Future works are presented:

 Improve the minimum error by changing the hierarchical process;  Compare the proposed controller with other intelligent techniques like Artificial Neural Network and Fuzzy Cognitive Maps;  Genetic algorithm can also be used to tune the fuzzy logic controller;  Improve the complexity of the scenarios using for example, walls;  Add new functions in the controller: battery management (locate charging points) and reverse gear for extreme situations;  Apply the system in a real robot using an open source development platform, such as a low cost microcontroller (example, Arduino).

Fig. 1 .

 1 Fig. 1.Physical (a) and schematic (b) models of the robot.

Fig. 2 .

 2 Fig. 2. Hierarchical model of the fuzzy system.

Fig. 3 .

 3 Fig. 3.Fuzzy I control surfaces for left (a) and right (b) wheels.

Fig. 4 .

 4 Fig. 4.Fuzzy II control surfaces for left wheel.

Fig. 5 .

 5 Fig. 5. Scenario 01.

Fig. 6 .

 6 Fig. 6. Scenario 02.

Fig. 7 .

 7 Fig. 7. Scenario 03.

Fig. 8 .

 8 Fig. 8. Scenario 04.

Acknowledgment

The authors would like to thank CNPq and Araucaria Foundation of the State of Paraná, Brazil, for financial support.


Arbab Masood Ahmad
email: arbabmasood@nwfpuet.edu.pk

Gul Muhammad Khan

Sahibzada Ali Mahmud
email: sahibzada.mahmud@nwfpuet.edu.pk

Classification of Mammograms using Cartesian Genetic Programming evolved Artificial Neural Networks

Keywords: Mammogram, Image classification, GLCM, CGPANN, Haralick's parameters

We developed a system that classifies masses or microcalcifications observed in a mammogram as either benign or malignant. The system assumes prior manual segmentation of the image. The image segment is then processed for its statistical parameters and applied to a computational intelligence system for classification. We used Cartesian Genetic Programming Evolved Artificial Neural Network (CGPANN) for classification. To train and test our system we selected 2000 mammogram images with equal number of benign and malignant cases from the wellknown Digital Database for Screening Mammography (DDSM). To find the input parameters for our network we exploited the overlay files associated with the mammograms. These files mark the boundaries of masses or microcalcifications. A Gray Level Co-occurrence matrix (GLCM) was developed for a rectangular region enclosing each boundary and its statistical parameters computed. Five experiments were conducted in each fold of a 10-fold cross validation strategy. Testing accuracy of 100 % was achieved in some experiments.

Introduction

Breast cancer is a leading cause of death in women worldwide. The disease has often times no symptoms till it advances to a dangerous level. It is therefore highly recommended to carry out screening tests after a certain age. The best screening method to date is the mammography, in which both the breasts are imaged with low dose x-ray radiation. Nowadays digital mammography has become the standard screening practice.

As mammography is highly subject to the expertise of radiologist and prone to errors, a decision support system based on machine learning is highly desirable.

There are two main indicators for breast cancer using mammography. These are masses and microcalcifications. Often times before a suspicious mass appears in the mammogram, very fine specs appear in the image, which is caused by micro-calcifications (MCs). The MCs that are 1 mm or smaller in diameter and appear in clusters are more likely to be cancerous while those that are larger in size and scattered randomly are often benign. A mass on the other hand is considered benign if its shape is round or oval and the margins are circumscribed, while it is malignant if it is irregular, stellate or micro-lobulated in shape. The density of breast is such that the mammogram shows a very low contrast between parenchymal tissue and a mass and hence very difficult to isolate the two, visually. A number of methods have been developed for computer based classification of the masses and microcalcifications. Before classification the mammogram image is preprocessed using digital filters to enhance the different regions of the image. The masses and microcalcifications are then outlined using segmentation techniques. Before these segmented images could be classified using machine, a machine learning system is trained with a large set of mammograms that are classified by expert radiologists. There are a number of mammogram databases available on the internet. The two most popular of them are Digital Database for Screening Mammography (DDSM) at the University of South Florida1 and the MIAS 2In this paper we present our work in classifying the masses and MCs seen in mammograms, as either benign or malignant. The system that we developed assumes that the physician segments the masses or MCs manually using the CROP function, found in most windows based graphic software packages. In order to train our system for classification we had to train it with sample mammogram images from the Digital Database for Screening Mammography (DDSM). These images are available in compressed lossless JPEG format. The Windows versions of the uncompressed images were downloaded under a transfer agreement with Dr. Thomas Deserno (nee Lehmann) Department of Medical Informatics Aachen University of Technology D-52057 Aachen GERMANY, under the IRMA (Image Retrieval in Medical Applications) project. The database contains 2620 cases comprising of Normal, Benign and Malignant, high resolution mammograms. Each case further consists of two views of each breast, the cranio-caudal view and the oblique medio-lateral view. Besides the images, each case has a .ics file that contains information about the patient and the image file. Section 4 gives the details of the work done in preparing the training and testing data for the CGPANN. After training the CGPANN with the former the system is then evaluated with the later.

The paper is organized as follows: The next section titled "Literature Survey" describes the latest research done in the field of mammogram classification. The sections "Cartesian Genetic Programming Evolved Artificial Neural Network (CGPANN)" and "Evolution Strategy" describe the evolutionary computation system that we used for the classification task. The section "Experimental setup" describes the preprocessing and statistical parameters extraction steps needed before mammogram classification. It also describes the network parameters that we chose. The section "Results and Analyses" compares the results of our ex-periments with those of the competitors. Finally, the section "Conclusion and Future work" summarizes the paper and states our intentions for future work in this field.

Literature Survey

A brief review of the work done in the field of mammogram classification is presented below. As the abnormality in mammograms can be in the form of microcalcifications or masses, separate subsections review each of them.

Microcalcifications

In [START_REF] Zhang | Effect of training artificial neural networks on 2d image: An example study on mammography[END_REF] Xuejun et al. presented a number of ANN architectures for detecting microcalcifications (MC) in mammogram images. A back propagation neural network responds to an MC lying in the middle of a region of interest. To reduce the image size, FFT of the image was also determined. Another network with multiple outputs had one of its outputs as 1 when its corresponding input had a microcalcification at its position in the image. A Shift Invariant ANN (SIANN) was also experimented with. The performance of the networks was compared with Triple Ring Filter (TRF) which is a rule based filter [START_REF] Ibrahim | Automated detection of clustered microcalcifications on mammograms: Cad system application to mias database[END_REF]. A sensitivity of 95% was achieved by using SIANN and TRF together.

In [START_REF] El-Naqa | Support vector machine learning for detection of microcalcifications in mammograms[END_REF] Issam et al. presented an SVM based microcalcification (MC) classification technique. In [START_REF] Terashima-Marın | Feature selection for the classification of both individual and clustered microcalcifications in digital mammograms using genetic algorithms[END_REF] Rolando et al. presented a technique in which a mammogram is first preprocessed with a median filter to remove noise. This is followed by binarization. The resulting image is then applied to two Gaussian filters. The optimized difference of Gaussian (DoG) filters is used to enhance those regions in the image that contain bright points. A number of techniques are then applied to this image to detect potential MCs.

In [START_REF] James | Parallel evolution using multi-chromosome cartesian genetic programming[END_REF] Walker et al. discussed a multi-chromosome Cartesian Genetic Programming in general and its application for classification of microcalcifications (MCs) in mammograms, in particular. The process is termed multi-chromosome Evolution (MCE). About 80% test images were classified correctly. In [START_REF] Zhang | Neural vs. statistical classifier in conjunction with genetic algorithm based feature selection[END_REF] Zhang et al. presented a technique in which areas marked by radiologists in the DDSM database were resized and fourteen features extracted from each area. These features are represented by genes in a chromosome of a neural-Genetic Algorithm. A subset of features is applied as input and the NN trained. A random population of subsets is generated and each individual is evaluated. Genetic operators of crossover and mutation are applied. The NN with the best classification rate together with the selected feature subset is chosen. It was observed that the highest classification result using the proposed algorithm with NN classifier was 85%.

Masses

In [START_REF] Vasantha | Classifications of mammogram images using hybrid features[END_REF]the authors preprocessed and segmented images from popular databases on the basis of grey level distribution and texture using Otsu's method. They ex-tracted the intensity histogram and Gray Level Co-occurrence Matrix (GLCM) features. To improve prediction accuracy the author used a hybrid of Genetic Algorithm (GA) and Linear Forward Selection (LFS) algorithms. For classification they used the machine learning package WEKA and trained the system using J48 decision tree method. The classification accuracy based on the selected features was 86.7%. In [START_REF] Gulzar | Breast cancer detection using mammography[END_REF] the author presents mammogram classification technique using Linear Vector Quantization (LVQ). Best classification accuracy of 99% was achieved with 100 DDSM cases.

In [START_REF] Martí | Active region segmentation of mammographic masses based on texture, contour and shape features[END_REF] the authors present an algorithm that is based on the principle that a mass segment has uniform texture, its margins should coincide with the maximum gradient points that corresponds to the edges and that the mass profile shape has minimum changes. In [START_REF] Hong | A topographic representation for mammogram segmentation[END_REF], [START_REF] Hong | Segmentation of regions of interest in mammograms in a topographic approach[END_REF] the authors present mammogram image segmentation based on Iso-level contour map representation of the image.

In [START_REF] Saidin | Segmentation of breast regions in mammogram based on density: A review[END_REF] a detailed review of the work done in segmentation and classification of the different anatomical regions of the breast is presented. In [START_REF] Abdalla | Detection of masses in digital mammogram using second order statistics and artificial neural network[END_REF] the authors used Gray Level Co-occurrence Matrix (GLCM) to extract second order statistical descriptors of the texture from the masses. These features were applied to error back propagation ANN for classification. The best performance result that they obtained had 91.67% sensitivity, and 84.17% specificity.

In [START_REF] Zhang | Image enhancement and edge-based mass segmentation in mammogram[END_REF] the authors made use of the chain code in the overlay files of mammograms, in the DDSM database. A rectangular image is formed from the ROI defined by the chain code. The image is preprocessed and a GLCM formed from it. The Haralick energy descriptors are then determined from the GLCM. Adaptive thresholding is applied to the image so formed to detect edges. A binary image is thus formed. The morphological operation of image filling is applied to all closed path edges. The filled area that has the largest overlapping with the central part of ROI is the segmented mass.

In [START_REF] Delogu | Characterization of mammographic masses using a gradient-based segmentation algorithm and a neural classifier[END_REF] the authors present a technique for segmentation and classification of masses. For segmentation the highest intensity point inside the ROI is taken as center and radial lines drawn to its margins. Critical point, the point with highest local variance on each line is detected and new ROI drawn by linearly interpolating in between these points. Sixteen different morphological and textural features of the segmented masses are computed and applied to an ANN for classifying the mass as benign or malignant.

In [START_REF] Tahmasbi | Mass diagnosis in mammography images using novel ftrd features[END_REF] the authors present a technique focusing on utilization of mass margin descriptors called Fourier Transform of Radial Distance (FTRD). These features are applied to an MLP ANN for classification of the mass as either benign or malignant. The best accuracy that they achieved was 92.8%.

In [START_REF] Belal | Mammogram computer aided diagnosis[END_REF] the authors present a mammogram classification system based on computational and human features. These features include shape, size and margins of the mass, patient age and tissue density. The density values are represented in Breast Imaging Reporting and Data System (BI-RADS). Textural features are found using Spatial Gray Level Dependence Method (SGLDM) and Run Difference Method (RDM). Sequential Forward Selection technique and genetic algorithm technique were used for classification.

In [START_REF] Eddaoudi | Masses detection using svm classifier based on textures analysis[END_REF] the authors present a mass detection technique in which the pectoral muscles are segmented and removed. The mass inside the breast is then segmented using intensity thresholding. The segmented mass is analyzed for its textural features, proposed by Haralick, using the gray level co-occurence matrix (GLCM). The textural indices are applied to a support vector machine (SVM) for training and classification. An average classification rate of 95% was achieved.

Cartesian Genetic Programming Evolved Artificial

Neural Network (CGPANN)

In CGPANN a neural network is developed by evolving its inter-node connections, weights, output connection(s) and the activation functions. It's an enhancement to the popular Cartesian genetic programming [START_REF] Miller | Cartesian genetic programming[END_REF]. The nodes and connections in CGPANN are arranged as a graph with rows and columns. A CGPANN node, shown in fig. 1b, consists of a summer and an activation function, similar to an ANN neuron. The summer takes its inputs from other nodes through weighted connections. Each connection additionally has a switch that can be turned On or Off. The number of inputs to each node, number of rows, number of columns and levels-back are predefined.

A CGPANN genotype is a string of integers, each representing one of the network quantities. A typical phenotype and its related genotype can be seen in fig. 1a. For each node the letters F I W C .. have the following meanings and possible values. F: Activation function-sigmoid or Tangent Hyperbolic; I: The node connected to an input of this node, only a node in a column on the left or a network input are allowed; W: connection weight (-1 to +1); C: on-off switch (0 or 1); O: Network output, all nodes and network inputs are allowed to connect to it. Nodes of the corresponding phenotype are numbered sequentially, starting with the top node in the first column followed by the nodes down the column, followed by all the columns to the right in the same manner. When the genotype is decoded to phenotype, outputs of the nodes that don't connect to any other node are called inactive nodes. During evolution, a certain percentage of genes are randomly picked and mutated to allowed values only. Unlike other ANN configurations that use both crossover and mutation, CGP and its derivative CGPANN give excellent results with mutation only. During the process many inactive nodes become active and vice versa. CGP architectures and its derivative CGPANN have been investigated on a number of problems in the past [START_REF] Masood | Breast cancer detection using cartesian genetic programming evolved artificial neural networks[END_REF][START_REF] Masood | Bio-signal processing using cartesian genetic programming evolved artificial neural network (cgpann)[END_REF][START_REF] Masood | Classification of arrhythmia types using cartesian genetic programming evolved artificial neural networks[END_REF].

Evolution Strategy

We use a 1+ λ (Number of Offspring) evolution strategy in which λ = 4. The pseudo-code for the algorithm that we use for training and testing is presented below.

-Prepare the set of parameters to be classified and a set of corresponding target outputs. -Form the initial population of fifty genotypes by assigning random, yet legitimate values to the genes of each genotype as discussed above.

-Generate new population with the fittest genotype and its four replicas. Accuracy of the result has been used as the fitness measure for this application. -Randomly mutate 10% (Mutation Rate) of each replica, forming four offspring. -Determine fitness of the parent and the offspring and select the fittest to make the next parent. If the parent and an offspring have equal fitness, priority is given to the offspring over the parent, [START_REF] Miller | Cartesian genetic programming[END_REF]. The fitness improves from generation to generation until the iterations are stopped. -Evaluate the performance of the trained network by applying the testing data.

-The system is now ready to classify a new pattern.

-END

Experimental Setup

We trained our classifier system with 1000 mammogram images of benign and malignant types each. Using the Matlab command GET DDSM GROUNDTRUTH we extracted the image information from the groundtruth file. The overlay file inside the groundtruth file contains the following information: lesion type, assessment, subtlety, pathology, annotations and a chain code representing the region of interest (ROI) marked by expert radiologists. The function is normally used to get a binary image of the ROI but we modified it to return a rectangular image that contains this ROI (see fig. 2c). The network trained with parameters from these rectangular images, containing masses and MCs, makes it capable to accept parameters from manually segmented images (using the CROP function) easier. A Gray Level Co-occurrence Matrix (GLCM) of an image is then formed.

The matrix contains information about the frequency of gray level repetition between pixels at a certain offset distance and angle and can be used to extract statistical parameters of the image. Out of the many possible second order statistical texture descriptors, proposed by Haralick [START_REF] Haralick | Texture features for image classification[END_REF], we extracted only contrast, energy, homogeneity and correlation. Each of these four parameters were determined for four different angles and a certain distance, using the graycoprops function in matlab. The sample parameters were divided into a training set and a testing set for training and testing our CGPANN. See equations ( 1) to (4) for the four Haralick's parameters.

Contrast = N -1 i,j=0 P ij (i -j) 2 (1)
Energy = N i=1 N j=1 p(i, j) 2 (2)
Homogeneity = N -1 i,j=0 P ij 1 + (i -j) 2 (3)
Correlation = [ (ij)p(i, j)] -µ x µ y σ x σ y (4)
Where p(i, j) is the normalized entry in row i and column j of the GLCM, i is the intensity of one pixel while j is that of the next pixel making the pair for GLCM [START_REF] Abdalla | Detection of masses in digital mammogram using second order statistics and artificial neural network[END_REF]. We get a total of 16 parameters. A 10-fold cross validation strategy was adapted, where ten distinct data sets are formed. Each set has nine parts for training and one for testing. We experimented with the following six distance offsets (D): 4, 8, 12, 16, 20 and 24, and found that for D=20 we got the best average 10-fold accuracy result i.e. Accuracy=90.85%, Sensitivity=86.2% and Specificity=95.5%. We performed five experiments with this offset value, each time using a different seed for random number generator in the initial population in CGPANN. The tenfold results for these experiments are shown in table 1.

The CGPANN network that we used has the following features: Number of nodes= 100 (10rows × 10columns), Inputs per node= 3 and Number of out-puts= 1(Average of ten outputs). An input-output set contains the 16 statistical parameters as inputs and a target output that is 0 for benign and 1 for malignant. In the process of evolution, an initial population of 50 networks was formed randomly. Each network is applied all the 2000 sample parameters and its fitness determined using the following metrics: Fold-10 Acc Sen Spec Acc Sen Spec Acc Sen Spec Acc Sen Spec Acc Sen Spec 95.4 90.8 100.0 97.5 95.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 72.2 61.2 83.2 Table 1: Average values for training and testing results for five independent evolution runs with offset:20 and 10-fold cross validation; Acc: accuracy, Sen: Sensitivity, Spec: Specificity

Results from other researchers for comparison Acc Sen Spec Al Mutaz et al. [START_REF] Abdalla | Detection of masses in digital mammogram using second order statistics and artificial neural network[END_REF] (mass) 87.9 91.67 84.17 M Vasantha et al. [START_REF] Vasantha | Classifications of mammogram images using hybrid features[END_REF] (mass) 86.7 Zhang et al. [START_REF] Zhang | Neural vs. statistical classifier in conjunction with genetic algorithm based feature selection[END_REF] (MC) 85 Amir Tahmasabi et al. [START_REF] Tahmasbi | Mass diagnosis in mammography images using novel ftrd features[END_REF] (mass) 92.8 Fatima Eddaoudi et al. [START_REF] Eddaoudi | Masses detection using svm classifier based on textures analysis[END_REF] (mass) 95 Proposed method (overall 10-fold average ) (Both MC and mass) 90.58 85.32 95.84 Table 2: Comparative results from other authors and the overall 10-fold average from the proposed method; MC: Micro-calcifications, Acc: accuracy, Sen: Sensitivity, Spec: Specificity

Where N=Number of samples, A=Actual, T=Target. We chose accuracy as the measure of fitness for our network. Thus in the initial population the network that has the highest accuracy is chosen as the parent for the next generation. The parent, together with four of its mutated replicas, form the next generation. The fittest of these five networks form the new parent. This process repeats till we get the required fitness. In our case the fitness became almost stable after 100,000 generations so we stopped the experiments at 200,000 generations.

Results and analyses

In this project we tried to provide a user friendly mammogram classification system using image statistical parameters and CGPANN. Table 1 shows that although many of the accuracy, sensitivity and specificity values in the 10-fold cross validation strategy test results are above 90%, some are infact 100%. Table 2 shows the comparative results for a few other authors in comparison to our proposed work. All these authors have tried to classify either masses or micro- calcifications alone. In comparison, our method classifies a sample set containing both masses and microcalcifications. Amongst the authors who worked in this area, Al Mutaz et al. [START_REF] Abdalla | Detection of masses in digital mammogram using second order statistics and artificial neural network[END_REF] used the same Haralick's statistical texture descriptors as we did and the same database for their system training and testing. The main difference however is that they used an MLP ANN as the computational intelligence system for classification while we used CGPANN.

Conclusions and Future Work

In this paper we have attempted to classify mammograms for both masses and microcalcifications. The reason for this versatility lies in the fact that irrespective of the type of abnormality the technique relies on the textural characteristics of the abnormality on which our network is trained. Unlike this approach, most of the other techniques that we reviewed in the literature classify only masses or microcalcifications alone. We also developed the method to convert the chain code for ROIs, associated with the images, into rectangular image sections and training our network with the statistical parameters obtained from them. This makes the system simple to use in a windows based graphical environment for real mammogram classification. We evaluated our system with a 10-fold cross validation strategy and got an accuracy of 100% in some experiments (see table 1). In the current work the mammogram is segmented manually. Our system only classifies the region for benignity or malignancy. In future, we intend to work on automatic mammogram segmentation as well. We would then be able to segment and classify the image on a single platform.

Fig. 1 :

 1 Fig. 1: (a) A typical CGPANN phenotype. Nodes 3, 5, and 9 are inactive and the remaining nodes are active. (b) Internal view of a single CGPANN neuron

Fig. 2 :

 2 Fig. 2: Conceptual Illustration of (a) Gray Level Co-occurence Matrix (b) GLCM offsets (c) A mammogram with a malignant mass, outlined by expert (Red) and generated by software (White Rectangle). Courtesy of TM Deserno, Dept. of Medical Informatics, RWTH Aachen, Germany for the mammogram image

http://marathon.csee.usf.edu/Mammography/Database.html

http://peipa.essex.ac.uk/info/mias.html

Acknowledgments

Many thanks to TM Deserno, Dept. of Medical Informatics, RWTH Aachen, Germany, for providing the windows version of DDSM mammogram images.