Autonomous Vehicle Navigation Using Harmonic Functions via Modified Arithmetic Mean Iterative Method
Harmonic functions are solutions to Laplace’s equation
that are known to have an advantage as a global approach in providing
the potential values for autonomous vehicle navigation. However,
the computation for obtaining harmonic functions is often too slow
particularly when it involves very large environment. This paper
presents a two-stage iterative method namely Modified Arithmetic
Mean (MAM) method for solving 2D Laplace’s equation. Once
the harmonic functions are obtained, the standard Gradient Descent
Search (GDS) is performed for path finding of an autonomous vehicle
from arbitrary initial position to the specified goal position. Details
of the MAM method are discussed. Several simulations of vehicle
navigation with path planning in a static known indoor environment
were conducted to verify the efficiency of the MAM method. The
generated paths obtained from the simulations are presented. The
performance of the MAM method in computing harmonic functions
in 2D environment to solve path planning problem for an autonomous
vehicle navigation is also provided.
Fast Return Path Planning for Agricultural Autonomous Terrestrial Robot in a Known Field
The agricultural sector is becoming more critical than ever in view of the expected overpopulation of the Earth. The introduction of robotic solutions in this field is an increasingly researched topic to make the most of the Earth's resources, thus going to avoid the problems of wear and tear of the human body due to the harsh agricultural work, and open the possibility of a constant careful processing 24 hours a day. This project is realized for a terrestrial autonomous robot aimed to navigate in an orchard collecting fallen peaches below the trees. When it receives the signal indicating the low battery, it has to return to the docking station where it will replace its battery and then return to the last work point and resume its routine. Considering a preset path in orchards with tree rows with variable length by which the robot goes iteratively using the algorithm D*. In case of low battery, the D* algorithm is still used to determine the fastest return path to the docking station as well as to come back from the docking station to the last work point. MATLAB simulations were performed to analyze the flexibility and adaptability of the developed algorithm. The simulation results show an enormous potential for adaptability, particularly in view of the irregularity of orchard field, since it is not flat and undergoes modifications over time from fallen branch as well as from other obstacles and constraints. The D* algorithm determines the best route in spite of the irregularity of the terrain. Moreover, in this work, it will be shown a possible solution to improve the initial points tracking and reduce time between movements.
A Review on Comparative Analysis of Path Planning and Collision Avoidance Algorithms
Autonomous mobile robots (AMR) are expected as smart tools for operations in every automation industry. Path planning and obstacle avoidance is the backbone of AMR as robots have to reach their goal location avoiding obstacles while traversing through optimized path defined according to some criteria such as distance, time or energy. Path planning can be classified into global and local path planning where environmental information is known and unknown/partially known, respectively. A number of sensors are used for data collection. A number of algorithms such as artificial potential field (APF), rapidly exploring random trees (RRT), bidirectional RRT, Fuzzy approach, Purepursuit, A* algorithm, vector field histogram (VFH) and modified local path planning algorithm, etc. have been used in the last three decades for path planning and obstacle avoidance for AMR. This paper makes an attempt to review some of the path planning and obstacle avoidance algorithms used in the field of AMR. The review includes comparative analysis of simulation and mathematical computations of path planning and obstacle avoidance algorithms using MATLAB 2018a. From the review, it could be concluded that different algorithms may complete the same task (i.e. with a different set of instructions) in less or more time, space, effort, etc.
Application of Rapidly Exploring Random Tree Star-Smart and G2 Quintic Pythagorean Hodograph Curves to the UAV Path Planning Problem
This work approaches the automatic planning of paths
for Unmanned Aerial Vehicles (UAVs) through the application of the
Rapidly Exploring Random Tree Star-Smart (RRT*-Smart) algorithm.
RRT*-Smart is a sampling process of positions of a navigation
environment through a tree-type graph. The algorithm consists of
randomly expanding a tree from an initial position (root node) until
one of its branches reaches the final position of the path to be
planned. The algorithm ensures the planning of the shortest path,
considering the number of iterations tending to infinity. When a
new node is inserted into the tree, each neighbor node of the
new node is connected to it, if and only if the extension of the
path between the root node and that neighbor node, with this new
connection, is less than the current extension of the path between
those two nodes. RRT*-smart uses an intelligent sampling strategy
to plan less extensive routes by spending a smaller number of
iterations. This strategy is based on the creation of samples/nodes
near to the convex vertices of the navigation environment obstacles.
The planned paths are smoothed through the application of the
method called quintic pythagorean hodograph curves. The smoothing
process converts a route into a dynamically-viable one based on the
kinematic constraints of the vehicle. This smoothing method models
the hodograph components of a curve with polynomials that obey
the Pythagorean Theorem. Its advantage is that the obtained structure
allows computation of the curve length in an exact way, without the
need for quadratural techniques for the resolution of integrals.
Three-Dimensional Off-Line Path Planning for Unmanned Aerial Vehicle Using Modified Particle Swarm Optimization
This paper addresses the problem of offline path
planning for Unmanned Aerial Vehicles (UAVs) in complex threedimensional
environment with obstacles, which is modelled by 3D
Cartesian grid system. Path planning for UAVs require the
computational intelligence methods to move aerial vehicles along the
flight path effectively to target while avoiding obstacles. In this paper
Modified Particle Swarm Optimization (MPSO) algorithm is applied
to generate the optimal collision free 3D flight path for UAV. The
simulations results clearly demonstrate effectiveness of the proposed
algorithm in guiding UAV to the final destination by providing
optimal feasible path quickly and effectively.
Optimization Based Obstacle Avoidance
Based on a non-linear single track model which
describes the dynamics of vehicle, an optimal path planning strategy
is developed. Real time optimization is used to generate reference
control values to allow leading the vehicle alongside a calculated lane
which is optimal for different objectives such as energy consumption,
run time, safety or comfort characteristics. Strict mathematic
formulation of the autonomous driving allows taking decision on
undefined situation such as lane change or obstacle avoidance. Based
on position of the vehicle, lane situation and obstacle position, the
optimization problem is reformulated in real-time to avoid the
obstacle and any car crash.
A New Multi-Target, Multi-Agent Search-and-Rescue Path Planning Approach
Perfectly suited for natural or man-made emergency and disaster management situations such as flood, earthquakes, tornadoes, or tsunami, multi-target search path planning for a team of rescue agents is known to be computationally hard, and most techniques developed so far come short to successfully estimate optimality gap. A novel mixed-integer linear programming (MIP) formulation is proposed to optimally solve the multi-target multi-agent discrete search and rescue (SAR) path planning problem. Aimed at maximizing cumulative probability of successful target detection, it captures anticipated feedback information associated with possible observation outcomes resulting from projected path execution, while modeling agent discrete actions over all possible moving directions. Problem modeling further takes advantage of network representation to encompass decision variables, expedite compact constraint specification, and lead to substantial problem-solving speed-up. The proposed MIP approach uses CPLEX optimization machinery, efficiently computing near-optimal solutions for practical size problems, while giving a robust upper bound obtained from Lagrangean integrality constraint relaxation. Should eventually a target be positively detected during plan execution, a new problem instance would simply be reformulated from the current state, and then solved over the next decision cycle. A computational experiment shows the feasibility and the value of the proposed approach.
Genetic Algorithm for In-Theatre Military Logistics Search-and-Delivery Path Planning
Discrete search path planning in time-constrained uncertain environment relying upon imperfect sensors is known to be hard, and current problem-solving techniques proposed so far to compute near real-time efficient path plans are mainly bounded to provide a few move solutions. A new information-theoretic –based open-loop decision model explicitly incorporating false alarm sensor readings, to solve a single agent military logistics search-and-delivery path planning problem with anticipated feedback is presented. The decision model consists in minimizing expected entropy considering anticipated possible observation outcomes over a given time horizon. The model captures uncertainty associated with observation events for all possible scenarios. Entropy represents a measure of uncertainty about the searched target location. Feedback information resulting from possible sensor observations outcomes along the projected path plan is exploited to update anticipated unit target occupancy beliefs. For the first time, a compact belief update formulation is generalized to explicitly include false positive observation events that may occur during plan execution. A novel genetic algorithm is then proposed to efficiently solve search path planning, providing near-optimal solutions for practical realistic problem instances. Given the run-time performance of the algorithm, natural extension to a closed-loop environment to progressively integrate real visit outcomes on a rolling time horizon can be easily envisioned. Computational results show the value of the approach in comparison to alternate heuristics.
Development of Optimized User Interface of Public Transit Navigator for a Smartphone
We develop a new interface for Bus-Net which is
optimized for a smartphone. We are continuing to develop the shortest
path planning system of public transportation called "Bus-Net" in
Tottori prefecture as web application to improve the usability of
public transportation. Recent trend of computing platform, however
has shifted to an advanced mobile device called a smartphone such as
iPhone and Android in Japan. A smartphone has different characters
with existing feature phone in terms of OS, large touche panel, and
several other features. We derive a guideline to design the new interface
for a smartphone to full use of the functionality. The guideline is
about simplicity of user-s operation, location awareness and usability.
We developed the new interface for “Bus-Net" on iPhone referring
to the guideline. Due to the evaluation, the application interface we
developed is better than the existing web-based interface in terms of
Providing On-Demand Path and Arrival Time Information Considering Realtime Delays of Buses
This paper demonstrates the bus location system for
the route bus through the experiment in the real environment. A
bus location system is a system that provides information such as
the bus delay and positions. This system uses actual services and
positions data of buses, and those information should match data
on the database. The system has two possible problems. One, the
system could cost high in preparing devices to get bus positions.
Two, it could be difficult to match services data of buses. To avoid
these problems, we have developed this system at low cost and short
time by using the smart phone with GPS and the bus route system.
This system realizes the path planning considering bus delay and
displaying position of buses on the map. The bus location system
was demonstrated on route buses with smart phones for two months.
Intelligent Path Planning for Rescue Robot
In this paper, a heuristic method for simultaneous
rescue robot path-planning and mission scheduling is introduced
based on project management techniques, multi criteria decision
making and artificial potential fields path-planning. Groups of
injured people are trapped in a disastrous situation. These people are
categorized into several groups based on the severity of their
situation. A rescue robot, whose ultimate objective is reaching
injured groups and providing preliminary aid for them through a path
with minimum risk, has to perform certain tasks on its way towards
targets before the arrival of rescue team. A decision value is assigned
to each target based on the whole degree of satisfaction of the criteria
and duties of the robot toward the target and the importance of
rescuing each target based on their category and the number of
injured people. The resulted decision value defines the strength of the
attractive potential field of each target. Dangerous environmental
parameters are defined as obstacles whose risk determines the
strength of the repulsive potential field of each obstacle. Moreover,
negative and positive energies are assigned to the targets and
obstacles, which are variable with respects to the factors involved.
The simulation results show that the generated path for two cases
studies with certain differences in environmental conditions and
other risk factors differ considerably.
Adaptive Path Planning for Mobile Robot Obstacle Avoidance
Generally speaking, the mobile robot is capable of
sensing its surrounding environment, interpreting the sensed
information to obtain the knowledge of its location and the
environment, planning a real-time trajectory to reach the object. In
this process, the issue of obstacle avoidance is a fundamental topic to
be challenged. Thus, an adaptive path-planning control scheme is
designed without detailed environmental information, large memory
size and heavy computation burden in this study for the obstacle
avoidance of a mobile robot. In this scheme, the robot can gradually
approach its object according to the motion tracking mode, obstacle
avoidance mode, self-rotation mode, and robot state selection. The
effectiveness of the proposed adaptive path-planning control scheme
is verified by numerical simulations of a differential-driving mobile
robot under the possible occurrence of obstacle shapes.
Development of User Interface for Path Planning System for Bus Network and On-demand Bus Reservation System
Route bus system is one of fundamental transportation device for aged people and students, and has an important role in every province. However, passengers decrease year by year, therefore the authors have developed the system called "Bus-Net" as a web application to sustain the public transport. But there are two problems in Bus-Net. One is the user interface that does not consider the variety of the device, and the other is the path planning system that dose not correspond to the on-demand bus. Then, Bus-Net was improved to be able to utilize the variety of the device, and a new function corresponding to the on-demand bus was developed.
Development of User Interface for Multiple Devices Connecting Path Planning System for Bus Network
Recently, web services to access from many type devices
are often used. We have developed the shortest path planning
system called "Bus-Net" in Tottori prefecture as a web application
to sustain the public transport. And it used the same user interface
for both devices. To support both devices, the interface cannot use
Thus, we developed the method that use individual user interface
for each device type to improve its convenience. To be concrete,
we defined formats of condition input to the path planning system
and result output from it and separate the system into the request
processing part and user interface parts that depend on device types.
By this method, we have also developed special device for Bus-Net
Mobile Robot Path Planning in a 2-Dimentional Mesh
A topologically oriented neural network is very
efficient for real-time path planning for a mobile robot in changing
environments. When using a recurrent neural network for this
purpose and with the combination of the partial differential equation
of heat transfer and the distributed potential concept of the network,
the problem of obstacle avoidance of trajectory planning for a
moving robot can be efficiently solved. The related dimensional
network represents the state variables and the topology of the robot's
working space. In this paper two approaches to problem solution are
proposed. The first approach relies on the potential distribution of
attraction distributed around the moving target, acting as a unique
local extreme in the net, with the gradient of the state variables
directing the current flow toward the source of the potential heat. The
second approach considers two attractive and repulsive potential
sources to decrease the time of potential distribution. Computer
simulations have been carried out to interrogate the performance of
the proposed approaches.
Optimal Path Planning under Priori Information in Stochastic, Time-varying Networks
A novel path planning approach is presented to solve
optimal path in stochastic, time-varying networks under priori traffic
information. Most existing studies make use of dynamic programming
to find optimal path. However, those methods are proved to
be unable to obtain global optimal value, moreover, how to design
efficient algorithms is also another challenge.
This paper employs a decision theoretic framework for defining
optimal path: for a given source S and destination D in urban transit
network, we seek an S - D path of lowest expected travel time
where its link travel times are discrete random variables. To solve
deficiency caused by the methods of dynamic programming, such as
curse of dimensionality and violation of optimal principle, an integer
programming model is built to realize assignment of discrete travel
time variables to arcs. Simultaneously, pruning techniques are also
applied to reduce computation complexity in the algorithm. The final
experiments show the feasibility of the novel approach.
A Valley Detection for Path Planning
This paper presents a constrained valley detection
algorithm. The intent is to find valleys in the map for the path planning
that enables a robot or a vehicle to move safely. The constraint to the
valley is a desired width and a desired depth to ensure the space for
movement when a vehicle passes through the valley. We propose an
algorithm to find valleys satisfying these 2 dimensional constraints.
The merit of our algorithm is that the pre-processing and the
post-processing are not necessary to eliminate undesired small valleys.
The algorithm is validated through simulation using digitized
A Cooperative Multi-Robot Control Using Ad Hoc Wireless Network
In this paper, a Cooperative Multi-robot for Carrying
Targets (CMCT) algorithm is proposed. The multi-robot team
consists of three robots, one is a supervisor and the others are
workers for carrying boxes in a store of 100×100 m2. Each robot has
a self recharging mechanism. The CMCT minimizes robot-s worked
time for carrying many boxes during day by working in parallel. That
is, the supervisor detects the required variables in the same time
another robots work with previous variables. It works with
straightforward mechanical models by using simple cosine laws. It
detects the robot-s shortest path for reaching the target position
avoiding obstacles by using a proposed CMCT path planning
(CMCT-PP) algorithm. It prevents the collision between robots
during moving. The robots interact in an ad hoc wireless network.
Simulation results show that the proposed system that consists of
CMCT algorithm and its accomplished CMCT-PP algorithm
achieves a high improvement in time and distance while performing
the required tasks over the already existed algorithms.
Design and Implementation a Fully Autonomous Soccer Player Robot
Omni directional mobile robots have been popularly
employed in several applications especially in soccer player robots
considered in Robocup competitions. However, Omni directional
navigation system, Omni-vision system and solenoid kicking
mechanism in such mobile robots have not ever been combined. This
situation brings the idea of a robot with no head direction into
existence, a comprehensive Omni directional mobile robot. Such a
robot can respond more quickly and it would be capable for more
sophisticated behaviors with multi-sensor data fusion algorithm for
global localization base on the data fusion. This paper has tried to
focus on the research improvements in the mechanical, electrical and
software design of the robots of team ADRO Iran. The main
improvements are the world model, the new strategy framework,
mechanical structure, Omni-vision sensor for object detection, robot
path planning, active ball handling mechanism and the new kicker
design, , and other subjects related to mobile robot
Mobile Robot Path Planning Utilizing Probability Recursive Function
In this work a software simulation model has been
proposed for two driven wheels mobile robot path planning; that can
navigate in dynamic environment with static distributed obstacles.
The work involves utilizing Bezier curve method in a proposed N
order matrix form; for engineering the mobile robot path. The Bezier
curve drawbacks in this field have been diagnosed. Two directions:
Up and Right function has been proposed; Probability Recursive
Function (PRF) to overcome those drawbacks.
PRF functionality has been developed through a proposed;
obstacle detection function, optimization function which has the
capability of prediction the optimum path without comparison
between all feasible paths, and N order Bezier curve function that
ensures the drawing of the obtained path.
The simulation results that have been taken showed; the mobile
robot travels successfully from starting point and reaching its goal
point. All obstacles that are located in its way have been avoided.
This navigation is being done successfully using the proposed PRF
Geometry Design Supported by Minimizing and Visualizing Collision in Dynamic Packing
This paper presents a method to support dynamic
packing in cases when no collision-free path can be found. The
method, which is primarily based on path planning and shrinking of
geometries, suggests a minimal geometry design change that results
in a collision-free assembly path. A supplementing approach to
optimize geometry design change with respect to redesign cost is
described. Supporting this dynamic packing method, a new method
to shrink geometry based on vertex translation, interweaved with
retriangulation, is suggested. The shrinking method requires neither
tetrahedralization nor calculation of medial axis and it preserves the
topology of the geometry, i.e. holes are neither lost nor introduced.
The proposed methods are successfully applied on industrial
Unknown Environment Representation for Mobile Robot Using Spiking Neural Networks
In this paper, a model of self-organizing spiking neural networks is introduced and applied to mobile robot environment representation and path planning problem. A network of spike-response-model neurons with a recurrent architecture is used to create robot-s internal representation from surrounding environment. The overall activity of network simulates a self-organizing system with unsupervised learning. A modified A* algorithm is used to find the best path using this internal representation between starting and goal points. This method can be used with good performance for both known and unknown environments.
Optimal Path Planner for Autonomous Vehicles
In this paper a real-time trajectory generation algorithm for computing 2-D optimal paths for autonomous aerial vehicles has been discussed. A dynamic programming approach is adopted to compute k-best paths by minimizing a cost function. Collision detection is implemented to detect intersection of the paths with obstacles. Our contribution is a novel approach to the problem of trajectory generation that is computationally efficient and offers considerable gain over existing techniques.
Path Planning of a Robot Manipulator using Retrieval RRT Strategy
This paper presents an algorithm which extends the rapidly-exploring random tree (RRT) framework to deal with change of the task environments. This algorithm called the Retrieval RRT Strategy (RRS) combines a support vector machine (SVM) and RRT and plans the robot motion in the presence of the change of the surrounding environment. This algorithm consists of two levels. At the first level, the SVM is built and selects a proper path from the bank of RRTs for a given environment. At the second level, a real path is planned by the RRT planners for the given environment. The suggested method is applied to the control of KUKA™,, a commercial 6 DOF robot manipulator, and its feasibility and efficiency are demonstrated via the cosimulatation of MatLab™, and RecurDyn™,.
Memetic Algorithm Based Path Planning for a Mobile Robot
In this paper, the problem of finding the optimal collision free path for a mobile robot, the path planning problem, is solved using an advanced evolutionary algorithm called memetic algorithm. What is new in this work is a novel representation of solutions for evolutionary algorithms that is efficient, simple and also compatible with memetic algorithm. The new representation makes it possible to solve the problem with a small population and in a few generations. It also makes the genetic operator simple and allows using an efficient local search operator within the evolutionary algorithm. The proposed algorithm is applied to two instances of path planning problem and the results are available.