This chapter summarises the results of the experiments that were reported in Part III of this thesis.

Section 18.1 examines the performance of the sensor model by analysing the results of the wall-following explorations that were presented in Chapter 13. Section 18.2 uses the same experimental data to consider the effectiveness of the feature-based map-building algorithm.

Chapters 12 to 17 described a variety of exploration strategies and presented the results of experiments to evaluate those strategies. Section 18.3 collects those experimental results together in order to compare all of the autonomous strategies across the set of test environments.

Section 6.3 introduced a sensor model in which adjacent sonar returns of similar range were grouped into ‘readings’ to decrease the uncertainty caused by the width and uneven strength of the sonar beam. Table 18.1 shows the number of readings of each size that were taken during the wall-following explorations of the three main test environments. It can be seen that approximately 20% of the readings contained two or more returns. Expressed in terms of the raw returns instead of the readings, the results show that 37.5% of the returns were included into groups of size two or more. (Maximum-range returns are excluded from the grouping process and from this calculation.) This supports the opportunistic nature of this approach, grouping the returns where possible but using all of the available information. An insistence that groups contain at least two returns would have eliminated almost two-thirds of the returns.

Map construction is an essential component of the research reported in this thesis. This chapter examines the reasons why a mobile robot might need a map and reviews the variety of types of world model which have been devised and implemented by previous researchers.

Early research work into mobile robots (Moravec 1983; Crowley 1985) took it as axiomatic that an effective mobile robot would need an environment model. The process of control was viewed as two steps: first the robot uses its sensors to build a world model and then it uses the world model to plan and execute its actions. The details could vary (different sensor modalities, different data structures for the world model) but the underlying two-step process was not questioned.

In the mid-1980's a number of researchers, most prominent among them being Rodney Brooks (1986), became frustrated with the perceived slow progress in mobile robotics and began to search for an alternative approach to the ‘traditional’ dependence on environment models. The intention was to minimise the processing between sensing and action. Robots were built in which there was an almost immediate link between the robot's sensors and its actuators. (Braitenberg's excellent book ‘Vehicles’ (1984) describes, in the form of thought experiments, what could be achieved by such robots.) The robots were able to perform tasks such as approaching beacons, avoiding obstacles, and following walls. These behaviours were found to be very robust. Brooks's robots could operate in unmodified office environments, sharing their world with unpredictable humans.

Published work shows a variety of approaches to exploration for mobile robots, ranging from disregarding the issue completely through to detailed mathematical analysis of exploration algorithms. This chapter reviews this work in the context of the recent debate between ‘reactive’ and ‘model-based’ robotics (as discussed in Section 2.1).

Many of the published papers on the map-building and navigation of mobile robots do not consider the question of exploration at all. This is, of course, often just a choice of research focus; effort is expended on the mechanics of map construction from sensor data without worrying about how the sensing positions were selected. On the other hand there are theoretical reasons why some researchers have chosen not to study exploration. A robot will not need to explore if its application is such that it does not need a map (Brooks 1990, pages 8–9) or if the map is to be supplied by the operator (Crowley 1985; Drumheller 1987). Neither of these arguments apply in the context of this thesis. Section 2.1 argued that a map was needed for the proposed delivery application and Section 3.4 explained the reasons for allowing ARNE to build its own maps.

Some researchers (Engelson (1992), for example) have adopted a strategy of ‘passive’ mapping, in which the map is built while the robot carries out its normal activities. In contrast, the current research proposes an initial exploration period during which the robot' objective is simply to learn about its environment.

Chapters 12 and 13 showed the results of exploring by wall-following. How, if at all, can that performance be bettered? This chapter begins by describing, in Section 14.1, some circumstances in which wall-following appears to be inefficient and then, in Section 14.2, proposes a new strategy, Supervised Wall-Following, to eliminate these inefficiencies.

Section 14.3 presents the results of experimental tests of Supervised Wall-Following. Its value is shown to be higher in more complex environments.

Section 14.4 summarises the results and suggests some directions in which the algorithm could be developed.

14.1 Shortcomings of Wall-Following

In the wall-following experiments described in the previous two chapters, ARNE was specifically denied access to the map while making navigational decisions. A consequence of this was that a human observer watching the exploration (and looking at the map) would become frustrated by ARNE's inflexibility. In certain circumstances ARNE would make movements which, to the human observer, would simply appear to be ‘stupid’. Three of the most obvious circumstances are: falling into traps, re-examining known objects, and repeating fruitless examinations. The remainder of this section considers each of these problems in turn, illustrating with examples.

Figure 14.1 shows a simple example of a wall-following trap. ARNE began at position 6 in room ‘Columns’, close to one of the free-standing cylinders. It began to circulate around the cylinder and continued to do so for the entire exploration period. This obviously restricted its view of the environment and limited the quality of the map.

This chapter describes the map-building algorithms which were designed and implemented in this research. Figure 7.1 shows that the sonar readings (as described in Chapter 6) and knowledge of ARNE's position are combined to generate a sequence of feature-based representations and a free-space map.

The sensor model that was developed in Chapter 6 showed that positional uncertainty in the sonar returns could be decreased by grouping multiple returns from the same viewpoint. But uncertainty, especially angular uncertainty, still remains. The objective of the algorithms in this chapter is to reduce the uncertainty further and build an accurate representation of the environment.

More value can be derived from a sensor reading by examining it in the context of preexisting information about the world. This information comes from two sources; either the latest map or sensor data which has not yet contributed to the map. As an example of the first type, imagine that the current map shows that there is a wall directly in front of the robot. If a sensor reading is then obtained which is consistent with a sonar reflection from that wall, the range reading can be used to update the estimated position of the wall. The uncertainty due to beam width has been eliminated and the new range reading can be averaged with the existing knowledge to limit the impact of unpredictable errors.

Unfortunately map-building is not quite this simple. First, there is the ‘bootstrap’ problem of gathering enough initial information so that sensor readings can be matched with known objects.

Introduction

In this chapter the main results of the thesis are summarised. The extent to which these address the problems facing performance analysis, identified in Section 2.4, is assessed. In Section 9.4, the direction for further work and future development of PEPA, as it appeared at the end of the thesis, are discussed. The chapter concludes with a review of work which has been developed since the thesis was completed, particularly examining the extent to which the areas outlined in Section 9.4 have been addressed.

Summary

A compositional approach to performance modelling has been presented. This novel model construction technique, based on the stochastic process algebra PEPA, has been shown to be suitable for specifying a Markov process. This underlying process can subsequently be solved using any appropriate numerical technique. The ease with which models can be constructed and modified using PEPA was demonstrated in the case studies presented in Chapter 4. For example, when the effect of a faulty component was to be investigated, only the relevant component within the model had to be modified.

As outlined in Section 3.6, one of the major advantages of PEPA over the standard paradigms for specifying stochastic performance models is the inherent apparatus for reasoning about the structure and behaviour of models. In the later chapters of the thesis this apparatus has been exploited to define four equivalence relations over PEPA components. Each of these notions of equivalence has intrinsic interest from a process algebra perspective.

Introduction

In this chapter we develop a strong bisimulation, based on the labelled multi-transition system for PEPA developed in Chapter 3, and examine some of its properties. The strong bisimulation relation aims to capture the idea that strongly bisimilar components are able to perform the same activities, resulting in derivatives that are themselves strongly bisimilar. In Section 7.2 we show how this property may be expressed in the definition of a strong bisimulation relation. Strong bisimilarity is then defined as the largest relation satisfying the conditions of a strong bisimulation relation.

The rest of the chapter is concerned with the properties exhibited by the strong bisimilarity relation, ∼. In Section 7.3 the relation is investigated from a process algebra perspective. In particular it is shown that strong bisimilarity is a congruence relation for PEPA. The implications of strong bisimilarity for the system components being modelled are discussed in Section 7.4. The relationship between strong bisimilarity and the underlying Markov process is examined in Section 7.5, as we investigate whether the partition induced by the relation forms a suitable basis for exact aggregation. This is found not to be the case.

Finally in Section 7.6 we suggest how strong bisimilarity may be used as a model simplification technique. The relation is used to find components which exhibit the same activities. These may then be subjected to a simple further test to ensure that the behaviours of the components are indeed the same.

Introduction

This chapter presents the background material for the thesis. The field of performance modelling is introduced and the standard paradigms for specifying stochastic performance models, queueing networks and stochastic Petri nets, are reviewed. In Section 2.3 process algebras are introduced, and some of the extensions into timed and probabilistic processes are considered in the following subsections. In particular we describe the Calculus of Communicating Systems (CCS), and various extended calculi based upon it.

We present the motivation for applying process algebras to performance modelling in Section 2.4. This outlines the objectives of the work presented in the remainder of the thesis. Finally, in Section 2.5, some related work, involving process algebras and performance evaluation, is discussed.

Performance Modelling

Performance evaluation is concerned with the description, analysis and optimisation of the dynamic behaviour of computer and communication systems. This involves the investigation of the flow of data, and control information, within and between components of a system. The aim is to understand the behaviour of the system and identify the aspects of the system which are sensitive from a performance point of view.

In performance modelling an abstract representation, or model, of the system is used to capture the essential characteristics of the system so that its performance can be reproduced. A performance study will address some objective, usually investigating several alternatives— these are represented by values given to the parameters of the model.

Performance modelling is concerned with the capture and analysis of the dynamic behaviour of computer and communication systems. The size and complexity of many modern systems result in large, complex models. A compositional approach decomposes the system into subsystems that are smaller and more easily modelled. In this thesis a novel compositional approach to performance modelling is presented. This chapter presents an overview of the thesis. The major results are identified.

A significant contribution is the approach itself. It is based on a suitably enhanced process algebra, PEPA (Performance Evaluation Process Algebra). As this represents a new departure for performance modelling, some background material and definitions are provided in Chapter 2 before PEPA is presented. The chapter includes the motivations for applying process algebras to performance modelling, based on three perceived problems of performance evaluation. The recent developments of timed and probabilistic process algebras are unsuitable for performance modelling. PEPA, and related work on TIPP [1], represent a new area of work, stochastic process algebras [2]. The extent to which work on PEPA attempts to address the identified problems of performance evaluation is explained. The chapter concludes with a brief review of TIPP and other related work.

Chapter 3 presents PEPA in detail. The modifications which have been made to the language to make it suitable for performance modelling are explained. An operational semantics for PEPA is given and its use to generate a continuous time Markov process for any PEPA model is explained.

Introduction

In this chapter we develop a framework to analyse notions of equivalence between models. Within this framework we present several equivalences which have been applied to process algebra models and performance models. By notions of equivalence we mean criteria which may be applied to determine whether two entities can be considered to be, in some sense, the same. For example, a common concern for most modelling methodologies is model verification—the problem of ascertaining whether a model is the same as the system under study, in the sense of providing an adequate representation to meet the objectives of the study. For a performance model “adequate representation” is usually interpreted as the calculation of certain quantitative performance characteristics within acceptable error bounds. For a process algebra model it is interpreted as a condition on the observable behaviour of the model, as represented by its actions, compared with the observable or intended behaviour of the system.

The framework we consider identifies three different classes of entity-to-entity equivalence which may arise during a modelling study: system-to-model equivalence, model-to-model equivalence and state-to-state equivalence. We will see that for process algebra models these equivalences are all addressed by a single notion of equivalence, the bisimulation. Two agents are considered to be equivalent in this way when their externally observed behaviour appears to be the same. This is a formally defined notion of equivalence, based on the labelled transition system underlying the process algebra.

Introduction

In this chapter an alternative notion of equivalence for PEPA components is developed. This equivalence, strong equivalence, is defined in Section 8.2. It is developed in the style of Larsen and Skou's probabilistic bisimulation which was discussed in Section 5.2.3. Here transition rates, already embedded in the PEPA labelled transition system as activity rates, are used instead of probabilities. As with strong bisimulation the relation aims to capture a notion of equivalent behaviour between components. However, observation now occurs without detailed knowledge of the individual transitions involved. Strong equivalence, unlike strong bisimulation, is unable to distinguish between a single (α, 2r) activity and two simultaneously enabled instances of the (α, r) activity.

Some properties of the relation from a process algebra perspective are examined in Section 8.3. Like strong bisimulation, strong equivalence is found to be a congruence relation for PEPA. In Section 8.4 we discuss some of the implications of strong equivalence for the system components being represented, and in Section 8.5 the implications for the underlying Markov processes are reviewed. Finally, in Section 8.6, we outline the use of strong equivalence as a state-to-state equivalence forming the basis of exact aggregation. An alternative approach to the generation of the Markov process underlying a PEPA model is also discussed. These ideas are illustrated in Section 8.6.3 with an example taken from Section 4.4.4.

Introduction

In this chapter we present a modelling study demonstrating the use of PEPA for performance evaluation. Examples drawn from the modelling study will be used to exhibit the model simplification techniques developed later in the thesis. This study considers and compares various multi-server multi-queue systems. Such systems, an extension of the traditional polling system, have been used to model applications in which multiple resources are shared among several users, possibly with differing requirements. Examples include local area networks with multiple tokens, and multibus interconnection networks in distributed systems. Similar systems have been investigated in [26, 84, 85, 86, 87, 88].

A polling system consists of several queues and a single server which moves round the queues in cyclic order. These systems have been found to be good models of many systems which arise in computer network and communication scenarios, and consequently they have been extensively studied. A recent survey by Takagi [89] references over four hundred contributions.

A variety of extensions and modifications to the traditional polling system have been investigated [89], including non-cyclic polling, priority queues, and queues with feedback. One extension which is particularly suited to modelling innovative local area networks is the introduction of additional servers, each of which moves around the queues providing service where it is needed. These systems, sometimes known as multi-server multi-queue systems, are not readily amenable to queueing theory solution. Several suggested approximation techniques, based on queueing theory, and exact solutions based on GSPNs are reviewed in Section 4.3.1.

Introduction

This chapter presents the Performance Evaluation Process Algebra (PEPA). This language has been developed to investigate how the compositional features of process algebra might impact upon the practice of performance modelling. Section 3.2 outlines the major design objectives for the language. Most of the rest of the chapter is taken up with the subsequent informal and formal descriptions of the language, and a description of its use as a paradigm for specifying Markov models. Some simple examples are presented to introduce the reader to the language and its use in describing systems. This establishes PEPA as a formal system description technique. Presentation of more complex examples is postponed until Chapter 4.

The use of PEPA for performance modelling is based on an underlying stochastic process. It is shown that, under the given assumptions, this stochastic process will be a continuous time Markov process. Generating this Markov process, solving it and using it to derive performance results are presented and illustrated by a simple example. The relationship between PEPA and established performance modelling paradigms is discussed in Section 3.6.

Design Objectives for PEPA

An objective when designing a process algebra suitable for performance evaluation has been to retain as many as possible of the characteristics of a process algebra whilst also incorporating features to make it suitable for specifying a stochastic process.

Introduction

In this chapter we develop a very strong notion of equivalence between PEPA components called isomorphism. This is a condition on the derivation graphs of components and it ensures that components are only considered equivalent if there is a one-to-one correspondence between their derivatives and they are capable of carrying out exactly the same activities. It is not an observation based notion of equivalence in the style of bisimulation which is usual for process algebras. It is structural, in the style of the equivalence between Markov processes introduced in Section 5.3. Isomorphism is defined in Section 6.2.

In Sections 6.3 to 6.5 we examine some properties of this notion of equivalence, from the perspectives of a process algebra, the modelled system components and the underlying Markov processes. As we might expect from such a strong notion of equivalence, we can derive strong properties for isomorphism. The relation is a congruence for PEPA. The relationship between isomorphism and the Markov processes underlying the PEPA components is found to be a close one—isomorphic components generate equivalent Markov processes.

In the remainder of the chapter we develop a weaker form of this equivalence called weak isomorphism. This equivalence reflects the hidden nature of τ type activities. We will consider two components equivalent in this way if they only differ in their capabilities to carry out such activities. A definition of this notion of equivalence is presented in Section 6.6.