The recently designed Semi-circular Mecanum Double Wheel (SMDW) is a type of wheel that provides vehicles with enhanced omnidirectional motion on rough terrain and obstacle overcoming capabilities. This thesis proposes a new maneuvering methodology that allows robots with SMDWs to overcome obstacles in diverse approach configurations allowing robots to select their position and orientation according to their environment. The techniques developed prior to this work considered only the obstacle overcoming in a lateral motion, significantly restricting the holonomic abilities of the device. The methodology proposed in this thesis considers the generation of cubic spline trajectories that connect the initial position and orientation of the robot with the target configurations and the SMDWs states necessary to perform the obstacle overcoming task. For the generation of those trajectories a Particle Swarm Optimization (PSO) search technique explores the navigation space of the robot in order to find suitable control point locations to achieve the required robot’s position and wheels states. The obtained trajectories were tested using a novel physical simulator that incorporates the effects of the peripheral rollers in order to evaluate the performance over a wide range of obstacles and terrain configurations. The new methodology provides an effective tool to enable robots using SMDWs to move and navigate more effectively in complex outdoor and indoor rough terrains.