Biorobotics Laboratory BioRob

Path Planning with the humanoid robot iCub

Panteleimon Zotos

Semester project, autumn 2008

Supervisor: Sarah Degallier
Professor: Auke Jan Ijspeert

Abstract

The goal of this project was to implement a path planning algorithm on the humanoid robot iCub. The project consisted of the following parts:

 

• Study of different path planning algorithms used to find an optimal path from a start to an end position in an environment with obstacles.
• Selection of one algorithm to implement. We have chosen to use the Ant Colony Optimization method to solve the path planning problem. Ant Colony Optimization (ACO), which was introduced by Marco Dorigo in his PhD. thesis, is a class of algorithms, whose main idea is inspired by the behavior of real ants. ACO was initially applied to the travelling salesman problem, and to the quadratic assignment problem. Since then, a lot of extended versions have been developed, which have been applied to different combination optimization problems. The biological inspiration for ACO comes from the fact that many ant species deposit on the ground a substance, called pheromone, when they are walking to and from food source. Other ants tend to follow the path, where the concentration of pheromone is higher, the most effective path. While several ants are able to select among different routes from their nest to the food source, the first ants that will return from the food source will be these that followed the shortest path, so that path will have the highest concentration in pheromone and the ants will choose this path at their next traverses to the food source.
• The next part was the implementation of the ACO algorithm for our path planning problem. We placed the path planning problem at a grid of squares. There is a square of the grid considered as start position and another one considered as end position. The agents (ants) must find a path from the start to the end position. Each agent has a current position in the grid, can move by one square and has to make a decision about its new position. This decision is based on the amount of the pheromone in the grid square and on the value of a heuristic function. When implementing the ACO algorithm several design parameters need to be defined. Several simulation were performed in different environments in order to explore the characteristics of the algorithm and to take some decisions over the selection of the following parameters.
  • number of ants (agents)
  • number of generations (iterations)
  • alpha, the pheromone factor
  • beta, the heuristic factor
  The pheromone factor, alpha, and the heuristic factor, beta, indicate in which degree the amount of pheromone or the heuristic function value, respectively, in uences the selection of the next position.
• The iCub is an infant-like robot. It has the size of a 2 years-old child and the ability to crawl. Information on iCub's crawilng can be found here. We used a simulation of this robot at the ODE-based software Webots in order to perform some tests of the implementation of the ACO algorithm. The steering ability of the iCub robot was not previously modeled, but that was essential for this project as long as the robot has to walk among obstacles in order to reach a goal position starting from an initial position.
• At the final part, we have integrated the ACO algorithm in a simulation of the robot iCub in Webots. We have constructed a simulation world represented by a chesslike board of 8x8 squares surrounded by a wall and with 5 square obstacles inside. The start position of the robot is the lower left square and the end position is the upper right square. The goal of the simulation is the robot to crawl from the start position to the end position through the result path of the ACO algorithm without colliding with an obstacle or the wall, which is the boundary of the board. Another feature of the simulation is the ability to change the obstacles' positions dynamically. When the robot detects a change in the obstacles' positions, it stops and recomputes a plan with start position its current position and the same end position and it continues its crawling from this position to the end.

 

Final report and presentation

Final report and presentation:

final_report_Pantelis_Zotos.pdf
Path Planning with the humanoid robot iCub2.pptx
Path_Planning_with_the_humanoid_robot_iCub_presentation.pdf

Videos

1. The iCub is steering.
2. The iCub finds a path from the start position(down left square) to the end position(upper right square).
3. The iCub changes its path "on-line" after the obstacles' positions have changed dynamically.

Turn.mpeg
crawling_ACO2.mpeg
crawling_ACO_dyn_changed_env1.mpeg

Source Code C++

Source Code of the application in Webots.

Crawling_iCub_PantelisZotos_SP.tar.gz