M.Sc Thesis

M.Sc StudentGuy Eran
SubjectNavigation Algorithm for Plan Spider Robot in Smooth
Intermittent-Linear Tunnel
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Elon Rimon


The objective of this research is to develop an algorithm for navigating a spider robot with four limbs (each limb has four links) in a planar piecewise linear tunnel. The algorithm continuously stabilizes the robot’s position by pushing its limbs against the tunnel walls, while avoiding collision between the robot and the tunnel and between the robot’s limbs. The research contribution of this thesis is the combination of three research areas (multi-limb walking mechanisms, autonomous navigation, and stability of grasped objects) into a navigation algorithm for a spider robot.

The research includes investigation of the robot’s environment from a grasping point of view, and determination of the points on the tunnel walls where the robot can push its limbs against the walls. A study of the robot’s environment from feasibility point of view while taking into account the robot’s physical dimensions. A proposal for a naive connectivity graph in which vertices represent feasible three-limb postures, and shuffling legs along the tunnel walls are represented by the edges. A proposal for a search algorithm in the naive connectivity graph. Last, we propose a heuristic algorithm that converts the path from the foothold-space as it represented in the naive connectivity graph to the robot’s joint-space, by finding for each posture along the path a continuous joints trajectory in the tunnel physical space. We propose a way to update the naïve connectivity graph when the conversion fails by disconnecting edges and removing vertices on the fly.

The work involves development of a C++ program that implements the proposed algorithm, and demonstration of the results in a three-dimensional graphical environment.