Cybernetics and Systems

An International Journal

ISSN: (Print) (Online) Journal homepage: https://www.tandfonline.com/loi/ucbs20

A Decision Algorithm for Motion Planning of Car-

Like Robots in Dynamic Environments

Elias K. Xidias

To cite this article: Elias K. Xidias (2021): A Decision Algorithm for Motion Planning
of Car-Like Robots in Dynamic Environments, Cybernetics and Systems, DOI:
10.1080/01969722.2021.1909844

To link to this article: https://doi.org/10.1080/01969722.2021.1909844

Published online: 05 Apr 2021.

Submit your article to this journal

Article views: 24

View related articles

View Crossmark data

Full Terms & Conditions of access and use can be found at

https://www.tandfonline.com/action/journalInformation?journalCode=ucbs20
CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL
https://doi.org/10.1080/01969722.2021.1909844

A Decision Algorithm for Motion Planning of Car-Like

Robots in Dynamic Environments
Elias K. Xidias
Department of Product & Systems Design Engineering, University of the Aegean, Syros, Greece

ABSTRACT KEYWORDS
Motion planning in dynamic environments is essential for B-spline curves; bump-
many applications such as in search and rescue missions and surface; dynamic
in servicing tasks. In this paper, I present a new approach for environment; genetic
algorithms; motion
motion planning for an autonomous mobile robot which is planning; moving obstacles
requested to operate in a dynamic environment. The robot’s
working environment is cluttered with static obstacles with a
priori knowledge of their shapes and positions and with mov-
ing obstacles with unknown geometry and motion. In order
to ensure a safe motion for the robot I propose a two-stage
approach. First, using the Bump-Surface concept I construct a
path by considering only the static obstacles of the environ-
ment. Then, the robot starts its motion on the given path.
When the robot detects a potential danger situation (i.e., colli-
sion), a decision algorithm tries to evaluate the risk of collision
and simultaneously to find the safest action for the robot. The
proposed approach is evaluated in randomly generated simu-
lated scenarios.

Introduction
Autonomous navigation for various robotic systems such as unmanned aer-
ial vehicles, mobile robots and manipulators, has attracted a lot of interest
during the last decades. Generally, the navigation task can be decomposed
into three important sub-tasks:

Localization,

Motion planning and,

Plan execution.

The present study focuses on the motion planning problem (termed

MMP) of a mobile robot which is requested to operate in a dynamic envir-
onment. Here, the robot is requested to move form an initial given state
(position and orientation) to a final state avoiding the collisions with the

CONTACT Elias K. Xidias xidias@aegean.gr Department of Product & Systems Design Engineering,
University of the Aegean, Konstantinoupoleos 1, Syros 84100, Greece.
ß 2021 Taylor & Francis Group, LLC
2 E. K. XIDIAS

Figure 1. The humanoid robot pepper is requested to help flyers in the Munich international
airport (https://www.thestar.com.my).

static and moving objects which may appear in the robot’s environment. I
was motivated by scenarios in which the robot must execute a series of axi-
ons in an indoor dynamic environment, such as an airport or in a manu-
factory. An example of such a case is shown in Figure 1, where a
humanoid robot is requested to help peoples in an airport.

Related Work
Determining feasible paths in dynamic environments has attracted signifi-
cant attention in the robotics research community (Lu, Xi, and Lien 2016).
There have been many different approaches for motion planning of
autonomous mobile robots which are operating in dynamic environments.
The proposed approaches can be classified in five main categories
(Latombe 1991): Artificial Potential fields-based approaches, State-Time
Space based approaches, Velocity obstacles-based motion planning
approaches, and Probabilistic collision checking based approaches.
The approaches which are based on the artificial potential field (APF)
generate a combined potential field in which the robot is attracted to its
target position and is repulsed away from the obstacles (Latombe 1991). In
most cases the existing APF approaches assume that, the attractive potential
field is defined as the relative position of the ending state to the robot
while the repulsive potential field is defined as a combination of the relative
position of the robot to the obstacles and the relative velocity of the robot
to the moving obstacles. The combined potential field moves the robot in
the environment in terms of both position and velocity rather than position
only (Ge and Cui 2002; Qixin, Yanwen, and Jingliang 2006; Chiang et al.
2015; Bounini et al. 2017). In most research works the robot is considered
as a point while the obstacles have convex shape. Furthermore, it is
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 3

assumed that, at each time instant only one obstacle is close to the robot.
In the literature, it has been reported that the APF suffer from many
drawbacks (Bing et al. 2011), such as trapping in local minima and huge
number of computations due to the enormous complexity introduced by
real-world landscapes. With the aim to overcome such limitations, there
have emerged hundreds of proposals using heuristic approaches, making
very difficult for its analysis.
The state-time space (Fraichard 1998) is an extension of the configuration
space C (Latombe 1991) and consists of pairs ðx, tÞ, where x denoting the
robot’s position, and t denoting the time. In state-time space, the robot is rep-
resented by a point while both static and moving obstacles are transformed to
static obstacles. The approaches which are based in state-time are typically lim-
ited to low dimensional state spaces and/or require significant computation
time (Latombe 1991). Furthermore, the derived paths must respect an add-
itional constraint, which is that the paths should be time monotonic since the
time marches forward. In (Petti and Fraichard 2005; Van den Berg and
Overmars 2008) probabilistic approaches are used for computing paths in
state-time space. These planners incrementally build a tree of explored configu-
rations for each planning query. More recently, researchers are trying to reduce
the complexity of the planning problem by first constructing a path based on
the off-line information of the environment, and subsequently planning a colli-
sion-free trajectory on this path/roadmap that considers the on-line informa-
tion (Zhang, Fattahi, and Li 2013).
The approaches which are based on Velocity obstacles concept first,
define the velocity obstacles by computing the robot’s velocities that would
cause a collision with obstacles at some near-future time assuming that the
obstacles are moving with constant velocities (Fiorini and Shiller 1998).
Then, an avoidance maneuver is computed by choosing velocities that are
outside of the velocity obstacles. A derived collision-free trajectory consists
of a series of avoidance maneuvers (Lee, Jeon, and Oh 2017; Huang, van
Gelder, and Wen 2018). However, these approaches are restricted (a) to
planning decisions to the velocity of the robot and (b) to represent each
obstacle (including the robot) as disk. While the disk representation has
several advantages, it should be noted that, a disk overestimates the actual
profile of an object. Furthermore, these approaches require that the time
horizon be carefully determined, otherwise the robot may avoid passing
through tight spaces and therefore it can be difficult to determine the
shortest path. The selection of the proper time horizon is still unresolved.
On the other hand, there are several approaches which deal with the
uncertainty or with the imperfect representation of the environment, per-
forming probabilistic collision detection. Some of them, approximate the
collision probability using numerical integrations (Blackmore 2006) or
4 E. K. XIDIAS

stochastic techniques (Lambert, Gruyer, and Saint Pierre 2008), which

require a large number of sample evaluations to compute an accurate prob-
ability. Another perspective is finding a path for the robot that is safe by
construction. If the system is modeled as a Markov Decision Process, for-
mal verification methods can be used to construct a plan that is guaranteed
to be safe (Feyzabadi and Carpin 2016). Finally, some approaches explicitly
model the uncertainty that arises due to unpredictable moving obstacles
(Rohrmuller et al. 2008). Moving obstacles are extracted from subsequent
sensor readings and their position and velocity is estimated to obtain a
probabilistic model that resembles the risk of collision. However, all these
approaches have slow convergence and prohibitive costs that increase with
the complexity of uncertainty.

Contributions
In this study I propose a two-stage approach for the MPP of a car-like
robot which is moving in dynamic environments:

In the first step, I use the Bump-Surface concept (Azariadis and

Aspragathos 2005) to create an optimum path in the static environment.
The proposed path is represented by a B-Spline curve (Piegl and
Wayne 1997).

In the second step, the robot starts moving from the predefined starting
state to the ending state by following the given path. If the robot detects
by its onboard sensors a moving obstacle, then a decision algorithm is
triggered to determine if there is a risk of collision between the robot and
the detected obstacle. If the probability of collision is different from zero,
a local motion planner algorithm is used to modifies locally the curve’s
shape or its velocity in order to continue its safe motion to the ending
state. Otherwise, continues its motion to the final state.

Compared to the existing approaches, the main innovations and contri-

butions of the proposed approach are the following:

The proposed method is quite simple and can guarantee the robot’s
safe motion.

The developed global path considers the geometrical and kinematical char-
acteristics of the robot and the morphological characteristics of the work-
ing environment.

A decision algorithm can decide if there is a probability of collision
in msecs.

The proposed local planner is not time-consuming.
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 5

Figure 2. The robot’s environment.

The remainder of the paper is organized as follows: “Problem Statement

& General Assumptions” presents the problem’s formulation and describes
the general assumption and notations. The proposed solution approach is
detailed in “Motion Planning in Dynamic Environment.” Extensive compu-
tational results are reported in “Simulation Results and Discussion” while
“Conclusions” draws some conclusions.

Problem Statement & General Assumptions

In this section, I present and discuss a general formulation for the problem
under consideration. I also give a briefly description of the kinematic model of
a mobile robot and I provide the general concept of Bump-Surfaces.

Formal Problem Definition

Our goal is to develop an approach to navigate a mobile robot safely in
dynamic environment by considering the robot’s kinematical characteristics
and its shape. Figure 2 illustrates the motion planning problem in dynamic
environments.
I make the following assumptions/definitions for the robot and the
environment.
6 E. K. XIDIAS

Figure 3. A schematic representation of the robot.

Assumption 1: The position and the geometry of the static obstacles is known
beforehand while the motion and the geometry of the moving obstacles
is unknown.
Assumption
2: The
 robot is represented by a car-like robot (Figure 3) where
pðtÞ ¼ xðtÞ, yðtÞ is the reference point of the robot. I ignore the steering vel-
ocity, and I assume that the robot is moving with constant velocity ju ~j <
j~
u max j, while the deceleration/acceleration max limits are famax , amax g:
Assumption 3: The robot has onboard sensors that can detect the positions and
velocities of moving objects. The range of the
robot’s sensors define a circle
with center the robot’s reference point pðtÞ ¼ xðtÞ, yðtÞ and radius Rs : An
illustration of the robot’s configuration and its environment is shown in
Figure 2, where opi ðtÞ ¼ ðoxi ðtÞ, oyi ðtÞÞ is the moving obstacle’s reference point
located at the center of rear middle axis and ~v i ðtÞ is the velocity of
the iobstacle.
Assumption 4: An iobstacle (i ¼ 1, :::, n) can have any shape. In this paper, I
assume that its shape is identical to that of the robot.
Assumption 5: The moving obstacles are “fair” players meaning that, when the
robot’s sensors detect an obstacle, then the moving iobstacle is not going to
do any sudden movement (e.g., to stop or to change its direction) and is mov-
ing in a constant direction with constant velocity.

Under the above analysis and assumptions, the aim is twofold:

A. To determine a robot’s feasible global path global that minimizes the total
travel time, is smooth and have a lower-bounded turning radius.
B. To avoid moving obstacles, choosing a collision avoidance maneuver in
such a way that the deviation from the initial path is minimum.
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 7

The Kinematical Model of a Mobile Robot

I consider that, the model of our mobile robot represents a car-like robot
with rectangular shape body (Figure 3). It has the following characteristics:

Has features like that of a car, i.e., a limited steering angle, which imposes
to a lower bounded turning radius.

It moves only forward and a long a direction normal on its rear
wheels’ axle.

The kinematical model of the robot can be described by the following

mathematical formula,
8
>
> _
xðtÞ ¼ uðtÞ cos ðhðtÞÞ
>
<
y_ ðtÞ ¼ uðtÞ sin ðhðtÞÞ
(1)
>
> uð t Þ
> h_ ðtÞ ¼
: tan ðuðtÞÞ
l
where,

q ¼ ½x, y, h, uΤ is the system state,

ðxðtÞ, yðtÞÞ are the coordinates of the middle point of the rear wheel axle
in the Cartesian space at time t,

hðtÞ is the orientation of the mobile robot with respect to the fixed frame
in our case the X axis,



uðtÞ 2  p2 , p2 is the steering angle at time t,

l is the distance between the front and rear wheel-axle centers,

uðtÞ is the driving velocity at time t and has the same direction with the
tangent vector at point ðxðtÞ, yðtÞÞ:

Mapping the Environment

In order to help the robot to move safely in the static environment and to
avoid the deadlocks or livelocks, I am mapping the robot’s environment by
using the following procedure:

A. Considering only the static obstacles of the normalized environment, I

determine the minimum distance md between the static obstacles and
between a static obstacle and the borders of the environment (Figure 4(a)).
If md  2w, where w is the size of robot’s width, then I fill this space
with a virtual obstacle (Figure 4(b)).
B. Considering the position and the shape of the “new” virtual static
obstacles, I use the Bump-Surface concept to represent the updated 2D
static environment. The construction of the Bump-Surface is obtained by a
8 E. K. XIDIAS

Figure 4. (a) The robot’s static environment. (b) The “new” environment, where the virtual obs-
tacle is represented with orange color and the central path (red line segments). (c) The corre-
sponding Bump-Surface.

straightforward extension of the z-value algorithm (Azariadis and

Aspragathos 2005), where the environment is discretized into uniform
subintervals along the orthogonal directions x and y, forming a grid of 3D
points pi, j ¼ ðui, j , vi, j , zi, j Þ 2 ½0, 1, ði, jÞ 2 ½0, Ng 12 where Ng denoted the
grid size and zi, j 2 ð0, 1 if the corresponding pi, j lies inside an obstacle
and zi, j ¼ 0 otherwise. In this paper, we used a (2,2)-degree B-Spline
Surface with improved the local isometry (Xidias and Azariadis 2011) to
represent the Bump-Surface S : ½0, 12 ! ½0, 13 , which is given by,
X
Ng 1 N
Xg 1

S ¼ Sðx, yÞ ¼ Ni2 ðxÞNj2 ðyÞpi, j (2)

i¼0 j¼0

where Ni2 ðxÞ and Nj2 ðyÞ are the B-Spline are functions. Figure 4(c) a
virtual representation of the corresponding Bump-Surface, where the
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 9

Figure 5. Motion planning architecture.

flat areas show the collision free space, and the bumps shows the for-
bidden areas.

Motion Planning in Dynamic Environment

I now present and discuss the developed solution approach. First, I present
the general mechanism and then I describe in detail its main components.
A schematic overview of the proposed approach is illustrated in Figure 5.
Given the static 2D environment, the starting and ending state, I construct
the “new” robot’s environment and then by using the Bump-Surface con-
cept and the Static/GA I determine the shortest path (minimum travel
time) by taking into account the kinematical robot’s characteristic and its
shape. Then, the robot starts its motion in the derived global path. When
the robot detects a moving object, the proposed decision algorithm is trig-
gered to determine if there is a risk of collision between the robot and the
detected moving obstacle. If the probability of collision is different from
zero a local motion planner algorithm is used to modifies locally the
robot’s path or its velocity in order to continue its motion to the ending
state. The objective of MPP is to determine the optimal robot motion plan
in the robot’s environment.

Determining a Collision Free Path for the Robot in the Static Environment
Given the central path, a path which connect the starting state and the end-
ing state should be computed. I adopt a two-degree B-Spline curves (Piegl
and Wayne 1997) to represent the robot’s path (Figure 6) which is repre-
sented as,
X
K1
CðsÞ ¼ ðxðsÞ, yðsÞÞ ¼ Nn2 ðsÞpn , s 2 ½0, 1 (3)
n¼0
10 E. K. XIDIAS

Figure 6. (a) Two random surfaced curves by the Static/GA. (b) Another point of view.

where pn ¼ fp0 , :::, pK1 g 2 ½0, 1  ½0, 1 are the control points which
define the B-Spline curve. Where,

p0 denotes the starting point.

pK1 denotes the ending point.

K is the overall number of knots (including the start and goal point)
which defined the backbone path.

Nn2 ðsÞ is the B-Spline base function.

The main reasons for adopting B-Spline curves to represent the central
path are the following:

They give us great control over the shape of a curve. A set of control
points and knot vectors, which guide the curve’s shape, can be directly
manipulated to control its smoothness and its curvature.

They can represent very complex shapes with remarkably little data.

They have simple mathematical formula.

Computational algorithms based on B-spline surfaces (and curves) are fast
and numerically stable.

The goal of the motion planning strategy is the determination of the

K  2 control points pn which define the collision free robot’s path.
Furthermore, it is considered that the robot’s orientation in each path’s
point has the same direction with the tangent vector of CðsÞ at that point.
A feasible path should be a path which is close as possible to the original
central path while satisfying the problem’s constraints. The minimization of
L, where L is the arc length of CðsÞ leads to a path which connect the start
and the goal and is smooth.
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 11

Since the robot’s steering angle is mechanically limited, a curvature con-

straint incorporated in the path CðsÞ: At each point Cj , j ¼ 1, :::, Np of
CðsÞ the corresponding curvature Cuj should be smaller than or equal to
maximum allowed curvature Cumax which is described by,
Cuj  Cumax , j ¼ 1, :::, Np (4)
In order to compute the curvature Cuj at each point Cj , j ¼ 1, :::, Np of
CðsÞ computationally fast, first I discretize the CðsÞ by Np  1 equal
sequential chords. Then, I compute the curvature Cj at point Cj by using
the following formula (Xidias and Azariadis 2011),
Cuj ¼ kCj1  2Cj þ Cjþ1 k  Cumax , j ¼ 2, :::, Np  1 (5)
Furthermore, to take into account, the size of the robot, at each point
Cj , j ¼ 1, :::, Np of CðsÞ I compute the minimum distance dmin between the
rectangular shape of the robot and the closest obstacle or the closest border
j
of the environment. The dmin , j ¼ 1, :::, Np should be greater than or equal
to dsafe , which is defined by the user.
Taking the above analysis into consideration, the goal of the proposed
motion planning problem is to determine a central path for the robot
which avoids the static obstacles and satisfies the above constraints by
adjusting of the K  2 control points pn , n ¼ 1, :::, K  2 : The global opti-
mization problem is formulated as,
minðLÞ, w:r:t: pn , n ¼ 1, :::, K  2
(
Cuj  Cumax
subject to j , j ¼ 2, :::, Np  1 (6)
dmin  dsafe

Computing an Optimum Path

Genetic Algorithms (GA) (hereinafter referred as Static/GA) has been
adopted to solve the problem presented in Eq. (7). Each chromosome of
the proposed Static/GA is represented by a floating-point scheme and
expressed by a sequence of the unknown control points pn , n ¼ 1, :::, K  2:
The following genetic operators are used (Goldberg 1989): Reproduction,
One-Point Crossover, and Mutation. The fitness function is given by,

F¼1 L
(
Cuj  Cumax
subject to j , j ¼ 2, :::, Np  1 (7)
dmin  dsafe

Figure 6, shows an example of two random paths by the Static/GA while

is searching on the Bump-Surface for the optimum path. The surfaced
12 E. K. XIDIAS

Figure 7. A simplified diagram for the calculation of the collision area, where the dotted lines
are vehicles’ directions.

curve with brown color proposes a path which is passing through the obs-
tacle while the surfaced curve with red color proposes a collision free path.

Local Planning
The main challenges of computing a safe maneuver for a robot while is
moving in a dynamic environment are: (a) to estimate the collision risk
between the robot and the moving obstacle and (b) to determine a safe
action in order to avoid the collision (if one exist).
In this section, I detail the procedure for estimating the collision risk
between the robot and the moving obstacle and then I present the collision
avoidance procedure.

Decision Algorithm
While the robot is moving on the constructed global path, I assume that, at
time instance t the robot detects a moving iobstacle which is moving
 
with velocity ~v ob 
i ðtÞ and its position is pi ðtÞ: Then, I compute the relative
ob

velocity between the robot and the iobstacle in the direction from the
robot to the obstacle, which is given by,

~ ro ðtÞ ¼ ½uðtÞ  ~v ob
u i ðtÞnro (8)

where nro is a unit vector pointing from the robot to the obstacle. If
~ ro ðtÞ  0, i.e., the robot is moving away from the obstacle, no collision
u
avoidance maneuver is needed. If u ~ ro ðtÞ > 0, i.e., the robot is moving close
to the obstacle, a collision avoidance action needs to be implemented.
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 13

Figure 8. The probability of collision.

Let consider that at time instance t, the robot is moving toward to the
~ ro ðtÞ > 0). Then, I use the Time to Collision (TTC) metric
iobstacle (i.e., u
(Noh and An 2017) as a criterion to cover the risky situations that may
occur from the motion of the moving obstacles in the robot’s environment.
TTC is the time of intersection between two of more objects. TTC is the
most well-known indicator and is applied in different studies for evaluating
the collision risk between two moving objects.
The determination of the TTC consists of the following steps:

A. I determine the collision area, which is defined by four collision points

(red dots), between the robot and the moving i obstacle by taking into
account their current positions and directions (Figure 7).
B. I calculate the time required by each one of the two moving objects (robot
and i obstacle) to reach the point ðcx, cyÞ: When these two times coin-
cide ði:e:, cti ¼ ctr Þ then, the two objects are going to collide (this is
the TTC).
C. In order to include a safety margin (such as the size of the moving
objects) that compensates the simplifications that have been made, a factor
d is considered to determine the TTC, as follow:
TTC ¼ jctr  cti j < d (9)
The higher the d value is, the more conservative the algorithm becomes.
Remark: In several research projects as ARCOS (www.arcos2004.fr) have
studied the metric TTC and give boundaries on the behavior of an auto-
mated system, with respect to the following values:
14 E. K. XIDIAS

Figure 9. The moving objects are sharing the same path and are moving with oppos-
ite directions.

at a TTC  10 sec, the moving iobstacle is supposed that not affect

the robot,

at a 1 sec  TTC < 10 sec, a warning is triggered, and collision avoidance
action must take place.

at a TTC < 1 sec, a collision will happen.

Two values are used to determine the probability of collision, the value 1
when collision occurs (TTC < d ¼ 1 sec) and the value 0 for no collision
(TTC  10 sec). Between these values, the probability of collision is linear
with respect to the time TTC (Figure 8).

Local Motion Planner

If the computed TTC (Decision algorithm) takes a value in the interval
½1, 10Þ, a collision avoidance action should be planned which is described
as follows:

A. If ctr  cti , I increase the robot’s velocity with acceleration a ¼

drmin þhc juðtÞj cti
2 cti 2 at the point CðtÞ, when the robot exits from the collision
area, the robot’s velocity becomes equal to juðtÞj: Otherwise, we decelerate
juðtÞj ctr ðdimin þwc Þ
the robot’s velocity with deceleration a ¼ 2 ctr 2 in order the
iobstacle passes through the collision point first.
B. If the two moving objects are sharing the same path with opposite direc-
tions (Figure 9), then I repeat the procedure descripted in “Determining a
Collision Free Path for the Robot in the Static Environment,” where the
collision area is transformed to a virtual obstacle, the robot’s initial state is
the current robot’s state while the robot’s final state is the current moving
obstacle’s state.

If the computed TTC takes a value in the interval ½0, 1Þ, then the robot
must perform an emergency break.
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 15

Figure 10. (a) The initial robot’s path. (b) The robot detects a moving obstacle. (c), (d) Two
consecutive time instances where the robot avoids the collision with the obstacle. (e) The colli-
sion point.

Simulation Results and Discussion

In this section, I evaluate the proposed approach qualitatively through a
simulation experiment for a robot moving in a 2D dynamic environment.
16 E. K. XIDIAS

Figure 11. The robot’s speed profile diagram.

All simulations are implemented in Matlab and run on a 3.50 GHz PC. The
control parameters of the proposed GA were:

population size ¼ 250,

maximum number of generations ¼ 500,

crossover rate ¼ 0:75,

mutation rate ¼ 0:004

The goal of this scenario is to present the ability of the proposed

approach to determine the shortest path in a dynamic environment. In this
environment I assume that there are several static obstacles with arbitrary
sizes and shapes and two moving obstacles (Figure 10). The two moving
obstacles are perceived by the robot when they enter in the robot sensors’
range. The robot is represented by a car with red color and the two moving
obstacles with cyan color. Furthermore, I assume that the robot’s speed is 1
while each a moving obstacle is moving with constant speed equal to
1.4 units.
In the first step, I construct a collision free shortest path by using the
bump-Surface concept (Figure 10(a)). The proposed path is defined by 6
control points þ the start and end points (i.e., by 8 control points). In
Figure 10(a) are represented by blue dots. The robot starts its motion on
the constructed path. While moving, at time instance tk , it detects a mov-
ing obstacle (Figure 10(b)), then the decision algorithm is activated and
finds that there will be a collision between the robot and the moving obs-
tacle. In Figure 10(b), the dashed circle shows the robot sensors’ range.
point. The robot arrives first at the collision point and according the
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 17

Figure 12. The robot detects a new obstacle.

Figure 13. The proposed maneuver.

decision algorithm should accelerate to avoid the collision. In Figure 10(c)

and (d) we can see that the robot avoids the collision with the moving obs-
tacle. In Figure 10(e) we can see the collision point while Figure 11 shows
the deviation of the robot’s speed while avoiding the moving obstacle.
The robot, while continues its motion on the constructed path at time tl
detects a new moving obstacle (Figure 12). The obstacle moves on the
same path with robot, with opposite direction. The decision algorithm is
activated and decides that the robot should deviate from its path. Figure 13
presents the robot’s maneuver, where the alternative path (red curve) is
represented by a B-spline curve which is defined by 5 control points (blue
dots). The first point is the robot’s position at time while the last control
18 E. K. XIDIAS

Figure 14. Three-time instances where the robot avoids the moving obstacle.

point is the obstacle’s position at time tl : The intermediate control points

are defined by the Static/GA (Computing an Optimum Path). The overall
number of the intermediate control points is defined by the user. Figure 14
presents three successive time instances where the robot follows the pro-
posed maneuver in order to avoid the collision with the moving obstacle.
In all experiments, the first step of the proposed approach which
includes the construction of initial robot’s path takes less of 3 sec while
decision algorithm takes few msecs.

Conclusions
In this paper I tackled the problem of motion planning within a dynamic
environment and proposed a decision algorithm which can guarantee the
safe motion of car-like robot in it. The proposed approach first, creates a
global path by taking into account both the kinematical characteristic of
the robot and the static obstacles which are cluttered in the environment.
Then, the robot starts moving from the predefined starting state to the
 CYBERNETICS AND SYSTEMS: AN INTERNATIONAL JOURNAL 19

ending state by following the given path. If the robot detects by its onboard
sensors a moving obstacle, then the proposed decision algorithm is trig-
gered to determine if there is a risk of collision between the robot and the
detected obstacle. If the probability of collision is different from zero, a
local motion planner algorithm is used to modifies locally the curve’s shape
or the robot’s velocity in order to continue its safe motion to the ending
state. Otherwise, continues its motion to the final state. Experimental tests
were conducted for various scenarios to verify the validity of the pro-
posed approach.
Future work will be devoted to two different directions. The first direc-
tion will be concentrated on applying the proposed concept to physical
experiments. The second direction will be concentrated in the context of a
multi-robots’ scenario in which several mobile robots can make decisions.
Here, the future work will be focused on the extension of the proposed
approach and development of planning techniques to share the decision-
making process among several robots to obtain mutually optimized plans.

References
Azariadis, P., and N. Aspragathos. 2005. Obstacle representation by bump-surfaces for opti-
mal motion-planning. Robotics and Autonomous Systems 51 (2-3):129–50. doi:10.1016/j.
robot.2004.11.001.
Bing, H., L. Gang, G. Jiang, W. Hong, N. Nan, and L. Yan. 2011. A route planning method
based on improved artificial potential field algorithm. IEEE 3rd International Conference
on Communication Software and Networks, Xi’an, China. doi:10.1109/iccsn.2011.
6014330.
Blackmore, L. 2006. A Probabilistic Particle Control Approach to Optimal, Robust
Predictive Control. AIAA Guidance, Navigation, and Control Conference and Exhibit
keystone Colorado. doi:10.2514/6.2006-6240.
Bounini, F., D. Gingras, H. Pollart, and D. Gruyer. 2017. Modified artificial potential field
method for online path planning applications. IEEE Intelligent Vehicles Symposium
(IV), Los Angeles, CA, USA. doi:10.1109/ivs.2017.7995717.
Chiang, H.-T., N. Malone, K. Lesser, M. Oishi, and L. Tapia. 2015. Path-guided artificial
potential fields with stochastic reachable sets for motion planning in highly dynamic
environments. IEEE International Conference on Robotics and Automation (ICRA),
Washington, USA. doi:10.1109/icra.2015.7139511.
Feyzabadi, S., and S. Carpin. 2016. Multi-objective planning with multiple high level task
specifications. IEEE International Conference on Robotics and Automation (ICRA),
Stockholm, Sweden. doi:10.1109/icra.2016.7487762.
Fiorini, P., and Z. Shiller. 1998. Motion planning in dynamic environments using velocity
obstacles. The International Journal of Robotics Research 17 (7):760–72. doi:10.1177/
027836499801700706.
Fraichard, T. 1998. Trajectory planning in a dynamic workspace: A “state-time space”
approach. Advanced Robotics 13 (1):75–94. doi:10.1163/156855399X00928.
Ge, S. S., and Y. J. Cui. 2002. Dynamic motion planning for mobile robots using potential
field method. Autonomous Robots 13 (3):207–22. doi:10.1023/A:1020564024509.
20 E. K. XIDIAS

Goldberg, D. E. 1989. Genetic algorithm in search, optimization and machine learning.

Reading, MA: Addison Wesley.
Huang, Y., P. H. A. J. M. van Gelder, and Y. Wen. 2018. Velocity obstacle algorithms for colli-
sion prevention at sea. Ocean Engineering 151:308–21. doi:10.1016/j.oceaneng.2018.01.001.
Lambert, A., D. Gruyer, and G. Saint Pierre. 2008. A fast Monte Carlo algorithm for colli-
sion probability estimation. 10th International Conference on Control, Automation,
Robotics and Vision, Hanoi, Vietnam. doi:10.1109/icarcv.2008.4795553.
Latombe, J. C. 1991. Robot motion planning. Boston: Kluwer Academic Publishers.
Lee, B. H., J. D. Jeon, and J. H. Oh. 2017. Velocity obstacle based local collision avoidance for a
holonomic elliptic robot. Autonomous Robots 41 (6):1347–63. doi:10.1007/s10514-016-9580-2.
Lu, Y., Z. Xi, and J.-M. Lien. 2016. Online collision prediction among 2D polygonal and
articulated obstacles. The International Journal of Robotics Research 35 (5):476–500. doi:
10.1177/0278364915603225.
Noh, S., and K. An. 2017. Risk assessment for automatic lane change maneuvers on high-
ways. IEEE International Conference on Robotics and Automation (ICRA), Singapore.
doi:10.1109/icra.2017.7989031.
Petti, S., and T. Fraichard. 2005. Safe motion planning in dynamic environments. IEEE/RSJ
International Conference on Intelligent Robots and Systems, Edmonton, Canada. doi:10.1109/
iros.2005.1545549.
Piegl, L., and T. Wayne. 1997. The NURBS book. Berlin: Springer-Verlag.
Qixin, C., H. Yanwen, and Z. Jingliang. 2006. An evolutionary artificial potential field algo-
rithm for dynamic path planning of mobile robot. IEEE/RSJ International Conference on
Intelligent Robots and Systems, Beijing, China. doi:10.1109/iros.2006.282508.
Rohrmuller, F., M. Althoff, D. Wollherr, and M. Buss. 2008. Probabilistic mapping of dynamic
obstacles using Markov chains for replanning in dynamic environments. IEEE/RSJ
International Conference on Intelligent Robots and Systems, Nice, France. doi:10.1109/iros.
2008.4650952.
Van den Berg, J., and M. Overmars. 2008. Planning time-minimal safe paths amidst unpre-
dictably moving obstacles. The International Journal of Robotics Research 27 (11-12):
1274–94. doi:10.1177/0278364908097581.
Xidias, E. K., and P. N. Azariadis. 2011. Mission design for a group of autonomous guided
vehicles. Robotics and Autonomous Systems 59 (1):34–43. doi:10.1016/j.robot.2010.10.003.
Zhang, Y., N. Fattahi, and W. Li. 2013. Probabilistic roadmap with self-learning for path plan-
ning of a mobile robot in a dynamic and unstructured environment. IEEE International
Conference on Mechatronics and Automation, Takamatsu, Japan. doi:10.1109/icma.2013.
6618064.