Self learning robotics algoritm: feedback needed

Question

I'm working on a robotics project and I've got this idea for a self learning algorithm. I'm looking for some feedback on this, and specifically on whether this is a more common way of doing things.

I simply want to store a lot of numerical log data of previous actions the robot took and the results it got. I then want to let it search through the DB multiple times per second so that the robot can make decisions based on that and thus learn from it's actions (like humans do).

So I constantly log a lot of data. One simple log record could be for example:

• speed: 5.43
• altitude: 35.23
• wind_speed: 6.19
• direction: 27
• current position: [12, -20]
• desired position: [18, -25]
• steering decision: 23
• success: 12

The desired_position are coordinates on a 2 dimensional matrix and the success is how close it came to the desired position within 10 seconds (so the lower the better).

I then have a certain situation for which I want to find a comparable experience in the database. So let's say my current situation is this:

• speed: 5.13
• altitude: 35.98
• wind_speed: 7.54
• direction: 24
• current position: [14, -22]
• desired_position: [17, -22]

As you can see it doesn't have a steering decision or a success yet, because it still has to make a steering decision and only after taking that action and seeing the result the success rate can be calculated.

So I want to search for the record "closest" to my current situation within certain boundaries, and which has the best (lowest) success rate. So for example, the boundaries could be that the direction cannot be more than 10% difference, and the heading cannot be more than 15% difference. So I first make a selection based on that. I'm left with A LOT of records. I then calculate for every field in every record the percentage difference, and accumulate those per record so that I get some sort of “closeness factor”. Once that's done I combine the closeness with the success, order by that number, and take the top record to base my decision on for the action to be taken. I take the steering decision of that record and randomly change it to something which is within a certain change percentage range. I do this because people also experiment, you try something new every time. And as the system becomes better at steering the robot (success factors get better) I also reduce the randomization change percentage. This is because as people get better, they also know that they are closer to the objective and they don't need to experiment as much any more.

So to steer my robot I will run the following process as often as possible (I will try to run it 20 times per second) and use this system to steer my robot.

So my questions are;

1. Do you think that this can work?
2. Is this kind of thing used more often?
3. Does anybody know a database which would make it possible to query based on a dynamically calculated factor (the closeness factor)?

Answer 1

What you are describing seems a lot like reinforcement learning, and yes, it works well for this sort of scenario. It is a popular enough approach that you should be able to find starter code in whatever language you prefer. This paper looks like it could be interesting for you.

Basic set-up

Typically the way the problem is set up is that we want to find a function called a policy which maps state/action pairs to rewards. For your problem, the state is all of the information besides steering_decision and success, your action is steering_decision and your reward is success. The goal is to find a policy that gives the best reward, where "best" could be the highest mean, lowest risk, etc. depending on the setting.

Importance of exploration

The randomization idea you propose is crucial, known as "exploration" in the reinforcement learning community. If you want to go really deep into how to best trade-off exploration and exploitation, statisticians have been studying the "Multi-armed bandit" problem for a few decades. If you're ok with exploration that is "good enough", then a linearly decreasing exploration factor will work fine.

Making it fast

As you note the amount of data you have to sift through makes it difficult to compute this policy quickly, so what typically happens is that we run a training phase off line (either based on historical data or simulated data) in order to find a good policy. Then we use this policy (without changing it) on-line. If you store the policy as a look-up table (for example by hashing your state), then the on-line computation will be very fast. Off-line training will work well as long as your environment is fairly static, or you are able to capture the time-variation in your state (for example by including weather or time-of-day information).

Comparing "similar" states

The last piece of the puzzle is to formalize the "closeness" concept, where you decide what information is relevant. There are quite a few ways to do this, but I would recommend looking into a Gaussian process approach (see this on-line book), where you define a kernel function, which takes in two state vectors $x_1$ and $x_2$, and returns a number which represents how similar the states are. The reason to use this approach is that you can use your historical data to fit a statistical model for the reward distribution given a state $x$, even if you haven't seen the state before.