Below is the problem
A robot has a board (like chess board) with some gold coins (50 coins on board of 10 X 10) in random squares. The red box is Robot, 0 means empty square, 1 means gold coin in square and there is walls surrounding the board.
Robot can only see the current square he is in and four adjacent squares ( limited memory), so based on surrounding he can take following actions
The objective is to after studying the world he is in robot must
The robot cannot go over all the squares one by one and pick up where there is a gold coin. Someone would think I would write nested for loop and I am done.
We want you to come with what action robot will perform in a given surrounding.The robot has limited memory and the actions need to be defined for a robot. This implies:
Red square is where Robot is, now you decide to go left in this situation.You get scenario as below.
Now if you decide that in this scenario robot move right, you get scenario below which is same as first scenario and you are in deadlock!!
If you wonder if this a complex problem worth discussing here. If we try to solve it iteratively, there are 7.074 e+169 combinations to find a solution from.
So we will use genetic algorithm to solve the problem. Genetic algorithms are typically used for approximation/optimization problems.
In my next post I will describe the solution to the problem.
Genetic Algorithm - Part 2 - The Solution
A robot has a board (like chess board) with some gold coins (50 coins on board of 10 X 10) in random squares. The red box is Robot, 0 means empty square, 1 means gold coin in square and there is walls surrounding the board.
Robot can only see the current square he is in and four adjacent squares ( limited memory), so based on surrounding he can take following actions
- Go in any of four directions
- Bend and pick coin in the square he is in.
The objective is to after studying the world he is in robot must
- Come with a strategy to pick all the coins without scoring any negative points and that too in minimum moves i.e. if you score all 500 points in 100 moves its great.
- Get all possible combination of strategy.
The robot cannot go over all the squares one by one and pick up where there is a gold coin. Someone would think I would write nested for loop and I am done.
We want you to come with what action robot will perform in a given surrounding.The robot has limited memory and the actions need to be defined for a robot. This implies:
- At a certain position in a grid the robot is in, it has no idea which direction or from where it came to that position.
- Given a surrounding, the robot will always take the same action.
| Scenario 1 |
| Scenario 2 |
| Scenario 1 again |
Now try to find a solution iteratively or by working out a solution on paper to realize the complexity of the problem.
If you wonder if this a complex problem worth discussing here. If we try to solve it iteratively, there are 7.074 e+169 combinations to find a solution from.
So we will use genetic algorithm to solve the problem. Genetic algorithms are typically used for approximation/optimization problems.
In my next post I will describe the solution to the problem.
Genetic Algorithm - Part 2 - The Solution
No comments:
Post a Comment