Team:ETH Zurich/Path Planning

Project

• Description
• Applied Design
• Team Members
• Attributions
• Sponsoring
• Notebook
• Safety
• Downloads

Wet Lab

• Tar Receptor Evolution
• Approach A
• Approach B
• Experiments
• InterLab

Hardware

• Hardware Overview
• Microscope
• Mechanics
• Syringe Pump
• Microfluidic Chip
• Bubbling

Software

• Software Overview
• Motility Readout
• Luminescence Algorithm
• Robot Controls
• Path Planning

Model

• Model Overview
• Integrated Models
• Motility Model
• Split Luciferase Model
• Diffusion Model
• Bubbling Model
• Holographic Imaging Model
• Screening Assay Model
• Model Parameters

Human Practices

• Human Practices
• Education & Engagement

Achievements

• Results
• Parts Overview
• Demonstrate
• Collaborations

Content

Introduction Table

Home

A.R.O.M.A.

Project

• Description
• Applied Design
• Team Members
• Attributions
• Sponsoring
• Notebook
• Safety
• Downloads

Wet Lab

• Tar Receptor Evolution
• Approach A
• Approach B
• Experiments
• InterLab

Hardware

• Hardware Overview
• Microscope
• Mechanics
• Syringe Pump
• Microfluidic Chip
• Bubbling

Software

• Software Overview
• Motility Readout
• Luminescence Algorithm
• Robot Controls
• Path Planning

Model

• Model Overview
• Integrated Models
• Motility Model
• Split Luciferase Model
• Diffusion Model
• Bubbling Model
• Screening Assay Model
• Holographic Imaging Model

Human Practices

• Human Practices
• Education & Engagement

Achievements

• Results
• Parts Overview
• Demonstrate
• Collaborations

Path
Planning.

Scroll

Introduction

The path planning algorithm determines AROMA’s path through the field. Therefore, it is a crucial algorithm as it has to ensure that the source is found as quickly and efficiently as possible.

Initial Algorithm

Inspired by the actual movement of E.coli, we implemented two path planning algorithms, namely the biased random walk and gradient descend [REF 1]. The idea of the biased random walk is that at each point in time one performs a random tumble and walks into this new direction. If the concentration of the target molecule actually increased along this direction, one continues to walk for another percentage of the distance (the bias) into this direction, if not, one simply stays. The gradient descend works in a similar way. However, a random move is only taken when the concentration decreased along the walking direction, otherwise the walking direction is unchanged.

The animations below illustrate the behaviour of the previously described algorithms in a single source field, assuming perfect measurements at each point in time. The assumption of the perfect measurements is needed in order to solely evaluate those algorithms without any external influences.

Biased random walk

Normal gradient descent

Path of our initial algorithms towards the source.

As you can see, in this given setup, both of the algorithms find the source in around 70 steps. Usually, the greedy behaviour of the gradient descent algorithm (i.e. to keep walking in the same direction as long as concentration increases) results in better performance, especially when the starting point is further away from the source. As it is also visible in the animations, due to the random moves which are included in the algorithms, it sometimes can happen that they diverge further away from the source. Another weakness of these algorithms is that an external user has to define a threshold intensity that determines when the algorithm terminates. In a real-world search scenario, setting such a threshold is hardly possible and makes the two algorithms quite inflexible.

Improving the Gradient Descent Algorithm

Due to the better performance of the gradient descent algorithm in comparison with the biased random walk, we decide to use it as the basis for our improvements. The first modification faced the behaviour when a lower concentration is measured. We decided to modify the algorithm in a way that it returns to the previous spot whenever a lower concentration is sensed. Thus, the robot will never increase the distance to the source. Next, to prevent the algorithm from returning to an individual point too often, we set a threshold on how many times the algorithm checks other directions at a given step size. If the concentration along all those directions decreases, the algorithm halves the step size since then it is already very close to the source. Therefore the algorithm can simply be terminated whenever the stepsize falls below a user defined threshold. The elegance of this approach is that the termination of the algorithm is independent of prior knowledge about the source. This improved version clearly outperforms the initial gradient descend and biased random walk algorithm as shown in the figure below. In this scenario e.g. it found the source after only 28 moves.

Path of our improved Gradient Descent Algorithm

Further Improvement due to the Integrated Model

The modeling of our overall system (the integrated model) revealed difficulties when actually starting too far away from the source. Therefore we decided to implement a dual search strategy. This means that in the beginning another path planning algorithm systematically scams through the field until a measurable concentration is detected. As soon as this is the case, the local gradient descent algorithm is activated which then locates the source.

Results

Our improved gradient descent algorithm outperforms the standard gradient descent and biased random walk. In an idealized scenario it always efficiently finds the source without having to specify any property of the source. Therefore, it is perfectly suited for our given scenario of having to locate mines in a minefield as it is shown on the modeling page.

REFERENCES

1. [1] Bacterium-inspired Robots for Environmental Monitoring, by Amit Dhariwal et al. Proceedings of the 2004 IEEE

Sponsors

Contact Us