Modified GSO algorithm

Odor localization can be divided into three tasks:

1. Search for the presence of a chemical

2. Search for the source guided by chemical and other sensing; and

3. Verification of the identified source (odor source recognition/ declaration).

Odor source localization algorithms generally focus on solving only the second task. In this section, we modify the GSO algorithm to solve the full odor source localization problem. The glowworms are modified to have three different modes of behavior, namely the chemotactic, anemotactic and spiraling modes. The chemotactic mode and the anemotactic mode helps in solving the second stage of localization task. The spiralling mode is used by the glowworms to capture the plume thus addressing the first task. It has been seen in simulations that once the glowworms reach the source location they remain in the vicinity of the source. This property can be used for odor source declaration.

Chemotactic mode

The GSO algorithm is utilized here by the glowworms in the chemotactic mode, in order to move closer to the source. In turbulent flows, the peak concentration value within a patch and the frequency of encountering a patch increases as the glowworm gets closer to the source. However, the instantaneous concentration value might mislead the movement decision of the glowworms. Figure 1 shows the variation in concentration measured by glowworms placed directly downwind to the source. The glowworms measure concentration once every second. It can be seen that even for locations separated by three meters, the instantaneous concentration value can be higher at locations farther from the source, while the maximum concentration encountered in an interval is well separated. Hence, we define the luciferin value to be the maximum gas concentration value encountered by a glowworm in the last N_mem seconds in its trajectory. We assume a value of 1 ppm (10^-6) for the gas sensor threshold. Hence, gas concentration measurements below this value are taken to be zero.

Figure 1: Concentration measured by glowworms placed directly downwind to the source at different times.

The various steps of the GSO algorithm are shown in the psuedo code, where l_i(t) represents the luciferin level associated with Glowworm i at time t, C(x_i(t)) represents the concentration value measured at Glowworm i's location at time t, x_i(t) is the location of Glowworm i at time t, N_i(t) is the neighborhood of Glowworm i at time t, d_i,j(t) represents the euclidian distance between Glowworms i and j at time t, r_i ^d(t) represents the variable local-decision range associated with Glowworm i at time t, s(> 0) is the step-size, w is the wind direction, r_s represents communication range, the Glowworm i selects to move toward a Glowworm j in N_i(t) with probability p_j(t), n_t represents the desired number of neighbors, and B is a parameter to control the number of neighbors.

Glowworms update their luciferin value after every step. Each glowworm defines its set of neighbors, N_i(t) to be the set of glowworms within a distance of r_i ^d(t) from it and having a higher luciferin value. The dynamic decision domain radius, r_i ^d(t), is useful while localizing multiple sources simultaneously. Each glowworm then probabilistically selects a neighbor and moves toward it. This probability p_j(t) depends on the difference in the luciferin value between the glowworm and its neighbor. Thus, neighbors with high luciferin value will have higher probability of selection. After selecting a neighbor to move toward, the glowworm takes a step toward that neighbor. In the absence of a neighbor, the glowworm switches its behavioral mode either to anemotactic mode, if it has a non-zero luciferin value, or to the spiraling mode in case of zero luciferin. In the original GSO algorithm, the luciferin value update contained information about the glowworm's earlier luciferin value with a temporal decay term associated with it. The idea was to retain information from earlier measurements made by the glowworm. While this works well in case of a stable time-invariant environment, the odor profiles are subject to rapidly varying odor concentrations which is likely to make past information unreliable. This is the reason why we do not use this term in the modified GSO algorithm.

Anemotactic mode

A glowworm enters the anemotactic mode when it does not have any neighbors to move toward but has a non-zero luciferin value. A glowworm in this mode is within the gas plume but does not have a neighbor, that is, it does not have another glowworm within its local decision domain, which has a higher luciferin value than itself. The anemotactic mode is the exploratory mode, where glowworms move upwind searching for the source. The glowworm with the highest luciferin value will have no neighbors, hence it switches to the anemotactic mode and moves upwind. A glowworm in this mode takes a step in the upwind direction, when the measured concentration is above a threshold. This behavior prevents a glowworm from leaving the plume and proceeding upwind away from the source. In case the concentration measured at its current position is below the threshold value, the glowworm stays at its current position.

Spiraling mode

A glowworm enters the spiraling mode when is it completely lost, that is, it has no neighbor to move toward nor it is within the plume so that it could move upwind and get to the source. The spiral motion serves as a heuristic to explore the field in order to find a neighbor or to capture the plume. A glowworm switches to spiraling mode once its luciferin value becomes zero, that is, if the glowworm has measured zero concentration for the last N_mem seconds. Square spiraling is used for ease in robotic implementation. During spiraling, the glowworm takes w steps along a straight line, where w is defined as the spiraling width. After which it performs a 90± turn and moves w steps followed by another 90± turn and movement by 2w steps and so on. The length of the spiral is incremented by w steps after every 2 turns.

The mode switching behavior explained above is encapsulated in figure below. The figure is seen to be a fully connected graph. The conditions leading to a mode transition are also mentioned. A glowworm selects one of the three modes which best suits its environment.

The video below shows the behavior of glowworm using the modified GSO algorithm to locate odor sources in a turbulent environment. In this video the blue dots represent the glowworms and the black patch represents the odor source location. It can be clearly seen that the glowworms using the concentration measurements are able to converge at the odor source location.