Navigation of a ground vehicle towards target without map

Question

I have the following setup:

1. RC car chassis which can turn, go back and forward; both the turn rate and the acceleration can be controlled smoothly
2. Raspberry Pi 3
3. Two cameras so that depth map can be calculated on the fly for obstacle avoidance
4. Several microphones so that direction of the voice can be determined
5. Intertial measurement unit to keep heading at the direction of the voice
6. Several infrared distance sensors

What I want to acompilish is a robot that will drive towards me when called. Voice recognition, structure from motion and handling the IMU are not a problem for me because I've done it before. What I find really problematic is how do I actively avoid obstacles, while trying to follow the voice? I assume that I can call the robot multiple times - i.e. when it gets confused. The robot will stop when a face is recognized from one of the cameras, therefore the distance to target is initially unknown. In theory I could try to create a 3d point cloud using structure from motion and determine the robot's location within the pre-built map and use it for navigation, however as far as I know, the determination of robot location within the map is a costly and uncertain computation (especially when its initial position is unknown).

What I would like to learn is - are there some algorithms that allow the robot to stick to given heading while avoiding obstacles, but without a map? I would be very grateful for scientific papers, blog posts or simply algorithm names if there are any avalible.

I recently read about bug algorithms - especially dist bug. This sounds like most promising solution for me so far.

Answer 1

I know you said without maps but bear with me :).

Would something like the A* algorithm principle, but with a unknown map in which you add obstacles work for you ?

You could start with an empty map and use A* to go to the target. Each time you encounter an obstacle you had it to the empty map and recalculate A*. Using you IMU you can get odometry so building that simple map should be feasible. And by starting with an empty map you don't "need" that expensive localization initialization since you know where you start.

---

Another strategy I can think of is that of simple organisms. Just go toward the (light) sound in a straight line and if you encounter an obstacle just use a "wall follower" behavior, always trying to get closer to the sound, and pray it was the right direction. Simple but effective.

---

As you've pointed in the comment another interesting direction is to copy insect behaviors. You can look at the work done by this lab on desert ant navigation. I haven't read this paper but I saw a presentation of it and it sounded quite interesting.