I'm building a 4 legged robot (quadruped) with 3 Degrees of freedom per leg. The goal of my project is to make this robot able to learn how to walk. What learning algorithms will I need to implement for it to work?
I'm using an Arduino Uno for the microcontroller.
There are a number of things to consider for your project. Since you are asking for the learning algorithms, I asume your hardware is or will be up and running. When getting your robot to learn, you should differentiate between on-line and off-line learning. Further, there is on-system and off-sytem learning, which can be combined with the previous category. Since your system only has a micro-controller attached to it, your method of choice would be off-system. You learn (be it on-line or off-line) on your connected PC, but not on the system. The system will just execute your current learned policy.
All gait movements have some sort of cyclic nature, and can generally be described as functions that provide an angular value over time for each of the joints. The trick is to parametrize these functions that you come out with as little parameters as possible. Then you perform optimization on these functions. In order to do that you need to know what to optimize for.
Most learning approaches will require some sort of reward function, so effectively some feedback to the algorithm to tell it how well it does perform (e.g. maximise distance travelled/energy required). The algorithm will then want to see the reward for a given set of parameters (single episode). Depending on the complexity of your problem, the number of episodes might be quite large. This is where the destinction between on-line and off-line learning comes in. In off-line learning you use a simulation to perform the learning and then later move it to the system. In on-line learning you learn directly on the system. This is generally more difficult, since you will have to spend a lot of time performing evaluations for the learning algorithm.
There is not a specific set of learning algorithms that you will need to implement. Genetic algorithms (GA), neural networks (GA), and reinforcement learning (RL) have all successfully been applied to the problem of gait generation. I can also conceive of ways to use unsupervised learning methods to approach this problem but I can't say for certain whether they would work. Even if they would I'm inclined to think RL is the better approach.
Dr. Hod Lipson talks about using GAs in his TED video entitled Hod Lipson builds "self-aware" robots.
NNs have often been used. A few examples include:
I don't know whether RL has been appplied to quadrapeds but there are a number of succesful applications to hexapods.
Beware that these lists are by no means comprehensive.
GA and NN would be relatively simple to implement. RL on the other is a more principled way to approached the problem. In all cases you will need more processing power than the Uno offers to actually perform the learning. If you intended to do offline learning then the Uno may work after the learning phase.
Here's a paper that seems relevant: Policy Gradient Reinforcement Learning for Fast Quadrupedal Locomotion.
Abstract:
A simplified method for learning would be to make the robot into one random position and then another and tweak the second position until it moves forward. Using this position as a start do the process again n times and then you will have n positions to move through that make the robot move forward.
I have built a lot of walking robots, in my experience if you can't get it to walk by programming a gait you are not going to get it to learn because you don't know what it is supposed to do and the search space is too large. Using an Arduino you may be able to get it to fine tune some movements iff you can define good movements.
