Robotic’s motion planing

Solution to the Robot’s Navigation problem
Name
Course
Tutor
University
Date
City

Abstract
In the field of robotics, there are a couple of question which ought to be answered in the process of developing efficient and effective robots. For example in a physical world, how is it possible for a robot to achieve motion deciding the turns and twists to make to achieve a particular task in the physical world? Initially, there were insufficient capabilities of motion planning in the industrial robotic programming system. However, this field has grown to space exploration to intervention in hazardous environments by robots. These put into consideration makes the navigation problem become among the necessary components of robotic autonomy in such real-world contexts. Also, it is also a fundamental issue in simulation software of robots as it aids the designer of the cells to determine the path which is collision-free as the robots perform specific tasks. It is thus valuable research which has been carried out in this paper to learn algorithms which can give a solution to the navigation problem of robots with the help of a mobile robot simulator (MobotSim).

Algorithms to the Robot’s Navigation problem
Introduction
The robots are intelligent, and their autonomy is the basis for which they intelligence is measured. There is a need for the robot to have the ability to plan its motion autonomously about the environment it is. Motion planning is also referred to as the pianos mover problem or the navigation problem.

In the robotic field, it is the process of breaking down the desired movements which a robot ought to achieve into well-defined discrete motions which satisfy the constraints of action besides optimizing certain aspects of the change. A good example is the navigation of a mobile robot inside a building to say a distant point. This task should be accomplished smoothly without the robot hitting walls or falling off stairs.
In this paper, a couple of algorithms are discussed with which the motion of the robot is efficiently achieved. With the help of a motion planning algorithm which takes the description of specific tasks the robot should perform as input and output the required turning commands and speeds, the problem is solvable. This kind of algorithm can address robots application within a more significant number of joints such as industrial manipulators among other complex tasks. The motion planning should put into consideration specific constraints such as a vehicle that drives one way and other uncertainties such as an imperfect model of the environment or the robot itself.
There are several robotic application of motion planning which includes automation, autonomy and the design of robots in computer-aided design software. A fundamental navigation problem is the production of a continuous robotic motion that has the capability of connecting a starting point S to the goal G. this movement should be achieved avoiding collision with obstacles. The geometry of the robot and the barriers are represented in 2 dimensions while the motion is described as a path (Van, et. al., 2012, 1260).
A representation of all the possible configuration which can be achieved is referred to as the configuration space C. A configuration, on the other hand, represent the pose of the robot. If the robot is zero-sided, implying it has a single point, and it is translating in a two dimension workspace, the configuration can be represented with two parameters such as X and Y. A two-dimensional robot has the capability of turning and rotating. Despite the workspace being still 2D, the configuration has a representation with three parameters such as x, y, and theta. Finally, three-dimensional shaped robots require six settings. The first three are responsible for the rotation while the remaining two are for rotation. The figure below is an excellent example of a workspace or a configuration space.

Fig 1: A configuration space
Sometimes in literature, configuration space is regarded to as an approach to motion planning which is an incorrect view. However, it is a tool a tool which formulates precisely problems of motion planning. This configuration space concept makes the study of the aspect of motion planning a fashion which is unified. This approach facilitates the comparison and presentation of different approaches in planning which in literature are separately considered. Additionally, the methods description proceed incrementally when considering a primary navigation problem together with its extension.
What the process begins by first is taking the primary problem as the first target. In this study, we look at the major approaches to the computational concept of motion planning which is exposed in details after which they are extended in addition to describing new ones. Below is an example of a motion to goal algorithm code we are to look.
068580Sub Main
Dim difference As Single
SetMobotPosition(0, 15, 15, 90)’ Mobot start position
SetTimeStep 0.1′ simulation time step
startx = GetMobotX(0)’ x-start position of robot
starty = GetMobotY(0)’ y-start position of robot
goalx = GetMarkX(0)’ x-goal position of robot
goaly = GetMarkY(0)’ y-goal position of robot
‘ slope = (starty – goaly) / (startx – goalx)’ slope of straight line between start and goal
‘ n = goaly – goalx * slope’ y-axis crossing line between start and goal
‘Do
SetMobotColor(0,QBColor(13))’motion-to-goal colour (magenta)
Do’Motion to goal behavior
rot=RotationalDiff(0, goalx, goaly)’calculate difference between heading angle and “goal” angleSetSteering(0,0.1,3*rot)’mobot turns into the direction of rot (amplified by factor 3)
StepForward ‘ Dynamics simulation progresses one time step
robotx=GetMobotX(0)’ get current mobot position (x and y)
roboty=GetMobotY(0)
dist = Sqr((robotx-goalx)^2 + (roboty-goaly)^2)’ distance between current position and goal
s5 = MeasureRange(0,5,0) ‘ Measure distance to obstacle ahead (sensor 5)
Loop Until Abs(s5) < 0.7 Or dist < 0.1 ‘continue Motion to goal until obstacle ahead detected
SetMobotColor(0,QBColor(3))’ motion-to-goal colour (green)
‘Loop Until dist < 0.1
End Sub
00Sub Main
Dim difference As Single
SetMobotPosition(0, 15, 15, 90)’ Mobot start position
SetTimeStep 0.1′ simulation time step
startx = GetMobotX(0)’ x-start position of robot
starty = GetMobotY(0)’ y-start position of robot
goalx = GetMarkX(0)’ x-goal position of robot
goaly = GetMarkY(0)’ y-goal position of robot
‘ slope = (starty – goaly) / (startx – goalx)’ slope of straight line between start and goal
‘ n = goaly – goalx * slope’ y-axis crossing line between start and goal
‘Do
SetMobotColor(0,QBColor(13))’motion-to-goal colour (magenta)
Do’Motion to goal behavior
rot=RotationalDiff(0, goalx, goaly)’calculate difference between heading angle and “goal” angleSetSteering(0,0.1,3*rot)’mobot turns into the direction of rot (amplified by factor 3)
StepForward ‘ Dynamics simulation progresses one time step
robotx=GetMobotX(0)’ get current mobot position (x and y)
roboty=GetMobotY(0)
dist = Sqr((robotx-goalx)^2 + (roboty-goaly)^2)’ distance between current position and goal
s5 = MeasureRange(0,5,0) ‘ Measure distance to obstacle ahead (sensor 5)
Loop Until Abs(s5) < 0.7 Or dist < 0.1 ‘continue Motion to goal until obstacle ahead detected
SetMobotColor(0,QBColor(3))’ motion-to-goal colour (green)
‘Loop Until dist < 0.1
End Sub

Throughout the paper, we look into a primary navigation problem which is planning a collision-free path in which a rigid object, robot for this mater, translates amongst objects which are static. A mobile robot simulator is used to help in the study of the various algorithms of navigation. Using this simulator, it is possible to study the motion of a differential drives mobile robot smoothly. There are realistic drive patterns which are modeled by the simulator in addition to the collision with obstacles as shown in the figure below.

Fig 2: Mobile robot simulator
From a practical perspective, there are ultrasonic sensors which are mounted all over the body of the robot. The sensor is meant to detect obstacles in the path where it provides non-contact measurement of the distance between barriers precisely. With the help of the simulator discussed earlier, we create a program whose aim is to navigate a mobile robot in an environment which is filled with disorderly obstacles. The result of this laboratory experiment gives an apparent familiarity of the functioning of the mobile robot simulator understanding the behavior of different artificial intelligence based algorithms of navigation.
Motion planning algorithms
The control and planning of robotic motion require excellent interdisciplinary. Back in the late sixties is when researchers in robotic movement can be tracked when there was the development of robots which were computer controlled. Despite the early research, effects have been realized more recently in the eighties. There are some variables which are considered in the description of the configuration or position of a robot. They entail the joints of the robots, for example, the arms when the variables represent articulated robots. From the definitions, the motion of a robot is considered as the path in the configuration space which the robot follows.
A path like the one mentioned earlier ought to remain in the configuration of the workspace where there is no collision experienced between the obstacles and the robot which is so-called free space. The problem of motion planning is thus developing an algorithm to determine such a path via space which is free in an efficient way. The fundamental question in the robotics field is to obtain an algorithm which can convert the task of high specification level from human into a low-level description of movements.
About a classic version of a navigation problem, which is often referred to as the pianos movers’ problem, we can define it as follows: having a robot system, let it have k degrees of freedom. Additionally, it is free to move within a three or two-dimensional domain v. the dimensional domain is bounded by obstacles. The robotic system is conversant with the geometry of the obstacles. Having the given parameters, the navigation problem for beta is thus given the beginning and the system’s final placements. This is done to determine the possibility of achieving a motion which is continuous right from the initial placement to the final one. During this motion, beta ought to avoid obstacles with the known obstacles, and if it achieves the objective, there is need to plan for such a motion. When looking at this simple formulation of the problem, many issues are ignored, and the only interest is a geometric aspect of the motion. Among the issues ignored are speed, acceleration incompleteness or uncertainty in the geometric data and the strategies of control for execution of the motion among others (Tang, et al., 2012, 20). The primary step and issue in any particular navigation problem formulation are:
Computation of configuration
Representation of the object
Motion planning approaches
Search methods
Local optimization of the motion
Right from the initial piano mover’s problem which is discussed earlier, there have been evolutions of motion planning where need have arisen to address a significant number of different variations of the same problem. This has allowed its application in areas which include the animation of digital characters to automatic verification of layouts in factories, surgical planning, mapping of uncontrolled environments, drug design, navigation of changing settings and assembly sequencing among others. These new applications have brought further considerations which need to be addressed in the design of navigation problem algorithms.
Mobile robotics have steered research to non-holonomic systems. Non-holonomic motion path planning shows the way in which geometric algorithms can be combined with control techniques with the aim of accounting for the non-holonomic constraints which are evident in most of the mobile robots. Mathematical machinery is employed to bring an understanding of the geometry of the non-holonomic system. Great emphasis is required on non-holonomic metrics and the different interests involved in evaluating the combinational complexity of motion planning which is non-holonomic.
The algorithms for deterministic and complete motion planning is exceptionally time-consuming when there is an increase in the dimensions of the configuration space. This problematic approach which is complicated can be addressed by alternative methods which relax the constraint of completeness for the sake of questionable completeness and possible efficiency.
Methods and Materials
There have been considerable amounts of research which has been carried out in the robotics’ field of the different motion planning approaches. This discipline has been in existence since its launch in the mid-sixties. However, it was not until the work of Wesley and Lozano in nineteen seventy-nine which was on spatial planning that the motion planning field drew the attention of many researchers (Latombe, 2012). Currently, there have been developed methods which are variations of a few general approaches which includes:
Bug Algorithms
Roadmap
Cell Decomposition
Potential Fields
Sampling-based motion planning
Kalman filtering
Mathematical programming and Heuristic Approaches
The listed above methods are not mutually exclusive necessarily. A combination of these algorithms is often used in the development of motion planners. These methods are discussed in this paper, and the most efficient one is identified.
There are two significant problems which are raised by path planning: the first one is responsible for addressing the existence of a right path which is collision free, and it is commonly referred to as the decision problem. The second one is meant to send the computation of the track and is hence called the computation problem. The experiments carried out show that the decision problem is always solved for any system which is controllable over smalltime. It is addressed irrespective of the existence of an approximate algorithm which exists to explain the entire problem. The solution which is exact is only responsible for dealing with the unique class small time controllable systems.
Bug Algorithm
This algorithm assumes only local knowledge of the environment and has a global goal to achieve. The bug behavior is simple and they ought to either follow a wall, be it right or left, or move in a straight line towards the goal. The algorithm begins by first identifying the direction of the goal. The robot can measure the distance d (x, y), between the two-point x, starting point, and y, the purpose, as they are visually illustrated in the figure below.

Fig 3: starting and ending point illustration
With a simple bug algorithm planner, we can represent difficult, interesting issues as well. The bug algorithm is the most straightforward and earliest planner which sensor based on having a certain guarantee. The algorithm assumes that the robot is appointed which is operating inside a plane and it has a contact sensor or in other words, a zero ranger sensor meant to detect obstacles. Assuming the robot has a non-zero or finite range sensor, the algorithm is a derivative which can use the information from the sensor to find shorter paths to the goal.
By the help of the simulation software, some program can be written to represent the algorithm to ensure it is tested. The solution begins by declaring the start position of the robot. The location gave regarding the x and y-axis. There are instructions which follow along meant to direct the robot to the required goal. Below is an example code a bug like an algorithm which has been implemented in the simulation software.
right5715Sub Main
‘————– BUG – LIKE ALGORITHM
SetTimeStep 0.01′ simulation time step
SetMobotPosition(0, 2, 2, -90)’ Mobot start position
startx = GetMobotX(0)’ x-start position of robot
starty = GetMobotY(0)’ y-start position of robot
goalx = startx’ x-goal position of robot
goaly = starty’ y-goal position of robot
SetMobotPosition(0, 8, 8, -90)’ Mobot start position
Do ‘ —————— OVERALL LOOP ——————-
‘———————- MOTION TO GOAL BEHAVIOUR —————–
SetMobotColor(0,QBColor(13))’ motion-to-goal colour (magenta)
Do’——– Motion to goal behaviour
rot=RotationalDiff(0, goalx, goaly)’ calculate difference between heading angle and “goal” angle
SetSteering(0,.5,2*rot)’ mobot turns into the direction of rot (amplified by a factor)
‘ SetSteering(Mobot number, forward speed, turning angle)
StepForward ‘ Dynamics simulation progresses one time step
robotx=GetMobotX(0)’ get current mobot position (x and y)
roboty=GetMobotY(0)
dist = Sqr((robotx-goalx)^2 + (roboty-goaly)^2)’ distance between current position and goal
sensor5 = MeasureRange(0,5,0) ‘ Measure distance to obstacle ahead (sensor 5)
Loop Until (dist < 0.1 Or Abs(sensor5) < 0.5)
‘——– continue Motion to goal until goal reached or obstacle hit
‘ ———————-Boundary Following —————-
SetMobotColor(0,QBColor(4))’ boundary following colour (brown)
D0 = .5′ set desired distance to the wall
gain = 30′ set gain for propotional (P) controller
‘ SetSteering(0,0,90)’ mobot turns into the direction of rot (amplified by a factor)
‘ SetSteering(Mobot number, forward speed, turning angle)
Do’ ——– Boundary Following Loop ———
sensor3 = MeasureRange(0,3,0) ‘Read sensor 3 (right)
delta = D0 – sensor3’ deviation from desired distance
SetWheelSpeed(0,20-delta*gain,20+delta*gain)
‘ Actuation: set the speeds of the robot wheels proportional to delta
StepForward ‘ Dynamics simulation progresses one-time step
rot2=RotationalDiff(0, goals, goals)’ calculate difference between heading angle and “goal” angle
‘Debug.Print rot2
Loop Until (rot2 >=90) ‘ —— End of boundary following Loop ——
Loop Until (dist < 0.1)
End Sub
00Sub Main
‘————– BUG – LIKE ALGORITHM
SetTimeStep 0.01′ simulation time step
SetMobotPosition(0, 2, 2, -90)’ Mobot start position
startx = GetMobotX(0)’ x-start position of robot
starty = GetMobotY(0)’ y-start position of robot
goalx = startx’ x-goal position of robot
goaly = starty’ y-goal position of robot
SetMobotPosition(0, 8, 8, -90)’ Mobot start position
Do ‘ —————— OVERALL LOOP ——————-
‘———————- MOTION TO GOAL BEHAVIOUR —————–
SetMobotColor(0,QBColor(13))’ motion-to-goal colour (magenta)
Do’——– Motion to goal behaviourrot=RotationalDiff(0, goalx, goaly)’ calculate difference between heading angle and “goal” angle
SetSteering(0,.5,2*rot)’ mobot turns into the direction of rot (amplified by a factor)
‘ SetSteering(Mobot number, forward speed, turning angle)
StepForward ‘ Dynamics simulation progresses one time step
robotx=GetMobotX(0)’ get current mobot position (x and y)
roboty=GetMobotY(0)
dist = Sqr((robotx-goalx)^2 + (roboty-goaly)^2)’ distance between current position and goal
sensor5 = MeasureRange(0,5,0) ‘ Measure distance to obstacle ahead (sensor 5)
Loop Until (dist < 0.1 Or Abs(sensor5) < 0.5)
‘——– continue Motion to goal until goal reached or obstacle hit
‘ ———————-Boundary Following —————-
SetMobotColor(0,QBColor(4))’ boundary following colour (brown)
D0 = .5′ set desired distance to the wall
gain = 30′ set gain for propotional (P) controller
‘ SetSteering(0,0,90)’ mobot turns into the direction of rot (amplified by a factor)
‘ SetSteering(Mobot number, forward speed, turning angle)
Do’ ——– Boundary Following Loop ———
sensor3 = MeasureRange(0,3,0) ‘Read sensor 3 (right)
delta = D0 – sensor3’ deviation from desired distance
SetWheelSpeed(0,20-delta*gain,20+delta*gain)
‘ Actuation: set the speeds of the robot wheels proportional to delta
StepForward ‘ Dynamics simulation progresses one-time step
rot2=RotationalDiff(0, goals, goals)’ calculate difference between heading angle and “goal” angle
‘Debug.Print rot2
Loop Until (rot2 >=90) ‘ —— End of boundary following Loop ——
Loop Until (dist < 0.1)
End Sub

The bug and algorithms which are bug-like usually are straightforward in their implementation. The basic analysis shows that the success of these algorithms is guaranteed whenever their application is possible. There are two behaviors which these algorithms require which are boundary following and motion to the goal. Mathematically, it has been proved that the length of the path between bug 1 and bug 2 has the condition represented in the image below.

Fig 4: Condition for the length of bug 1 and bug 2
From the equation above, d (qstart, qgoal) are representations of the Euclidian distance which is the distance between the start and the goal. Pi is the representation of the perimeter of the specific obstacle in question where n represents the number of barriers in the configuration space. Finally, ni represents the number of intersections which are between M-line and the obstacle in the ith position.
Bug 1 Algorithm
With the bug algorithm, the surest way to reach a goal is to move straight toward the target or an obstacle is reached. However, there is a difference in how the circumnavigation of the barrier is carried out in bug 1 and bug 2. In bug 1, the robot circumnavigates the obstacle through the entire perimeter of the obstacle while finding the closest point from which it can obtain the goal. Due to its nature of searching exhaustively, this algorithm is referred to as an exhaustive search algorithm since it looks for the leaving point which is optimal. After this, the robot gets into the motion to the goal. It heads straight towards the goal and peradventure another obstacle is encountered, this behavior is repeated until the goal point is achieved.
For the sake of testing the bug one algorithm, a simple environment shown in the figure below was developed.

Fig 5: Bug 1 environment
From the above illustration, fig 5, the robot ought to move from the bottom left of the workspace moving upwards towards the goal. Looking at part b of the illustration, it is evident that the robot goes around the entire obstacle after which it departs from the closest point heading to the goal. This proves the expected motion of the robot bug one algorithm. To ensure the algorithm is consistent, the goal and start position are placed randomly in different locations. And the results obtained are illustrated in the figure below.

Fig 6: Bug 1 environment with different start and goal positions
From the above illustration, bug 1 proved that its functionality is the same and consistent irrespective of random start and goal positions. This ensures that the behavior of a bug one mobile robot simulator algorithm is valid.
Despite the efficiency of bug 1 in the first environment, there is the possibility of having an environment which is significantly complicated. This makes the bug one algorithm to fail to find the path to the goal. Such a situation can be easily achieved by having the placed nearby in such a way that the sensors are unable to find their way via the obstacle. If accidentally the opening between the obstacles is too small for the robot to pass, the mobot could get stuck in the workspace thus not achieving the goal point. The figure below is an illustration of a workspace with a starting point and goal. However, the bug one algorithm is unable to get to the goal and get stuck in the workspace.

Fig 7: failing of bug one algorithm
From the illustration, despite being a possible path for the robot to use passing through the bottom left all the way up to the goal, it is unable to find it and thus get stuck I the obstacle unable to circumnavigate them. This is a clear indication of the shortcoming of the bug one algorithm because it tries to follow a straight line thus failing to recognize alternative routes to the goal. The failure of the algorithm is attributed to the complexity of this environment despite the general behavior proving to solve it.
Bug 2 Algorithm
The behavior of this algorithm is similar to that of bug 1. During the process of identifying the goal, the robot moves straight heading to the goal until encountering an obstacle. The robot circumnavigates the obstacle to the point from the start to the goal line that is of proximity in comparison to the initial contact point. It is thus considered a greedy algorithm since on finding a better leave point as compared to the first one; it opts for it. After this, it moves straight heading toward the goal unless it encounters another obstacle. This process is repeated over and over again until the goal is reached. This algorithm is quicker when the navigation is in a simple environment. However, when the environment is of a complex nature, the approach of bug one which is exhaustive is a better performer and hence preferred.
Comparing the two algorithms is achieved by providing the same environment for both of them. As shown in the illustration below, the bug two algorithm does not circumnavigate the entire obstacle as it was the case in bug 1.

Fig 8: bug 2 in a simple environment
Despite its quick performance in a simple setting, the robot as well gets stuck when the situation gets complex as shown in the figure below.

Fig 9: bug 2 in a complex environment
In conclusion, the simulations carried out are meant to prove and compare them with their theoretical values to check their validity. The algorithms of navigation provide a guarantee in the probability that the robot will achieve a given goal from the starting point. Complex environments are however challenging for both the bug 1 and two algorithms as the robot got stuck in both situations.

Reference ListLatombe, J.C., 2012. Robot motion planning (Vol. 124). Springer Science & Business Media.
Tang, S.H., Khaksar, W., Ismail, N.B. and Ariffin, M.K.A., 2012. A review on robot motion planning approaches. Pertanika Journal of Science and Technology, 20(1), pp.15-29.
Van Den Berg, J., Patil, S. and Alterovitz, R., 2012. Motion planning under uncertainty using iterative local optimization in belief space. The International Journal of Robotics Research, 31(11), pp.1263-1278.