Autonomous navigation vehicle algorithms

Introduction

A great resource is F1Tenth, https://f1tenth.org/

See also https://mushr.io/tutorials/tuning/ and https://racecar.mit.edu/platform

Safety Concerns

• Real-life problems
• Sensors
• Failure modes

Automatic breaking AEB

Automatic emergency breaking AEB

• Detect objects
• Find range, velocity, heading
• Determine critical objects. Time to collision TTC.

• False positive: Nobody will buy a system with these
• False negative: kills innocent people

Stop the vehicle before colliding.

Sensors

• Camera
  • Structured light 3d scanner camera
  • Stereo camera
  • Monocular camera
• Radar
• Ultrasonic
• Lidar
  • Planar lidar (Hokuyo 30LX)
  • 3d lidar
  • solid state lidar (Velodyne velarray)
• Odometry

Reactive Methods

Follow the Gap

Follow the gap

Furthest distance?

• Misreading
• Too small gap

Gap: Series of at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} consecutive hits that pass some distance threshold Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} .

• Works good for holonomic robots. Also good if only sparse obstacles.
• No car's dimensions, no safety.
• What is the threshold radius Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} ?

Avoid the nearest obstacle every timestep.

1. Find the nearest point: add a safety bubble with radius Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_b} around it.
2. Set all distance points inside the safety bubble to zero (0).
3. Find the max gaps of consecutive nonzeros
4. Choose the best max gap of all. Naive: The furthest max-gap.

Consider changing the speed.

References

• https://panxiaofan.github.io/myf1tenth/2021/01/24/lab4.html
• F1/10 Autonomous Racing - Montreal Grand Prix Winning Team https://www.youtube.com/watch?v=ctTJHueaTcY&t=368s
• F1Tenth Autonomous Racing Cars(Lab 4) https://www.youtube.com/watch?v=4HOsg2SRabw

Bug algorithms

Original bug algorithm published around 1986.

Assume local knowledge of the environment and a global goal.

TangentBug

• Distance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(x, \theta)} function, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in\mathbb R^2} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta\in[0,2\pi]} .

Saturated distance function for range Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_R(x, \theta) = \begin{cases} \rho(x,\theta), \text{ if } \rho(x,\theta)<R\\ \infty, \text{ otherwise} \end{cases} }

Problems

• Requires knowledge about the distance to the goal; beacon setup or similar

References

• https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg_howie.pdf
• https://cs.gmu.edu/~plaku/teaching/LecRoboBugAlgorithms.pdf

Artificial Potential Fields

Gradient descent

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix} \text{If } &\nabla U(q_i) \neq 0: \\ &q_{i+1} = q_i - \alpha_i \nabla U(q_i) \end{matrix} }

Problems

• Local minima

References

• https://www.cs.cmu.edu/~motionplanning/lecture/Chap4-Potential-Field_howie.pdf
• https://www.coursera.org/learn/robotics-motion-planning

Labs from F1tenth

1. Wall following https://f1tenth-coursekit.readthedocs.io/en/latest/assignments/labs/lab3.html#doc-lab3

More references

• Quaternions: Steven M. LaValle - Virtual reality lectures https://www.youtube.com/playlist?list=PL_ezWOhnpakMojiJGm-YiCz5zr4GpuLG_
• Names of the coordinates: https://www.ros.org/reps/rep-0105.html
• Ziegler-Nichols method for PID https://en.wikipedia.org/wiki/Ziegler%E2%80%93Nichols_method
• Harmonic potential field path planning for high speed vehicles https://folk.ntnu.no/skoge/prost/proceedings/acc08/data/papers/0383.pdf
• Robotic Motion Planning: Potential Functions https://www.cs.cmu.edu/~motionplanning/lecture/Chap4-Potential-Field_howie.pdf