<figure><img src="image_1.png" /></figure>

HAL
open science

# Assisted Navigation for Persons with Reduced Mobility: Path Recognition Through Particle Filtering (Condensation Algorithm)

Régis Grasse, Yann Morère, Alain Pruski

► To cite this version:

Régis Grasse, Yann Morère, Alain Pruski. Assisted Navigation for Persons with Reduced Mobility: Path Recognition Through Particle Filtering (Condensation Algorithm). Journal of Intelligent and Robotic Systems, 2010, 60 (1), pp.19-57. 10.1007/s10846-010-9406-y. hal-04928667

HAL Id: hal-04928667

https://hal.univ-lorraine.fr/hal-04928667v1

Submitted on 4 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Assisted Navigation for Persons with Reduced Mobility: Path Recognition Through Particle Filtering (Condensation Algorithm)

Régis Grasse · Yann Morère · Alain Pruski

Received: 28 April 2008 / Accepted: 22 February 2010 / Published online: 19 March 2010
© Springer Science+Business Media B.V. 2010

**Abstract** In the few past decades, several international researchers have worked to develop intelligent wheelchairs for the people with reduced mobility. For many of these projects, the structured set of commands is based on a sensor-based command. Many types of commands are available but the final decision is to be made by the user. A former work established a behaviour-based multi-agent form of control ensuring that the user selects the best option for him/her in relation to his/her preferences or requirements. This type of command aims at “merging” this user and his/her machine—a kind of symbiotic relationship making the machine more amenable and the command more effective. In this contribution, the approach is based on a curve matching procedure to provide comprehensive assistance to the user. This new agent, using a modelization of the paths that are most frequently used, assists the user during navigation by proposing the direction to be taken when the path has been recognized. This approach will spare the user the effort of determining a new direction—which might be a major benefit in the case of severe disabilities. The approach considered uses particle filtering to implement the recognition of the most frequent paths according to a topological map of the environment.

**Keywords** Assistance to navigation · Particle filtering · Condensation algorithm · Course modelling · Recognition · Smart wheelchair

<footnote>R. Grasse · Y. Morère (✉) · A. Pruski
LASC, Université Paul Verlaine—Metz, Île du Saulcy,
BP 80794, 57012 Metz Cedex 1, France
e-mail: yann.morere@lasc.univ-metz.fr, morere@univ-metz.fr</footnote>

<footnote>R. Grasse
e-mail: regis.grasse@lasc.univ-metz.fr</footnote>

<footnote>A. Pruski
e-mail: alain.pruski@lasc.univ-metz.fr</footnote>
# 1 Introduction

Mobility is a need that all human beings share; but some of them suffer severe disabilities preventing them from moving in wheelchairs driven by hand or electric wheelchairs operated by a joystick. Some specialized interfaces have been developed using speech, breath or muscle contraction to make it possible for the user to transmit a command that the machine can perceive. However, these interfaces do not offer the possibility of giving specific directional orders to operate the wheelchair directly.

It is possible to use a so-called smart interface (On/Off switch in combination with a rotating cursor on an interface) to select the desired direction [1]. The wheelchair control device acquires intelligence through reactive behaviours (e.g. obstacle avoidance, assisted navigation) [2, 3] and thus deserves the name of “intelligent wheelchair” or “smart wheelchair”. However, we should emphasize that the purpose of these tools is to provide assistance to the user and not substitute itself to him/her as an operator for the movements.

The objective of the VAHM (Autonomous Vehicle for Motor Disabled Persons) project [4] that has been conducted by LASC (Laboratoire d'Automatique humaine et de Sciences Comportementales) since the early 90s is to develop an intelligent wheelchair; it is comparable to what several research centres are trying to achieve:

- the NavChair project from the University of Michigan [5]. It uses a behavior-based control and a joystick,

- the ROLLAND project, from the University of Bremen [6]. It uses a neural network based control and a camera.

- the CWA (Collaborative WheelchAir) project from the National Institute of Singapore [7]. It uses a neural control system and recorded courses to navigate.

- the CCPWNS (Computer-Controlled Power Wheelchair Navigation System) from the University of Notre Dame [8]. It uses a manual learning control system, two cameras, odometric coders and ultrasonic (US) sensors.

- the INRO (INtelligent ROllstuhl), from the University of Mannheim [9]. It uses a GPS, a laser sensor, US sensors.

- the Intelligent Wheelchair System project from the University of Osaka [10]. It uses two cameras to control the navigation. The first one operates a facial recognition of the user to determine the direction to follow, and the second one is designed to target following.

- the MAID (Mobility Aid for Elderly and Disabled people) project from the University of Ulm [11]. It uses a laser, gyroscope sensor, US sensors to achieve autonomous and semi-autonomous navigation (see Section 1.2).

- the OMNI (Office Wheelchair with High Manoeuvrability and Navigation with Intelligence for People with Severe Handicap), from the University of Hagen (Germany). It uses IR and US sensors and a holonomic mobile base to navigate.

- the RobChair (Robotic Wheelchair) project from the University of Coimbra Polo II [12]. It uses several infrared (IR) and US sensors and a vocal control system.

- the SmartChair project from the University of Pennsylvania [13]. It uses an omnidirectional camera and projected images to control the navigation of the wheelchair.
- the WAD (Wheelchair Attractor Dynamics) from the University of Marseille [14]. It uses several IR sensors and odometric coders. The navigation control is achieved by a graphic user interface on a screen.

- the WATSON project from the Nara Institute of Sciences and Technology (Japan) [15]. It uses two cameras to detect the control from head movements.

The purpose of our project is to offer assistance for navigation in an indoor environment to disabled persons without giving them an impression of just being moved around. The user should at all times be in control of his/her own movements and therefore master the path covered by the wheelchair.

The control architecture developed by our research center offers several levels of assistance in relation to the user’s disability, ranging from the force feedback joystick [16] to near-autonomous operation [17].

The context of the study carried out in our center and reported below is the case of severe disabilities. The system offers additional assistance to navigation to those persons who cannot use standard electric wheelchairs and for whom direction commands—even if generated via a smart interface—is tiring, thus achieving a higher level of autonomy in movement control. The basic idea is to reduce the number of commands without impairing the possibility of maintaining control on the movement. The purpose of our approach is to offer a semi-autonomous navigation assistance when the user operates the wheelchair. We try to recognize the current path from several ones that have been covered earlier. In the case of a good recognition, the device allows to repeat the movement automatically along the path without any intervention of the user. This new function uses a topological map and a particle filtering method, but cannot currently be classified as a SLAM (Simultaneous Location And Mapping) as the topological map is built manually.

We now briefly present smart wheelchairs, their specificities and the asset of the approach presented. A second part will deal with the tools and methods used to achieve our goal. The next part presents the simulation and real results using the VAHM3 smart wheelchair. We conclude with a discussion on the method proposed.

## 1.1 Smart Wheelchairs

Mobile robots have been greatly improved in the past few years due to the development of microelectronics and have become more “intelligent”, responsive and autonomous. This progress has been used to offer improved assistance to disabled persons. The first intelligent wheelchairs appeared in the research centers in the late 80s. There were composed of a robotic base onto which a wheelchair was installed (e.g. Mister Ed [18], the first VAHM prototype [19]); the more recent models of intelligent wheelchairs are generally electric wheelchairs available on the market on which sensors and a computer have been installed (e.g. NavChair [20], OMNI [21], MAid [11], SENARIO [22], VAHM [4]). Other projects (e.g. SWCS [23], SPAM [24], Hephaestus [25], TinMan [26], Siamo [27]) have been developed and designed so as to be “grafted” onto standard electric wheelchairs. The goal of these devices is to offset the difficulties by offering assistance for the generation of a directional order and assistance for navigation. Such wheelchairs call on various operational modes as described below.
## 1.2 Operational Modes

Three operational modes are available for such smart wheelchairs:

- **Autonomous mode:** the user has an interface permitting to select a destination and the wheelchair calculates the path to reach this destination. This method requires accurate positioning of the wheelchair in the environment but does not call for much attention from the user. Using it implies that either the wheelchair has full knowledge of the environment (full metric or topological map) or the environment has been modified due to complementation with landmarks. In such a case, the operational mode does not make it possible to control the changes in the environment or to navigate in an unknown environment; [28, 29];

- **semi-autonomous:** users have assistance for navigation so that they can drive the wheelchair in spite of their disabilities. This method calls for sustained cognitive work and constant attention from the users for path planning. This form of assistance is sometimes restricted to obstacle avoidance but may also be composed of several types of behaviour. The selection process of the best behaviour is to be carried out either by the user [26] (manual adaptation) or in automatic mode [1, 20, 30] (automatic adaptation). The most common automatic selection process used is subsumption [31], but other systems can be used such as systems based on probabilistic reasoning [32] or on case-based reasoning [3];

- **without assistance:** this mode implies using a standard control joystick to drive the wheelchair.

## 1.3 The Assets of This Approach

The cognitive process related to the movement towards a goal calls for a mental pattern composed of several movements [33]. The full set of these movements determines the overall map of the movement and each portion of the path is marked by a change in direction.

These changes in direction imply that the user enters a new command when driving his/her electric wheelchair. In case of severe disabilities, these actions represent difficult tasks. The data collected through the smart control devices carry very little information (On/Off switch, vocal control). In some particular cases, the mere actuation of a sensor can be strenuous. The people affected by such pathologies cannot drive a standard wheelchair. The objective is to design a system by which the wheelchair has assisted navigation so that the number of necessary actions is reduced, while leaving to the user full control on his/her movements and thus offering him/her greater autonomy.

In this context, we cannot envisage to develop a purely autonomous mode; as for the semi autonomous mode—as described in the literature—it calls for numerous actions (cognitive or muscular) to be performed by the user.

The point of this study is to put forward a new operational mode that is “quasi-autonomous”. When the user is not prepared to intervene to control the movement of the wheelchair, the vehicle will follow a known path; in case of need, the user can regain control of the device and then enter a command to set the path that (s)he has planned.
This may seem to be trivial: “following a known path” calls for several things:

- the memory of the smart wheelchair should contain a database with all the paths that are frequently taken;

- to make sure that the wheelchair responds appropriately when in “autonomous” mode, it has to be able to determine its position on a known path. we need a localization method;

- to be able to follow a path that has already been covered, the wheelchair should be able to recognize a path in progress as compared to the database of known paths. We need a path recognition method;

- the user should be in a position to take over the control of his/her movement at any time.

Considering that the smart wheelchair and the user will closely cooperate to cover the path in optimal conditions, we can say that the operational mode of the system is symbiotic [1].

The components necessary for proper localization and path recognition have been listed above. The following paragraph provides a list of tools to be selected for our approach.

# 2 Tools and Methods

## 2.1 The VAHM System

Our research centre has installed the VAHM robot onto a STORM 3 wheelchair manufactured by Invacare and can thus carry out experiments with an instrumented smart wheelchair.

### 2.1.1 *Equipment Architecture*

The VAHM3 Prototype is based on the Invacare STORM 3 wheelchair (cf. Fig. 1). It is equipped with 16 ultrasound sensors (US, see Fig. 2) for direct perception of the environment. The odometric data are provided by incremental coders set on each electric motor. It is also equipped with an onboard computer with a Pentium4 processor running at 2.66 GHz speed, 512Mo RAM capacity under the Windows XP Pro operating system.

### 2.1.2 *Control Architecture*

The control architecture of the VAHM is based on a multi-agent system [3] represented in Fig. 3. The agents are autonomous and communicate between each other with a shared memory.

The agents used are of three different types: behavioural, cognitive and environmental agents.

*The behavioural agents* behavioural agents allow to establish the responses provided by the wheelchair in relation to the environment and the user's commands [1]. The selection of active behaviour on the wheelchair is done on the basis of a case-based reasoning [34].
<figure><img src="image_3.png" /><figcaption>**Fig. 1** VAHM 3 prototype</figcaption></figure>

One of the advantages of this approach is to offer a robust control system.
In case an agent does not work due to the absence of any source information or for
any other functional reasons, this failure will be compensated for by another agent
which might be less efficient but will prevent the system from being blocked. Another

<figure><img src="image_4.png" /><figcaption>**Fig. 2** Distribution of the
ultrasonic sensors on the
VAHM3 prototype</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>**Fig. 3** The multi-agent structure</figcaption></figure>

advantage is that withdrawal or addition of an agent is a transparent process for all aspects of the operation of the system.

The behavioural agents available on the wheelchair are as follows:

- Avoiding an obstacle;

- Following a direction;

- Following a wall;

- Backtracking;

*The cognitive agents* the purpose of these agents is to provide information composed on the basis of data provided by the sensors to the other agents:

- The Wall agent calculating the distance and the angles on both right and left-hand sides of the wheelchair;

- The Detection agent calculating the distances from the obstacles in relation to the preset zones (front side, on the right, on the left, back);

All these agents do not have any direct interaction with the external environment. They operate via the environmental agents.

*The environmental agents* this concept refers to all agents interacting with the external environment of the wheelchair. These agents include:

- the graphic user/developer interface;

- the management of odometric device and motor controls;

- Ultrasonic sensors data management and user control management.

The advantage of this separation is that a modification of the wheelchair or its equipment has no effects on the other components of the system.
## 2.2 Modelization Context

The wheelchair we have designed moved around within indoor environments that are composed of modular blocks. The calculator records the following data during the movement (see Fig. 4):

- active behaviour;

- the position and rotation in relation to the starting point of the path;

- front narrowing (see Fig. 4);

- the distance to the closest obstacle (see Fig. 4);

- linear and angular velocity (see Fig. 4).

These data are sampled in relation to the distance covered by the wheelchair. Time constraints such as stops and paths covered at different speeds can be eliminated. Figure 5 shows an example of a series of paths covered within the same environment.

A path is defined as a set of samples representing a part of the movement of a wheelchair, e.g. a curve plus a straight line.

A course is a set of paths—and therefore samples—representing a part of the movement of the wheelchair that can be used for the modelization. It starts and stops at the intersections between the various places visited by the wheelchair as such junctions may call for changes in direction.

It is then necessary to select a method for localization based on the paths covered by the wheelchair so that an eligible direction is submitted to the user. For that purpose, the VAHM should be able to establish its position from among the set of models representing the environment. As a consequence, the models should represent paths of various sizes which can then be concatenated and represent the environment as a whole as e.g. in Fig. 6. It can be viewed as a topological map.

The idea is to use the complete path covered by the user without “standard” assistance (VAHM 3 standard control architecture) as a reference model of the environment and thus create a topological map.

<figure><img src="image_6.png" /><figcaption>**Fig. 4** Available datas</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>**Fig. 5** Example of a path class</figcaption></figure>

The cutting of whole course in paths and points of intersection is currently carried out *manually* when the user creates the reference model. The points of intersection correspond to a place where the user has achieved a change in direction, the links then correspond to the intermediate paths.

From this cutting, each path becomes a reference model in the future recognition problem. Finally the whole course is modeled by a sequence of paths and intersections linked together. These links are modeled in a network as explained in Section 3.2.1.

<figure><img src="image_8.png" /><figcaption>**Fig. 6** Example of an environment including a set of paths separated by intersections and the associated topological view</figcaption></figure>
Then our system will be in charge of recognizing the path being covered, determine its position on the path and then suggest a direction; the information collected will be used to establish the course for the following times.

We can observe that paths belonging to the same category share various similarities (see Fig. 7). As a consequence, a curve-matching procedure may be applied to facilitate path recognition.

## 2.3 Localization

The work context is that of severe forms of pathology preventing the user from determining and/or maintaining a direction command, or planning a path. It is then up to the system to try and find a solution to these problems. For the wheelchair to respond in the expected manner, it is necessary to know its position on the current path. This problem is identical to those met in autonomous mobile robots. Navigation in a given environment requires the robot to establish its own position so as to carry out a path-planning task.

We can find a more detailed analysis of the navigation tools in [35, 36]. These papers offer a state-of-the-art study on localization, the learning process of environment models and path planning. They consider that navigation in robotics is based on three processes:

<figure><img src="image_9.png" /><figcaption>**Fig. 7** Example of similarities between different routes of a same class</figcaption></figure>
- Acquisition of a map of the environment with a robot memorizing the data during the exploration process under an adequate format.;

- Localization establishing the position of the robot on this map;

- Path planning selecting the series of actions to be performed to reach the goal starting from the current position.

For this experiment, path planning is done by the user. We will focus on the first two points which are closely related to each other. Having a map for localization and an estimation of the position are both necessary to compose a topological map of the environment. The map is built manually by covering usual courses and storing them in an appropriate form.

This close relationship is part of the so-called SLAM (Simultaneous Location And Mapping) issue. We will first remind of the various types of models used for localization and then examine various methods applied to that purpose.

### 2.3.1 The Environment Models

We can identify three main classes of environments used for localization and navigation:

- geometrical models: they describe the environment by using geometrical prim- itives (points, straight lines, arc of a circle...) presenting information about the obstacles or some characteristics of the environment such as wall angles [37–39].

- occupancy grid models: they represent the environment in the form of a grid in which each cell corresponds to a portion of space; this cell is associated to a value corresponding to the probability of occupancy [40–43].

- topological models: they are generated without any knowledge of the metric characteristics of the environment. They represent the structure or skeleton of the environment in the form of nodes and arcs. This model type is often associated to a metric model to facilitate the localization process, as is the case in [44]. This type of modelling has been used in our approach.

### 2.3.2 Location Methods

*Localization with landmarks.* In this type of location, the robot uses artificial landmarks existing in the environment [45].

*Autonomous Location.* Among all these numerous methods, ultrasonic ranging [37], grid representation [42], condensation [43], Monte Carlo localization [46], hidden Markov models [47], geometrical maps [48], multigrid algorithm [49], ultrasound and monocular cooperation [50], fuzzy map [41], some approaches seem to be closer to landmarks systems by using natural landmarks defined as remarkable points existing in the environment [51]. The other direct methods carry out a matching between the data provided by the sensors and those of the model [52]. The metric models represent the near environment made visible by the sensors in geometrical format or in the form of an occupancy grid. Localization is thus operated by a process matching this grid and the model. The advantage offered by this method is that the local map can also be updated on the basis of the data provided by the sensors and the map of the global environment. The process makes it then possible to identify one's location using only a partial map of the environment while integrating the new areas into the
global map. This method is called Concurrent Mapping and Localization (CML) or Simultaneous Location And Mapping (SLAM) [36, 53, 54].

In our case, we use a matching algorithm to achieve autonomous location.

## 2.4 Choice of the Matching Algorithm

The matching algorithm should meet specific constraints to carry out recognition but also perform localization. These constraints are as follows:

- taking model deformation into account as the user covers the same path in different ways (see Fig. 5);

- operating in real time with several observation vectors (data from the wheelchair sensors);

- offering a solution to the problem of the robot acting as if it had been moved offline (calling for an automatic reset of the recognition process);

- providing the position in the model.

The most common algorithms are based on the least squares [48, 55], Kalman filters [38, 51, 56], Markovian models [57–59], condensation (particle filters) [43, 60, 61] or active contours (SNAKES) [62]. This matching process can be operated, either in relation to a known position, or without a priori knowledge of the position of the robot [35].

This paper will not get into the detail of these algorithms and we will be content with comparing their potential. Table 1 indicates how far these algorithms are able to meet the needs.

The various columns represent the key needs to achieve recognition in our context:

- the model of a path involved in the method, should accept some deformations (velocity, trajectory differences in covered path) to take into account the way the user is navigating with the wheelchair. Typically, a simple least square method cannot deal with this problem;

- the method should operate online with short response time to be useful. In a practical way, it should give localization information to each sample. Managing multiple sources of data (US sensors, direction information, distance, velocity)

<table><caption>**Table 1** Comparing matching algorithms in relation with our constraints to carry out path recognition</caption><thead><tr><th></th><th>Model deformations of models</th><th>Real times with several observation vectors</th><th>Is a solution for the problem of the robot responds as if it had been moved offline</th><th>Provides the position in the model</th></tr></thead><tbody><tr><td>Least squares</td><td>No</td><td>Yes</td><td>No</td><td>Yes</td></tr><tr><td>Kalman approaches</td><td>Yes</td><td>Yes but complexity increases</td><td>No</td><td>Yes</td></tr><tr><td>Continuous-HMM</td><td>Yes</td><td>No (offline learning)</td><td>Yes</td><td>No</td></tr><tr><td>Condensation</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td></tr><tr><td>SNAKES</td><td>Yes</td><td>Probably (not tested)</td><td>No</td><td>Yes</td></tr></tbody></table>
is another key point. Clearly, Continuous MMC cannot manage the real time constraint due to offline learning;

- the method should operate with an unknown starting pose of the wheelchair. The method should operate a self-localization in the environment. This key point can't be managed by the Kalman Filter, which needs an *a priori* position of the wheelchair;

- the method should provide the current position recognized in the model in order to anticipate future actions (e.g. direction change) and control the wheelchair. While HMM method can't operate online, it does not fit our constraints.

Only the CONDENSATION (**CONDitional DENSity Propagation**) algorithm meets all the criteria set to achieve path recognition.

The benefit offered by our approach is that the user is integrated into the act of navigating while keeping full control on the movement and maintaining interaction with the machine.

# 3 Method and Implementation of the Particle Filtering on VAHM 3

## 3.1 Curve Matching Using the CONDENSATION Algorithm

The first idea for path recognition consists in studying direct matching of the curves provided by the sensors to make the matching process possible. However this method raises several problems.

### 3.1.1 Problems with Direct Curve Matching

The data selected to perform the matching are the normalized distances between the right and left walls (front and rear narrowing) and the value of the angular velocity provide the derivative of angle $θ$, as shown in Fig. 4. This decision was supported by the results supplied by earlier work based on hidden Markov models, as detailed in [63].

The curves computed from the data provided by the sensors, such as narrowing or angular velocity, can be matched and preliminary classification can be made on the basis of any difference between data provided by the various paths. However, this procedure does not deliver satisfactory results and problems remain. Figure 8 shows differences in terms of position displacement (resulting from the sampling) and magnitude (data supplied by the sensors). The CONDENSATION algorithm [64] can recognize and deal with such deformations.

### 3.1.2 Solution Through Condensation Algorithm

As described in [43], the CONDENSATION algorithm belongs to the general class of Monte Carlo filters discovered in the 1970s [65] and recently revisited in the target tracking issue [66] as reported in the literature dealing with the statistics [67] and vision by computer [60, 68] issue. This algorithm works on a set of random samples or particles to represent the arbitrary propagation of probability density in time. The algorithm also offers the possibility of processing multiple input sources.
<figure><img src="image_10.png" /><figcaption>**Fig. 8** Example of deformation in the case of narrowing as observed with two runs on the same type of path</figcaption></figure>

Moreover, this type of algorithm can deal with curve mapping (applying to ambiguous data, on the basis of the propagation of several states), as opposed to what traditional methods, such as Kalman filter [64], can do.

As the work described in [64] deals with the matching of temporal trajectories, which is quite similar to our context, we initially used the same parameters:

- normal distribution for prediction uncertainty;

- size of the particle cluster;

- number of new random states (updating step);

- amplitude and rate scale.

Then these parameters are tuned empirically to get an efficient method. Final parameters are given in Section 4.1.1.

The idea is basically to operate a matching between a set of *M* models {$m^{(\mu)}/\mu = 1, \dots, M$} and a specific path described by the data provided by the sensors on a sliding window. The data (*D* referring to their number) provided by the sensors are called observations and described at moment *t* by the equation $z_t = (z_{t,1}, \dots, z_{t,D})$.

The models are discretized by a parameter $\phi \in [0, \phi_{max}]$ representing the current position in the model. The values for the model $m^{(\mu)}$ at position $\phi$ can be represented by a vector of dimension *D*: $m_{\phi}^{(\mu)} = (m_{\phi,1}^{(\mu)}, \dots, m_{\phi,D}^{(\mu)})$.
In our context, a random sample (*particle*, *state*) represents the state of the wheelchair at a given position in a model $\mathbf{m}^{(\mu)}$. In order to take into account the variability of the covered path, the model deformations are associated to the particle.

By creating a random cluster of size $N$ (with $N \gg M$, [64]) for these states (*particles*), there is a probability of finding one or more states matching these observations.

A comprehensive description can be found in [64]. Some changes were made for an application to this situation. There are described below:

A state at time $t$ is defined as a vector of parameters $s_t = (\mu, \phi, \alpha, \rho)$ with:

- $\mu$: an integer corresponding to the model number (this number is unique for each model);

- $\phi$: position or phase at time $t$ at which the model is aligned with observations;

- $\alpha$: a parameter of amplitude used to deform a model and adjust its amplitude to correspond to observations;

- $\rho$: a rate enabling to vary the period of model sampling (horizontal adjustment of the model).

The aim is now to establish what is state $s_t^{(n)}$, state $n$ from the particle cluster of size $N$, $n \in \{1, \dots, N\}$ that is closest to observations $Z_t = (\mathbf{z}_t, \mathbf{z}_{t-1}, \dots)$. Let's take $Z_{t,i} = (z_{t,i}, z_{(t-1),i}, z_{(t-2),i}, \dots)$ as the $i^{th}$ observation vector at time $t$, and $i$ refers to data in $[1, \dots, D]$. The probability of observing $\mathbf{z}_t$ knowing state $s_t^{(n)}$ can be determined by

$$p(\mathbf{z}_t|s_t^{(n)}) = \prod_{i=1}^{D} p(Z_{t,i}|s_t^{(n)}), \quad (1)$$

where

$$p(Z_{t,i}|s_t^{(n)}) = \frac{1}{\sqrt{2\pi}\sigma_i} \exp \left( \frac{-\sum_{j=0}^{W-1} \left( z_{(t-j),i} - \alpha \times m_{(\phi-\rho j),i}^{(\mu)} \right)^2}{2\sigma_i^2(W-1)} \right). \quad (2)$$

Equation 1 evaluates the probability including the past values of observations (Vector $Z_{t,i}$). The normalization is made over the $W-1$ past samples of the sliding windows $W$.

The $\sigma_i$ values are estimates of the standard deviation for the curve $i$. Moreover, $\alpha \times m_{(\phi-\rho j),i}^{(\mu)}$ is simply the value of the $i^{th}$ coefficient in the model $\mu$ linearly interpolated at time $\phi - \rho j$ and deformed by $\alpha$. $W$ represents the size of the sliding window. Figure 9 shows $\pm 20\%$ model deformations by.

The result is composed of $N$ probabilities corresponding to each particle. The filter is now initialized. The stages described below allow to select the most probable states.

The CONDENSATION Algorithm is the following:

1. Weighting

the process is started by normalising the $N$ probabilities computed at time $t-1$ with

$$\pi_{t-1}^{(n)} = \frac{p(z_{t-1}|s_{t-1}^{(n)})}{\sum_{i=1}^{N} p(z_{t-1}|s_{t-1}^{(i)})}$$
<figure><img src="image_11.png" /><figcaption>**Fig. 9** Example of deformations by ±20% in amplitude and in model sampling (curve representing the narrowing of path 1 of class 1)</figcaption></figure>

where $\pi_{t-1}^{(n)}$ represents the weight of each particle at time $t-1$. The cumulative probability $c_{t-1}^{(n)}$ can thus be computed as follows:

$$c_{t-1}^{0} = 0$$

$$c_{t-1}^{(n)} = c_{t-1}^{(n-1)} + \pi_{t-1}^{(n)}$$

## 2. Selection

A state $s_{t-1}$ is selected first by sampling $c_{t-1}$ with a uniform random value $r = [0, 1]$ and identifying the lowest $c_{t-1}^{(n)}$ such as $c_{t-1}^{(n)} > r$ (the value just higher than $r$), as shown in Fig. 10. The most likely states are thus selected most frequently. We can see in Fig. 11 that the state $s_1$ is more likely to be selected than state $s_2$ as $r$ is uniformly selected.

After this selection stage, 10% of new random particles/states are added to avoid getting trapped in local minima and to deal with sudden changes in the input data [64].

## 3. Prediction

When a state has been selected, we can move over to the next stage for a prediction of its parameters at time $t$.

The objective is to try and predict the parameters applying to the new state $s_t^{(n)}$ at time $t$ on the basis of the state selected $s_{t-1}$ with:

$$\mu_t = \mu_{t-1}$$

$$\phi_t = \phi_{t-1} + \rho_{t-1} + \mathcal{N}(\sigma_{\phi})$$

$$\alpha_t = \alpha_{t-1} + \mathcal{N}(\sigma_{\alpha})$$

$$\rho_t = \rho_{t-1} + \mathcal{N}(\sigma_{\rho})$$
<figure><img src="image_12.png" /><figcaption>**Fig. 10** (in [64]) The probability distribution for states is sampled by establishing the cumulated probability distribution and sampling it uniformly. The corresponding state can be obtained by selecting *r* in a uniform distribution on [0, 1]</figcaption></figure>

where $N(σ_*)$ represents a normalized distribution of the uncertainty of prediction. A $φ_t > φ_{max}$ situation means that the end of the model has been reached and the state should be reset. If $α_t$ or $ρ_t$ are out of their respective ranges, new predictions should be made until values are again within the corresponding ranges.

4. Updating

In this part the probability $p(z_t|s_t^{(n)})$ of the state predicted $s_t^{(n)}$ is calculated. If this probability is too low, the predictive process is repeated; should the probability remain low in spite of several trials, a new state will be generated.

After establishing all *N* states, the weighting stage is started again for an iteration at time *t* + 1.

To avoid being blocked in a local minimum and take into account sudden changes in the input data, states obtained by random setting can be incorporated instead of selecting all *N* states.

The Fig. 12 sums up the operation of the algorithm.

<figure><img src="image_13.png" /><figcaption>**Fig. 11** Basic procedure for the selection of the most probable state</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>Fig. 12 Operation of the CONDENSATION algorithm</figcaption></figure>

### 3.1.3 Modification of the Initial Algorithm

Some modifications have been made in the CONDENSATION algorithm to obtain optimal operation.

The first change takes place in the setting step of a given state and concerns the procedure for the selection of the position in the model $\phi$. In [64], the approach is designed to give preference to the lower values. This original method thus considers that models are always started from their beginning. However, our context is such that we have to be able to use any point in the model as a starting point. Therefore the setting of $\phi$ is therefore done in [0, $\phi_{max}$].

The second modification relates to the calculation of likelihood. In [64], formula (2) presents two disadvantages. The first one concerns the output magnitude for this equation as it is located in the [0.24 0.39] interval rather than in the [0, 1] range so that the calculation of likelihood has to be normalized. Moreover, this system is rather time-consuming in terms of calculation. In the present case, the following method is applied for the calculation of likelihood $p(\mathbf{z}_t|s_t^{(n)})$ is

$$p(\mathbf{z}_t|s_t^{(n)}) = \prod_{i=1}^{D} p(Z_{t,i}|s_t^{(n)}),$$

where

$$p(Z_{t,i}|s_t^{(n)}) = \left( 1 - \left( \frac{\sum_{j=0}^{W-1} \left( z_{(t-j),i} - \alpha \times m_{(\phi-\rho j),i}^{(\mu)} \right)^2}{W-1} \right) \right)^A,$$

with $A = 10$. The value of $A$ is given empirically using Matlab. The constant $A$ can be used to improve the results supplied for recognition as they have higher discriminatory power with higher values for probabilities, as shown in Fig. 13 while calculation time is relatively low. The CONDENSATION algorithm is applied afterwards
<figure><img src="image_15.png" /><figcaption>**Fig. 13** Variations of the various power functions ($f(x) = x^A$) and the function given in [64]</figcaption></figure>

for a sorting of paths. A diagram displaying the implementation of the algorithm is presented in Fig. 14.

### 3.1.4 *Outcome of the Sorting Process*

The paths used for the recognition testing process were provided by four different categories, as described in Fig. 15.

A more detailed description is given in [63].

In the first stage, each first path in each class is selected as a class model. There is therefore no modelization phase and we pay attention only to the recognition test which is run as follows:

- the size of window *W* is set;

- the start position is set to windows size *W*;

- the algorithm is reiterated up to $\phi_{max}$.

- the result of recognition (cf. Table 2) is given at various moments of the iteration $t \in [W + 1, W + 5, W + 10, W + 20, W + 30, W + 40, W + 50]$. This percentage corresponds to the numbers of paths that have been properly recognized (classified) among the set of paths.

The first part of Table 2 summarizes the tests carried out for the 23 paths broken down into four classes.
<figure><img src="image_16.png" /><figcaption>**Fig. 14** CONDENSATION algorithm applied to our context</figcaption></figure>

The algorithm has been developed in its entirety with Matlab. The parameters of the filter are as follows: $N = 500$ states, $W = [10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60]$ observations, $\alpha \in [0.7, 1.3]$, $\rho \in [0.7, 1.3]$, 50 new states with each iteration (10%), $\varepsilon = 0.2$, 10 predictions before resetting the state, $\sigma_i = 1$ (no estimate of the standard deviation); the parameters for the uncertainty of prediction are selected as in [64]: $\sigma_{\phi} = 0.5$, $\sigma_{\alpha} = \sigma_{\rho} = 0.1$.

Figure 16a shows the model of the first path type and Fig. 16b the path to be recognized. These two paths were provided by two real tests in the form of two runs in an identical environment. We expect the algorithm to retrieve the current path and the current position of the path in the model. The last $W$ observations can be used to establish the most probable model and also the position in the model and its deformations.

An example of recognition is given in Fig. 16c with a 19% position curve deformation.

We can see that there is some misalignment between the model and the observations in Fig. 16a, b and this is a cause of error in the direct curve matching process whereas those differences are taken into account when applying the CONDENSATION algorithm—as shown in Fig. 16c, d, so that proper recognition is achieved.

Another series of tests provides information about the effectiveness of the algorithm. In the first part of Table 2, calculations were carried out by using the original algorithm found in [64] implemented under Matlab. The average computing time recorded with a Pentium4 processor of 2.4 GHz speed and equipped with 512Mo RAM is 0.9s/path.

The same tests were then carried out with the CONDENSATION algorithm after modification as described above.
<figure><img src="image_17.png" /><figcaption>**Fig. 15** Four classes of real paths</figcaption></figure>

The second part of Table 2 gives profits offered by the modification of the algorithm.

It appeared during the tests that the critical parameter to obtain a good com-
promise between the rate of recognition and reasonable computing time is proper
selection of the width W of the observation window. As described in Table 2, the
error made when recognizing decreases as the number of iterations increases. For
instance, with a window containing 35 or 40 observations, the error is zero up from
20 observations, which corresponds to covering a distance of 2 m.

The reader will notice that the results seems comparable for a window size W
from 35 to 50 and for the time W + 20 or W + 30. The reason is the following: the
<table><caption>**Table 2** Comparing percentages of paths recognized before and after modifying the method applied for the calculation of likelihood</caption><thead><tr><th>Window size W</th><th>10 (%)</th><th>15 (%)</th><th>20 (%)</th><th>25 (%)</th><th>30 (%)</th><th>35 (%)</th><th>40 (%)</th><th>45 (%)</th><th>50 (%)</th><th>55 (%)</th><th>60 (%)</th></tr></thead><tbody><tr><th colspan="13">Time t</th></tr><tr><th colspan="13">Percentages of paths recognized with original version of likelihood computing</th></tr><tr><th>W + 1</th><td>65</td><td>35</td><td>26</td><td>13</td><td>26</td><td>30</td><td>26</td><td>22</td><td>39</td><td>56</td><td>78</td></tr><tr><th>W + 5</th><td>52</td><td>35</td><td>35</td><td>35</td><td>39</td><td>43</td><td>52</td><td>70</td><td>65</td><td>87</td><td>87</td></tr><tr><th>W + 10</th><td>43</td><td>65</td><td>43</td><td>43</td><td>52</td><td>56</td><td>70</td><td>83</td><td>91</td><td>100</td><td>96</td></tr><tr><th>W + 20</th><td>52</td><td>70</td><td>65</td><td>70</td><td>78</td><td>91</td><td>91</td><td>96</td><td>100</td><td>96</td><td>96</td></tr><tr><th>W + 30</th><td>39</td><td>78</td><td>74</td><td>87</td><td>91</td><td>91</td><td>100</td><td>96</td><td>91</td><td>96</td><td>N/A</td></tr><tr><th>W + 40</th><td>35</td><td>65</td><td>65</td><td>74</td><td>78</td><td>87</td><td>83</td><td>96</td><td>N/A</td><td>N/A</td><td>N/A</td></tr><tr><th>W + 50</th><td>52</td><td>65</td><td>70</td><td>87</td><td>70</td><td>78</td><td>N/A</td><td>N/A</td><td>N/A</td><td>N/A</td><td>N/A</td></tr><tr><th colspan="13">Tile t</th></tr><tr><th colspan="13">Percentages of paths recognized with modified version of likelihood computing</th></tr><tr><th>W + 1</th><td>35</td><td>43</td><td>9</td><td>9</td><td>9</td><td>13</td><td>21</td><td>26</td><td>39</td><td>52</td><td>60</td></tr><tr><th>W + 5</th><td>48</td><td>65</td><td>26</td><td>35</td><td>39</td><td>43</td><td>39</td><td>70</td><td>74</td><td>87</td><td>83</td></tr><tr><th>W + 10</th><td>39</td><td>48</td><td>30</td><td>39</td><td>61</td><td>56</td><td>70</td><td>83</td><td>87</td><td>87</td><td>96</td></tr><tr><th>W + 20</th><td>52</td><td>61</td><td>74</td><td>70</td><td>78</td><td>87</td><td>96</td><td>100</td><td>96</td><td>96</td><td>100</td></tr><tr><th>W + 30</th><td>61</td><td>61</td><td>83</td><td>78</td><td>83</td><td>100</td><td>91</td><td>91</td><td>91</td><td>100</td><td>N/A</td></tr><tr><th>W + 40</th><td>83</td><td>78</td><td>83</td><td>83</td><td>83</td><td>83</td><td>83</td><td>91</td><td>N/A</td><td>N/A</td><td>N/A</td></tr><tr><th>W + 50</th><td>74</td><td>65</td><td>83</td><td>87</td><td>83</td><td>83</td><td>N/A</td><td>N/A</td><td>N/A</td><td>N/A</td><td>N/A</td></tr></tbody></table>

algorithm reaches best efficiency according to the windows size and the trajectory differences from the covered path.

## 3.2 Implementing the Path Recognition Systems on VAHM Architecture

The VAHM system is designed as a multi-agent system composed of a common memory surrounded by various agents whose function is to read the sensors, interact with the user or also respond to changes in the environment of the wheelchair (cf. Fig. 17 in the case of the simulation mode). The purpose of the agent in charge of path recognition is to provide assistance to the user while sparing him/her the need to send again commands for direction while moving in a familiar environment. This agent—that we called *path monitoring*—is one among the cognitive agents. When this agent is sure of knowing the position of the wheelchair, the agent replaces the command given by the user by the control recorded in the corresponding path model.

A simulator was developed to replace the real environment while using the agents of the VAHM system. It can be considered similar to an agent because it fulfils the function of the US sensors and electric motors which respectively provide the state of the environment and the command when in operation. This information is then replaced by the simulator agent (cf. Fig. 17) so that we gain independence from the equipment side during the test and adjustment phases.

### 3.2.1 The Path Monitoring Agent

The *path monitoring* agent has access to the shared central memory (cf. Fig. 17). This memory allows to interact with the other agents. It is composed of three components: the agent body (which supports memory access, result backups and observations management), the recognition algorithm and a network of models.
<figure><img src="image_18.png" /><figcaption>**Fig. 16** Recognition test for type 1 paths</figcaption></figure>

Our agent performs a recognition for each sampling operation and saves the results in a table also containing 3,000 elements whose index varies at the same time as the index of observations. It also makes it possible to display curves representing the probability of the dominant state as well as the position of this state in the model, as shown in Fig. 18 (for monitoring use only).

A complete course is modeled by several models in a chain or sequence. For these sequences to be established, the models are set in a network composed of states and transitions, similar to a Markov chain in which each state corresponds to a model and the probability of passing from a state to another is indicated in each transition. However, in this specific case, the transitions also have a small-size model so that the wheelchair can be controlled in these transitional phases. An example of such a model sequence as the user crosses a corridor is represented in the Fig. 19.

Whenever the wheelchair stops, the agent body transmits the results of recognition to the model network. These results are then parsed to detect the successful transitions. Whenever a transition is parsed, its probability increases. This probability
<figure><img src="image_19.png" /><figcaption>Fig. 17 Multi-agent system in simulation mode</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Fig. 18 Views displayed by the path monitoring agent. The *upper part of the diagram* presents the probability of recognition and the position in the model. The *second diagram* represents the observations made by the sensors of the wheelchair. The *third diagram* represents the recognition window of the model. Finally the *drawing* represents the course of the robot</figcaption></figure>
<figure><img src="image_21.png" /><figcaption>**Fig. 19** An intersection with its associated network</figcaption></figure>

corresponds to the number of successful passages through this transition. When looking for the transition with the highest probability, possibly leading to an automatic change in direction, the transition selected will be the transition with the highest counter.

### 3.2.2 The Recognition Algorithm

The recognition algorithm uses the CONDENSATION algorithm described above. It receives the observation vectors supplied by the agent body; it also has access to the model network. When being set, it reads in a setup file a list of the observation vectors to be used when recognizing. This system makes it possible to modify the observation vectors used without calling for a modification of the code. After each recognition, it returns the properties of the dominant state, i.e. the number of models, the position in the model, model deformations and the probability of being in this state. When the probability falls below a specific threshold, the state is reset.

The next part deals with the simulation and experimental results obtained with the VAHM 3 prototype.

## 4 Simulation and Experimental Results with VAHM 3

### 4.1 Simulation of Environments and Path Monitoring

A new agent called “path monitoring” has been developed on the basis of the results supplied by the classification process. It is a component of the multi-agent software piloting the VAHM as a cognitive agent. Its purpose is to determine its own position
within a known environment and help the user by suggesting automatic changes in direction. An automatic change in direction is carried out by replacing the direction given by the user by the direction that has been stored in the path model. The absence of reaction from the user is considered as a validation of the decision made by the agent. This new agent offered by the VAHM system is then submitted to a first test in a simulated environment.

### 4.1.1 Validating the Implementation of the Recognition Algorithm

With a view to validating the implementation of the algorithm, checking the real-time operation of the recognition process and selecting the parameters associated with the CONDENSATION algorithm, the command architecture was used in simulation mode. The test is run in two stages; the first one is dedicated to the creation of a path model and the second one to recognition.

This first path is taken as the model (see Fig. 20) and the recognition test can then be carried out. The test consists in moving in the environment covering a path similar to or different from the model. This important test targets two goals:

- is it possible to follow a model? It is performed by obtaining high probability and linear progression of the position in the model;

- Is it possible to distinguish similar paths? It is performed by obtaining low probability and/or non linear progression of the position in the model. The latter variation confirms that the system has identified its position in the environment.

The results displayed in Fig. 21 show that recognition was properly done in spite of minor differences in the path covered by the wheelchair. This figure presents three runs in the testing environment. The first run (samples from 0 to 300) follows the model with successful recognition evidenced by the high probability level and the linear progression of the position in the model. The second run (samples from 300

<figure><img src="image_22.png" /><figcaption>**Fig. 20** Testing environment and model provided by the first run</figcaption></figure>
<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /><figcaption>**Fig. 21** Results supplied by recognition</figcaption></figure>

to 570) follows the model at the onset but then turns off to the central area of the environment (the first part of this cycle is similar to the model, so the probability of recognition is high). We can locate the place where the wheelchair deviates from the model because of the sharp fall of the probability just after the 400th sample. The third turn in the environment begins at about the 600th sampling and follows the model.

These tests made it possible to adjust the parameters of the CONDENSATION algorithm. The values selected are as follows: $N = 500$ states, $W = 40$ observations, $\alpha \in [0.9, 1.1]$ (i.e. $\pm10\%$ deformation), $\beta \in [0.8, 1.2]$ (i.e. $\pm20\%$ deformation), $\varepsilon = 0.2$, 1 prediction before resetting the state, $\sigma_i = 1$ (no estimation of the standard deviation), $\sigma_{\phi} = 0.5$, $\sigma_{\alpha} = \sigma_{\rho} = 0.1$.
Once the CONDENSATION algorithm has been validated and the current parameters have been set, the procedure for model sequencing and the substitution of the user's command can be carried out.

### 4.1.2 Validating the Recognition

The outputs provided by the *path monitoring* agent evaluate the rate of recognition from the probability of recognition and the linear variation of the position in the model.

The method used to evaluate the rate of recognition is described below. The parameters have been set empirically under Matlab. The items used are:

- the mean value of the last seven samplings for the probability of recognition ($P_{mean}$), provided by formula (3) so as to smoothen out the probability curve and remedy cases of low recognition values.

$$p_{mean} = \frac{\sum_{i=1}^{7} P_i}{7}. \qquad (3)$$

- the error on the progression linearity of the position $\phi$ in the model of the last seven samplings ($L_{\phi}$). This error is calculated as the squared mean value of progression errors with the equation

$$L_{\phi} = \frac{\left( \sum_{i=1}^{7} \phi_i - \phi_{i+1} - \rho_i \right)^2}{7}$$

allowing a calculation of the difference between the positions of recognition $\phi_i$ and $\phi_{i+1}$ from which the increase pitch $\rho$ has been subtracted, thus supplying the progression error in the model. The calculation of the distance between $\phi_i$ and $\phi_{i+1}$ takes into account models used as references to overcome the difficulties involved in changing models.

The recognition is validated when:

- $P_{mean} > 0.98$ and $L_{\phi} < 300$

- $P_{mean} > 0.80$ and $L_{\phi} < 40$

- $P_{mean} > 0.90$ and $L_{\phi} < 100$

- The recognition at the preceding moment is validated and $P_{mean} > 0.70$ and $L_{\phi} < 200$

The last condition for validation creates a hysteresis curve to ensure greater stability against minor changes in the environment and better continuity for the validation process of recognition. These validation values have been fixed empirically.

### 4.1.3 Sequencing Path Models

The environment is stored per piece (model). These models should then be bound together to ensure continuity in the recognition process. To implement the sequencing of models as described above, we used two models connected in the environment of the simulator. These models represent a complete path which requires some actions from the user in standard cases (stopping and moving on again). This test has therefore two functions. The first one is ensuring that the system is able to follow
up changes of models according to a sequence that is known and established in the model network; the second one is meant to make sure that the system can follow up a change in direction.

The direction of the wheelchair can be modified by a substitution of direction commands. The control necessary to follow the path is saved in the model. It is applied when there is a need to recognize the position in the model. The recognition is validated by the method described in Section 4.1.2.

Without this validation phase of recognition, the wheelchair cannot know when changes in direction should be applied. The models used and the path covered are presented in Fig. 22. We can see that the wheelchair changes its direction without any command from the user. The results presented in Fig. 23 include the probability of likelihood, the position in the model and two procedures for the validation of the recognition. We can see that the validation based only on probability is not constant as the paths are not identical, whereas the approach using the probability and the linearity of progression validates the recognition on the whole path.

We can observe that there is no loss of recognition at the time of transition between the models, even though the dominant state is located in alternation at the end part of model 1 and at the beginning of model 2—as described in Fig. 23b—in the vicinity of the 110th sampling. This shows that the models are set in a sequence during the calculation of the distance between two samplings.

These simulations allow us to validate the approach that we propose. However, we still have to carry out real tests to validate this procedure without reservation. The next part deals with these tests.

<figure><img src="image_25.png" /><figcaption>**Fig. 22** Representation of the two models and a path in the environment. The path is covered without entering a direction after starting moving</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>(a) Likelihood probability evolution</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>(b) Evolution of the position in the models. Model 1 is recognized in the 50-100 range and model 2 in the 110-200 range.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>(c) Evolution of results provided by recognition using exclusively the probability of likelihood.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>(d) Evolution of the validation of recognition using the probability and progression linearity.</figcaption></figure>

<caption>**Fig. 23** Probability of likelihood, position in the model and validation of recognition during sequencing of two models. The direction is changed only when the validation of the recognition is 1. When validation is 0, it means that recognition has failed as there was a sufficient number of observations. When validation is -1, recognition cannot be performed due an insufficient number of observations (t < W). The difference between Fig. 23c, d proves that a calculation is needed to validate results</caption>
## 4.2 Real Environment Testing

### 4.2.1 Introduction

Tests have been carried out in two stages:

- In the first step, path recognition was implemented by using the joystick to operate the wheelchair (and not the interface whose scanning process was linked to an On/Off switch). This type of test made it possible to check and adjust the parameters for real-time recognition as compared to the tests made in simulation.

- In the second step, path recognition was implemented after linking the operating device to the On/Off switch. The purpose of this test is to validate the capacity of the system to memorise a path, recognize it and then apply the changes in direction contained in the model.

The environment used for the testing procedure is the research center itself. These tests consist in various movements made in the corridors. The procedure is quite simple and has no variations:

- a first passage is made in the above mentioned environment in order to model it,

- then the path recognition process is applied to all subsequent passages in the same environment.

The Fig. 24 displays the map of the lab where the tests were carried out.

### 4.2.2 Using the Operating Joystick

In the first step of the testing, the joystick of the standard wheelchair is used instead of an On/Off switch operating device. The operating program of the vehicle is started by activating the path recognition agent. Several paths are covered while introducing changes in the size of the window and the discriminatory capacity of the likelihood probability.

<figure><img src="image_30.png" /><figcaption>**Fig. 24** Environment used for real-time testing</figcaption></figure>
These tests show that elements such as the legs of a table have an impact on the process as they cause a peak to appear in a very specific place among the values provided by the sensors measuring the distances.

Another gap between the model and the real-time observations appears and, as a consequence, the peaks cause major differences to appear when the likelihood is being calculated. A way to circumvent the problem is to implement some smoothing of the values measured and therefore of the model itself during the modelling stage. The Fig. 25 displays the values submitted to smoothing and those left untouched in the same area as recorded during various passages. It also displays the mean square values of the gap between two identical “narrowing” curves in relation to the phase difference. These values are calculated on the basis of the data concerning the front and rear narrowings, with and without smoothing process. For that purpose, we have applied a linear interpolation between the values (moving average linear filter on five elements) similar to what the CONDENSATION algorithm does. We can observe in this figure that the offset is much wider without smoothing as with the smoothing process. This points out to the fact that the latter process can improve the operation of the system.

We can notice that the recognition process is improved by using a moving average linear filter on five elements. The modifications applied to the other parameters do not cause any notable improvement.

An offline analysis of results shows that, as long as the CONDENSATION algorithm is applied, the renewal of such states (particles) with low probability values is not very important. These states propagate in spite of the mean value. The threshold for renewal is therefore modified by being raised from its initial value $\epsilon = 0.2$ to $\epsilon = 0.5$ to facilitate a renewal of states.

This improves the results supplied by the recognition process. The new parameters for the CONDENSATION algorithm then became:

- size of the windows for observations: $W = 60$

- number of states: $N = 800$

- variation in magnitude: $\alpha = [0.9 \ 1.1]$

- variation in the sampling: $\beta = [0.9 \ 1.1]$

- threshold for the probability likelihood before the renewal of the state: $\epsilon = 0.5$ and computing a prediction before the renewal.

- using 10% of the new states.

- power used to discriminate the likelihood: $A = 16$

- uncertainty of prediction: $\delta_{\rho} = 0.02$, $\delta_{\phi} = 0.05$ et $\delta_{\alpha} = 0.02$

The results of the recognition are described in Fig. 26. This figure presents the three models acquired on the occasion of a first run in the environment and then the results provided by two consecutive runs in the same environment. The figure shows that the VAHM wheelchair succeeded in finding its way on the basis of the three models acquired. We can observe that the connection between model 3 and model 1 was not modeled and, as a consequence, the recognition process fails when having reached the transition point between the two models. However, the wheelchair is localized again when the window $W$ is placed completely within an area belonging to model 1.
<figure><img src="image_31.png" /><figcaption>**Fig. 25** Smoothing values. These *figures* display the effect of the smoothing process applied to the values in one specific part of the path</figcaption></figure>

On these two figures we can note the efficiency of the validation recognition process.
During these two cycles, the wheelchair is continuously localized.

The next section shows how the recognition process is implemented through the
On/Off switch interface.
<figure><img src="image_32.png" /><figcaption>**Fig. 26** Results of the real-time tests with controls provided by the joystick. This *figure* presents two paths covered in the environment after the modelling phase. The results show that the agent makes it possible to localize the wheelchair on an acquired path</figcaption></figure>

### 4.2.3 Applying the On/Off Switch Interface

The basic goal of this work is to integrate the use of the On/Off switch interface into the recognition process of the path. The test consists in validating the capacity of the system to acquire a specific path, recognize it and apply the directional changes contained in the model without any intervention by the user. Figure 27 shows the results provided when using the system in the same real environment. In this case, we use only one model based on the three models presented in the paragraph above with directional changes included in the model. The wheelchair covers the path three times:

- the model is established during the first run;

- the next two runs should be able to reproduce the path covered without requiring an intervention by the user to operate a change in direction.

The Fig. 27 shows a movement operated automatically—i.e. without any action by the user—by reproducing the model acquired during the first run.

It can be observed that some localization spots cannot be established. These failures are to be assigned to faulty measurements (imperfect technology of the US sensors, wheels slipping on the floor). These failures are also caused by problems related to the algorithm selecting behavioural agents. A part of the loss in localization are due to the environment configuration too, for instance in the case of a very small
<figure><img src="image_33.png" /><figcaption>**Fig. 27** Results provided by the real environment tests when operated by On/Off switch interface.
This figure presents the model, the path covered and the results of recognition</figcaption></figure>

narrowing. However the wheelchair is generally well localized and assists the user in
the navigation.

5 Discussion

The purpose of our approach is to offer the highest possible level of assistance when the user determines the path to be covered by using an intelligent control system. This monitoring agent is designed to recognize a path that has been covered earlier and then repeat the movement along this path without any user's intervention. This new function is based on tools for localization and path recognition. It uses a topological localization method and CONDENSATION algorithm as matching algorithm.
The modifications made to the initial CONDENSATION algorithm as well as the method of the validation of recognition and the filtering of the data from sensors optimize the recognition and the path following.

This new control architecture (“quasi”-autonomous mode with path monitoring agent) allows to navigate using an On/Off switch with a minimum of intervention by the user.

As a consequence, the smart wheelchair and the user will closely cooperate to cover the path in optimal conditions and the operational mode is called “symbiotic”.

But some difficulties remain. The adjustment of the CONDENSATION parameters represents the key of a good path recognition and especially parameter *W*. If the window is too small, there is a risk of confusion between parts of ways having similar zones and; if it is too large; additional computing time will be necessary.

The choice of the first path as the model is not optimal but allows to make the system usable as of the first navigations. A system of path aggregation could be studied at the later stage in order to tune the initial model.

Another problem relates to the management of a loss of localization. This loss can be temporary (mobile obstacles) or permanent (addition, removal of a fixed obstacle). In the first case, there is no consequence if it occurs in the following phase without change in direction. If not, the user will have to enter a new direction control. In the second case, a way to deal with the problem is to consider a new path.

To determine the right path, we use the history of the path on a fixed-time sliding window; this is a way to avoid errors when detecting the “landmarks” in the environment. The matching method by particle filtering makes it possible to identify the adequate path model in spite of the variations imposed on navigation by the user.

Currently, creating the path and entering data into the database are done manually. Future work will focus on designing a method to integrate new path in database.

After completing this work, our method could be compared to a FastSLAM [69] method. In particular the “Trajectory-Oriented SLAM” [70] in which the “landmarks” are not information in the form of scattered spots, but rather a part of the path.

## 6 Conclusion

The purpose of this contribution was primarily to present the VAHM3 prototype and the project for path recognition aiming to facilitate navigation. The procedure is based on a development of the curve matching process. It appears that the issue of magnitude and position curve deformations emerging with a direct curve matching process can be solved by using particle filtering as the CONDENSATION algorithm offers the possibility of taking deformations into account. The preliminary results provided by path classification allow for the development of a new agent for the command architecture. This agent was successfully implemented in a simulated environment. A method for path sequencing based on recognition is also presented in this contribution, with the possibility for the *path monitoring* agent to steer the wheelchair without intervention by the user. Finally, This method has been tested in a real environment to tune and validate fully the considered approach.
References

1. Pruski, A., Ennaji, M., Morère, Y.: Vahm: a user adapted intelligent wheelchair. In: IEEE Conference on Control Application, Glasgow, Scotland, UK (2002)

2. Simpson, R.: Smart wheelchairs: a literature review. J. Rehabil. Res. Dev. 42(4), 423–436 (2005)

3. Pruski, A., Ennaji, M., Morère, Y.: VAHM: un fauteuil intelligent adapté à l'utilisateur. In: Compte-rendu de la Conférences Handicap 2002, Paris: Handicap 2002, 13–14 Juin 2002

4. Bourhis, G., Horn, O., Habert, O., Pruski, A.: The VAHM project: autonomous vehicle for people with motor disabilities. IEEE Robot. Autom. Mag. 7(1), 21–28 (2001) (Special Issue on 'Research on Autonomous Robotics Wheelchair in Europe')

5. Bell, D., Borenstein, J., Levine, S., Koren, Y., Jaros, L.: An assistive navigation system for wheelchair based upon mobile robot obstacle avoidance. In: IEEE Robotics and Automation, San Diego (1994)

6. Röfer, T.: Routemark-based navigation of a wheelchair. In: Proceedings of the 3rd ECPD International Conference on Advanced Robotics, Intelligent Automation and Active Systems, pp. 333–338 (1997)

7. Boy, E., Teo, C., Burdet, E.: Collaborative wheelchair assistant. In: IEEE/RSJ International Conference on Robotics and Intelligent Systems (IROS), Lausanne, Suisse, vol. 30, pp. 1511–1516 (2002)

8. Del Castillo Del Riego, G.: Autonomous, vision-based, pivoting wheelchair with obstacle detection capability. Ph.D. dissertation, University of Notre Dame (2004)

9. Schilling, K., Roth, H., Lieb, R., Stützle, H.: Sensors to improve the safety of wheelchair user. In: Improving the quality of life for the European citizens, vol. 4, pp. 331–335. IOS, Fairfax (1998)

10. Adachi, Y., Kuno, Y., Shimada, N., Shirai, Y.: Intelligent wheelchair using visual information on human faces. In: Proceedings of the 1998 IEEE/RSJ International Conference on Intelligent Robot and Systems (IROS), vol. 13, pp. 354–359. IEEE, Victoria, BC, Canada (1998)

11. Prassler, E., Scholz, J., Fiorini, P.: A robotic wheelchair roaming in a railway station. In: Proc. Int. Conf. Field and Service Robotics, Pittsburgh, pp. 31–36 (1999)

12. Pires, G., Aradjo, R., Nunes, U., De Almeida, A.: Robchair—a powered wheelchair using a behaviour-based navigation. In: 5th International Workshop on Advanced Motion Control (ACM'98-Coimba), vol. 29, pp. 536–541. IEEE, Coimbra (1998)

13. Patel, S., Jung, S., Ostrowski, J., Rao, R., Taylor, C.: Sensor bseed door navigation for a non-holomic vehicle. In: Proceedings of the 2002 IEEE International Conference on Robotics and Automation (ICRA), pp. 3081–3086. IEEE, Washington, DC (2002)

14. Mallet, P., Schöner, G.: WAD project where attractor dynamics aids wheelchair navigation. In: Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 690–695. IEEE, Lausanne (2002)

15. Matsumoto, Y., Ino, T., Ogsawara, T.: Development of Intelligent wheelchair system with face and gaze based interface. In: Proceedings of the 10th IEEE International Workshop on Robot and Human Interactive Communication 2001, pp. 262–267. IEEE, Bordeaux, France (2001)

16. Sahnoun, M., Fattouh, A., Bourhis, G.: Assisted control for powered wheelchair with a force feedback joystick. In: Alain Pruski, H.K. (ed.) Assistive Technology: From Virtuality to Reality. Association for the Advancement of Assistive Technology in Europe (AAATE 2005), pp. 601–605. IOS, Fairfax (2005)

17. Pruski, A., Habert, O., Ennaji, M.: Symbiotic man-machine architecture for a smart wheelchair control. In: 6th Conf. for the Advancement of Assistive Technology, AAATE 2001, Ljubljana, Slovenia, pp. 216–221 (2001)

18. Connell, J., Viola, P.: Cooperative control of a semi-autonomous mobile robot. In: IEEE International Conference on Robotics and Automation, vol. 2, pp. 1118–1121, 13–18 May 1990

19. Bourhis, G., Pino, P.: Mobile robotic and mobility assistance for people with motor impairments: rational justification of the VAHM project. IEEE Trans. Rehabil. Eng. 4(1), 7–12 (1996)

20. Levine, S., Bell, D., Jaros, A., Simpsons, R., Koren, Y., Borenstein, J.: The NavChair assistive wheelchair navigation system. IEEE Trans. Rehabil. Eng. 7(4), 443–451 (1999)

21. Borgolte, V., Hoyer, H., Buhler, C., Heck, C., Hoelper, R.: Architectural concept of semi-autonomous wheelchair. J. Intell. Robot. Syst. 22, 233–253 (1998)

22. Beattie, P.: SENARIO: SENsor Aided intelligent wheelchaiR navigatiOn. In: IEE Colloquium on New Developments in Electric Vehicles for Disabled Persons, London, UK, vol. 17, pp. 2/1–2/4 (1995)
23. Simpson, R., LoPresti, E., Hayashi, S., Nourbakshs, I., Miller, D.: The smart wheelchair component system. J. Rehabil. Res. Dev. 41(3B), 429–442 (2004)

24. Simpson, R., LoPresti, E., Hayashi, S., Guo, S., Frisch, R., Martin, A., Ammer, W., Ding, D., Cooper, R.: The smart power assistance module for manual wheelchairs. In: Proceedings Of CWUAAT ’04, vol. 24, pp. 51–54. Cambridge, UK (2004)

25. Simpson, R., Poirot, D., Baxter, F.: The Hephaestus smart wheelchair system. IEEE Trans. Neural Syst. Rehabil. Eng. 10(2), 122–125 (2002)

26. Miller, D., Slack, M.: Increasing access with a low-cost robotic wheelchair. In: Proceedings of the IEEE/RSJ/GI International Conference on Intelligent Robots and Systems ’94. Advanced Robotic Systems and the Real World, vol. 3, pp. 1663–1667. Munich, Allemagne (1994)

27. Mazo, M.: An integral system for assisted mobility [automated wheelchair]. IEEE Robot. Autom. Mag. 8(1), 46–56 (2001)

28. Vlassis, N., Sgouros, N., Efthivoulidis, G., Papakonstantinou, G., Tsanakas, P.: Global path planning for autonomous qualitative navigation. In: Proc. 8th IEEE Int. Conf. on Tools with AI (1996)

29. Balcells, A., Gonzalez, J.: TetraNauta: a wheelchair controller for user with very severe mobility restrictions. In: Proceedings of the CSUN (California State University, Northridge)—Technology and Persons with Disabilities Conference, Los Angeles, US (1998)

30. Gomi, T., Griffith, A.: Developing intelligent wheelchairs for the handicapped, vol. 1458. Springer, New York (1998)

31. Brooks, R.: How to build complete creatures rather than isolated cognitive simulators. Ser. Architectures for Intelligence, pp. 225–239. Lawrence Erlbaum Associates, Hillsdale (1991)

32. Simpson, R.C., Levine, S.: Automatic adaptation in the NavChair assistive wheelchair navigation system. In: IEEE Trans. Rehabil. Eng. 7(4), 452–463 (1999)

33. Berthoz, A.: Parietal and hippocampal contribution to topokinetic and topographic memory. Philos. Trans. R. Soc. Lond. B 352, 1437–1448 (1997)

34. Habert, O., Pruski, A.: Raisonnement à partir de cas pour le contrôle d'un fauteuil électrique. JESA 34(6–7), 765–782 (2000)

35. Filliat, D., Meyer, J.-A.: Map-based navigation in mobile robots: I. A review of localization strategies. Cogn. Syst. Res. 4(4), 243–282 (2003). doi:10.1016/S1389-0417(03)00008-1

36. Meyer, J.-A., Filliat, D.: Map-based navigation in mobile robots: II. a review of map-learning and path-planning strategies. Cogn. Syst. Res. 4(4), 283–317 (2003). doi:10.1016/S1389-0417(03)00007-X

37. Crowley, J.L.: World modeling and position estimation for a mobile robot using ultrasonic ranging. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 674–680 (1989). citeseer.ist.psu.edu/crowley89world.html

38. Arras, K., Tomaris, N., Jensen, B., Siegwart, R.: Multisensor on-the-fly localization: precision and reliability for applications. Robot. Auton. Syst. 34, 131–143 (2001). http://citeseer.ist.psu.edu/arras01multisensor.html

39. Marhic, B., Mouaddib, E.M., Fofi, D., Brassart, E.: Localisation absolue par capteur omnidirectionnel SYCLOP. Trait. Signal 17(3-NS), 195–206 (2000). http://hdl.handle.net/2042/2142

40. Chong, K.S., Kleeman, L.: Sensor based map building for a mobile robot. In: Proceeding of the 1997 IEEE International Conference on Robotics and Automation, Albuquerque, New Mexico, pp. 1700–1705 (1997)

41. Oriolo, G., Ulivi, G., Vendittelli, M.: Fuzzy maps: a new tool for mobile robot perception and planning. J. Robot. Syst. 14(3), 179–197 (1997). citeseer.ist.psu.edu/oriolo97fuzzy.html

42. Cho, D.W.: Certainty grid representation for robot navigation by a Bayesian method. Robotica 8, 159–165 (1990)

43. Dellaert, F., Burgar, W., Fox, D., Thrun, S.: Using the condensation algorithm for robust, vision-based mobile robot localization. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’99) (1999)

44. Thrun, S., Bucken, A.: Integrating grid-based and topological maps for mobile robot navigation. In: AAAI/IAAI, vol. 2, pp. 944–950 (1996). citeseer.ist.psu.edu/thrun96integrating.html

45. Pruski, A.: Robotique mobile, planification de trajectoire. Hermes, Paris

46. Thrun, S., Fox, D., Burgard, W., Dellaert, F.: Robust Monte Carlo localisation for mobile robots. Artif. Intell. 128, 99–141 (2001)

47. Aycard, O., Charpillet, F., Fohr, D., Mari, J.-F.: Place learning and recognition using hidden Markov models. In: Proceedings if the IEEE/IROS, pp. 1741–1746 (1997)
48. Borges, G., Aldon, M.-J.: Optimal mobile robot pose estimation using geometrical maps. IEEE Trans. Robot. Autom. 18(1), 87–94 (2002)

49. Frese, U., Larsson, P., Duckett, T.: A multigrid algorithm for simultaneous localization and mapping. IEEE Trans. Robot. 21(2), 1–12 (2005). http://www.informatik.uni-bremen.de/~ufrese/slammlr_e.html

50. Kreutner, M., Horn, O.: Co-operation between ultrasound and monocular vision for the localization of a mobile robot. In: Proceedings of the Computing Engineering in Systems Applications, Ecole Centrale, Université de Lille, France (2003)

51. Leonard, J., Durrant-whyte, F.: Mobile robot localization by tracking geometric beacons. IEEE Trans. Robot. Autom. 7(3), 376–382 (1991)

52. Piasecki, M.: Global localization for mobile robots by multiple hypothesis tracking. Robot. Auton. Syst. 16(1), 93–104 (1995)

53. Araujo Broges, G.: Cartographie de l'environnement et localisation robuste pour la navigation de robots mobiles. Spécialité: Génie Informatique, automatique et traitement du signal, Université de Montpellier II, vol. 27, pp. 1299–1304 (2002)

54. Leonard, J.J., Tardòs, J.D.: Mobile navigation and mapping. In: IEEE International Conference on Robotics and Automation: Workshop on Mobile Robot Navigation and Mapping (2000)

55. Cox, J.: Blanche—an experiment in guidance and navigation of an autonomous robot vehicle. IEEE Trans. Robot. Autom. 7, 193–204 (1991)

56. Kalman, R.: A New approach to linear filtering and prediction problems. Trans. ASME J. Basic Eng. 82(Series D), 35–45 (1960)

57. Rabiner, L., Juang, B.: An introduction to hidden Markov models. IEEE ASSP Mag. 3, 4–16 (1986)

58. Fox, D., Burgard, W., Thrun, S.: Markov localization for mobile robots in dynamic environments. J. Artif. Intell. Res. 11, 391–427 (1999)

59. Shatkay, H., Kaelbling, L.: Learning geometrically-constrained hidden Markov models for robot navigation: bridging the topological–geometrical gap. J. Artif. Intell. Res. 16, 167–207 (2002)

60. Isard, M., Blake, A.: Contour tracking by stochastic propagation of conditional density. In: Eur. Conf. on Computer VisionECCV (1), pp. 343–356 (1996)

61. Jensfelt, P., Wijk, O., Austin, D., Andersson, M.: Experiments on augmenting Condensation for mobile robot localization. In: Proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, CA, pp. 2518–2524 (2000)

62. Kass, M., Witkins, A., Terzopoulos, D.: Snakes: active contour models. Int. J. Comput. Vis. 1(4), 321–331 (1988)

63. Grasse, R., Morère, Y., Pruski, A.: Aided navigation for disabled people: route recognition with augmented HMMs. In: 8th Conf. for the Advancement of Assistive Technology, AAATE 2005, Lille (2005)

64. Black, M.J., Jepson, A.D.: A probabilistic framework for matching temporal trajectories : condensation-based recognition of gesture and expressions. In: Burkhardt, H., Neumann, B. (eds.) European Conf. on Computer Vision, ECCV-98, pp. 909–924. Springer, Freiburg (1998)

65. Handschin, J.E.: Monte Carlo techniques for prediction and filtering of non-linear stochastic processes. In: Automatica, vol. 6, pp. 555–563 (1970)

66. Gordon, N.J., Salmond, D.J., Smith, A.F.M.: Novel approach to nonlinear/non-Gaussian Bayesian state estimation. In: IEEE Proceedings, F. 140(2), pp. 107–113 (1993)

67. Kitagawa, G.: Monte Carlo filter and smoother for non-Gaussian non-linear state space models. J. Comput. Graph. Stat. 5(1):1–25 (1996)

68. Isard, M., Blake, A.: Condensation-conditional density propagation for visual tracking. Int. J. Comput. Vis. 29(1):5–28 (1998)

69. Durrant Whyte, H., Bailey, T.: Simultaneous localization and mapping: part 1. IEEE Robot. Autom. Mag. 13(2), 99–108 (2006)

70. Durrant Whyte, H., Bailey, T.: Simultaneous localization and mapping: part 2. IEEE Robot. Autom. Mag. 13, 108–117 (2006)