Move blocks to create a designed surface

Question

I am new to machine learning and AI, so forgive me if this is obvious. I was talking with a friend on how to solve this problem, and neither of us could figure out how to do it.

Say I have a grid area of 100x100 blocks, and I want a robot to build a horizontal 100x100 grid, and 3 blocks high. I am given a random, but known starting surface, always 100x100 but the height of the random surface can vary from 1 to 5 blocks. I have an extra reserve of blocks i can pick up, so dont have to worry about running out. The robot can move in any direction, even diagonally at some cost penalty. The robot can obviously move a 4 high block to fill in a 2 high, so each is at the design height of 3. This sounds like a reinforcement learning problem, but would any one be able to explain more detail how I would do this, to a) minimize the amount of moves, and b) to get to the design surface.

Answer 1

This task can be done with keyframe based animation. The starting surface is keyframe 0, the goal-surface is keyframe 10. A RRT planner can bring the system from frame 0 to frame 10. This is done with brute-force-search in the problem space. To fasten up the search it makes sense, to define helper keyframes between them (guided policy search). Such in-between-keyframes can be extracted from previous manual demonstrations. The overall system consists of two parts:

1. an algorithm which searches for actions to bring keyframe a to keyframe b
2. and an algorithm who is searching in previous demonstrations for getting the in-between-keyframes

In the literature such problems are discussed in the domain of PDDL. The task-planner works with PDDL specifications, while the Motion planner uses Rapidly-exploring random trees. Logic-Geometric Programming: An Optimization-Based Approach to Combined Task and Motion Planning

Answer 2

Essentially, you could do something like have the robot randomly make moves (moving around and moving blocks) for some number of steps. Repeat this a bunch of times, and record the 'score' at the end (how close you are to a perfect result grid). Tell your algorithm to act more like the best scoring runs (Optimize a loss function), and start it over. Hopefully, you'll eventually get a robot that manages the task - the whole 'optimal path' thing will come around by the computer telling itself to learn from the lowest cost examples.

Remember, you're letting the machine do the hard thinking about the best way to do this or that. All you have to do is give it the framework to learn.