**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**2092

# Search results for: optimal path

##### 2092 Optimal Path Planning under Priori Information in Stochastic, Time-varying Networks

**Authors:**
Siliang Wang,
Minghui Wang,
Jun Hu

**Abstract:**

**Keywords:**
pruning method,
stochastic,
time-varying networks,
optimal path planning.

##### 2091 Three-Dimensional Off-Line Path Planning for Unmanned Aerial Vehicle Using Modified Particle Swarm Optimization

**Authors:**
Lana Dalawr Jalal

**Abstract:**

**Keywords:**
Obstacle Avoidance,
Particle Swarm Optimization,
Three-Dimensional Path Planning Unmanned Aerial Vehicles.

##### 2090 An Approach to the Solving Non-Steiner Minimum Link Path Problem

**Authors:**
V. Tereshchenko,
A. Tregubenko

**Abstract:**

In this study we survey the method for fast finding a minimum link path between two arbitrary points within a simple polygon, which can pass only through the vertices, with preprocessing.

**Keywords:**
Minimum link path,
simple polygon,
Steiner points,
optimal algorithm.

##### 2089 Decomposition of Graphs into Induced Paths and Cycles

**Authors:**
I. Sahul Hamid,
Abraham V. M.

**Abstract:**

A decomposition of a graph G is a collection ψ of subgraphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path or an induced cycle in G, then ψ is called an induced path decomposition of G. The minimum cardinality of an induced path decomposition of G is called the induced path decomposition number of G and is denoted by πi(G). In this paper we initiate a study of this parameter.

**Keywords:**
Path decomposition,
Induced path decomposition,
Induced path decomposition number.

##### 2088 Optimal Path Planner for Autonomous Vehicles

**Authors:**
M. Imran Akram,
Ahmed Pasha,
Nabeel Iqbal

**Abstract:**

**Keywords:**
dynamic programming,
graph search,
path planning.

##### 2087 Memetic Algorithm Based Path Planning for a Mobile Robot

**Authors:**
Neda Shahidi,
Hadi Esmaeilzadeh,
Marziye Abdollahi,
Caro Lucas

**Abstract:**

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.

**Keywords:**
Path planning problem,
Memetic Algorithm,
Representation.

##### 2086 Optimization Based Obstacle Avoidance

**Authors:**
R. Dariani,
S. Schmidt,
R. Kasper

**Abstract:**

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.

**Keywords:**
Autonomous driving,
Obstacle avoidance,
Optimal
control,
Path planning.

##### 2085 Services-Oriented Model for the Regulation of Learning

**Authors:**
Mohamed Bendahmane,
Brahim Elfalaki,
Mohammed Benattou

**Abstract:**

One of the major sources of learners' professional difficulties is their heterogeneity. Whether on cognitive, social, cultural or emotional level, learners being part of the same group have many differences. These differences do not allow to apply the same learning process at all learners. Thus, an optimal learning path for one, is not necessarily the same for the other. We present in this paper a model-oriented service to offer to each learner a personalized learning path to acquire the targeted skills.

**Keywords:**
Service-oriented architecture,
learning path,
web service,
personalization,
trace analysis.

##### 2084 The Same or Not the Same - On the Variety of Mechanisms of Path Dependence

**Authors:**
Jürgen Beyer

**Abstract:**

**Keywords:**
path dependence,
increasing returns,
historicalinstitutionalism,
lock-in.

##### 2083 Efficient Design Optimization of Multi-State Flow Network for Multiple Commodities

**Authors:**
Yu-Cheng Chou,
Po Ting Lin

**Abstract:**

The network of delivering commodities has been an important design problem in our daily lives and many transportation applications. The delivery performance is evaluated based on the system reliability of delivering commodities from a source node to a sink node in the network. The system reliability is thus maximized to find the optimal routing. However, the design problem is not simple because (1) each path segment has randomly distributed attributes; (2) there are multiple commodities that consume various path capacities; (3) the optimal routing must successfully complete the delivery process within the allowable time constraints. In this paper, we want to focus on the design optimization of the Multi-State Flow Network (MSFN) for multiple commodities. We propose an efficient approach to evaluate the system reliability in the MSFN with respect to randomly distributed path attributes and find the optimal routing subject to the allowable time constraints. The delivery rates, also known as delivery currents, of the path segments are evaluated and the minimal-current arcs are eliminated to reduce the complexity of the MSFN. Accordingly, the correct optimal routing is found and the worst-case reliability is evaluated. It has been shown that the reliability of the optimal routing is at least higher than worst-case measure. Two benchmark examples are utilized to demonstrate the proposed method. The comparisons between the original and the reduced networks show that the proposed method is very efficient.

**Keywords:**
Multiple Commodities,
Multi-State Flow Network (MSFN),
Time Constraints,
Worst-Case Reliability (WCR)

##### 2082 Optimizing Network Latency with Fast Path Assignment for Incoming Flows

**Abstract:**

**Keywords:**
Latency,
Fast path assignment,
Bottleneck link.

##### 2081 Using Multi-Thread Technology Realize Most Short-Path Parallel Algorithm

**Authors:**
Chang-le Lu,
Yong Chen

**Abstract:**

**Keywords:**
Dijkstra algorithm,
parallel algorithms,
multi-thread
technology,
most short-path,
ratio.

##### 2080 Optimal and Critical Path Analysis of State Transportation Network Using Neo4J

**Authors:**
Pallavi Bhogaram,
Xiaolong Wu,
Min He,
Onyedikachi Okenwa

**Abstract:**

A transportation network is a realization of a spatial network, describing a structure which permits either vehicular movement or flow of some commodity. Examples include road networks, railways, air routes, pipelines, and many more. The transportation network plays a vital role in maintaining the vigor of the nation’s economy. Hence, ensuring the network stays resilient all the time, especially in the face of challenges such as heavy traffic loads and large scale natural disasters, is of utmost importance. In this paper, we used the Neo4j application to develop the graph. Neo4j is the world's leading open-source, NoSQL, a native graph database that implements an ACID-compliant transactional backend to applications. The Southern California network model is developed using the Neo4j application and obtained the most critical and optimal nodes and paths in the network using centrality algorithms. The edge betweenness centrality algorithm calculates the critical or optimal paths using Yen's *k*-shortest paths algorithm, and the node betweenness centrality algorithm calculates the amount of influence a node has over the network. The preliminary study results confirm that the Neo4j application can be a suitable tool to study the important nodes and the critical paths for the major congested metropolitan area.

**Keywords:**
Transportation network,
critical path,
connectivity reliability,
network model,
Neo4J application,
optimal path,
critical path,
edge betweenness centrality index,
node betweenness centrality index,
Yen’s k-shortest paths.

##### 2079 An UML Statechart Diagram-Based MM-Path Generation Approach for Object-Oriented Integration Testing

**Authors:**
Ruilian Zhao,
Ling Lin

**Abstract:**

MM-Path, an acronym for Method/Message Path, describes the dynamic interactions between methods in object-oriented systems. This paper discusses the classifications of MM-Path, based on the characteristics of object-oriented software. We categorize it according to the generation reasons, the effect scope and the composition of MM-Path. A formalized representation of MM-Path is also proposed, which has considered the influence of state on response method sequences of messages. .Moreover, an automatic MM-Path generation approach based on UML Statechart diagram has been presented, and the difficulties in identifying and generating MM-Path can be solved. . As a result, it provides a solid foundation for further research on test cases generation based on MM-Path.

**Keywords:**
MM-Path,
Message Sequence,
Object-Oriented Integration Testing,
Response Method Sequence,
UML Statechart Diagram.

##### 2078 Optimized Delay Constrained QoS Routing

**Authors:**
P. S. Prakash,
S. Selvan

**Abstract:**

**Keywords:**
QoS,
Delay,
Routing,
Optimization.

##### 2077 Induced Acyclic Path Decomposition in Graphs

**Authors:**
Abraham V. M.,
I. Sahul Hamid

**Abstract:**

**Keywords:**
Cycle decomposition,
Induced acyclic path decomposition,
Induced acyclic path decomposition number.

##### 2076 A Feasible Path Selection QoS Routing Algorithm with two Constraints in Packet Switched Networks

**Authors:**
P.S.Prakash,
S.Selvan

**Abstract:**

**Keywords:**
feasible path,
multiple constraints,
path selection,
QoS routing

##### 2075 The Frequency Graph for the Traveling Salesman Problem

**Authors:**
Y. Wang

**Abstract:**

**Keywords:**
Traveling salesman problem,
frequency graph,
local
optimal Hamiltonian path,
four vertices and three lines inequality.

##### 2074 Application of Heuristic Integration Ant Colony Optimization in Path Planning

**Authors:**
Zeyu Zhang,
Guisheng Yin,
Ziying Zhang,
Liguo Zhang

**Abstract:**

This paper mainly studies the path planning method based on ant colony optimization (ACO), and proposes heuristic integration ant colony optimization (HIACO). This paper not only analyzes and optimizes the principle, but also simulates and analyzes the parameters related to the application of HIACO in path planning. Compared with the original algorithm, the improved algorithm optimizes probability formula, tabu table mechanism and updating mechanism, and introduces more reasonable heuristic factors. The optimized HIACO not only draws on the excellent ideas of the original algorithm, but also solves the problems of premature convergence, convergence to the sub optimal solution and improper exploration to some extent. HIACO can be used to achieve better simulation results and achieve the desired optimization. Combined with the probability formula and update formula, several parameters of HIACO are tested. This paper proves the principle of the HIACO and gives the best parameter range in the research of path planning.

**Keywords:**
Ant colony optimization,
heuristic integration,
path planning

##### 2073 Robot Path Planning in 3D Space Using Binary Integer Programming

**Authors:**
Ellips Masehian,
Golnaz Habibi

**Abstract:**

**Keywords:**
3D C-space,
Binary Integer Programming (BIP),
Delaunay Tessellation,
Robot Motion Planning.

##### 2072 Comparison of GSA, SA and PSO Based Intelligent Controllers for Path Planning of Mobile Robot in Unknown Environment

**Authors:**
P. K. Panigrahi,
Saradindu Ghosh,
Dayal R. Parhi

**Abstract:**

Now-a-days autonomous mobile robots have found applications in diverse fields. An autonomous robot system must be able to behave in an intelligent manner to deal with complex and changing environment. This work proposes the performance of path planning and navigation of autonomous mobile robot using Gravitational Search Algorithm (GSA), Simulated Annealing (SA) and Particle Swarm optimization (PSO) based intelligent controllers in an unstructured environment. The approach not only finds a valid collision free path but also optimal one. The main aim of the work is to minimize the length of the path and duration of travel from a starting point to a target while moving in an unknown environment with obstacles without collision. Finally, a comparison is made between the three controllers, it is found that the path length and time duration made by the robot using GSA is better than SA and PSO based controllers for the same work.

**Keywords:**
Autonomous Mobile Robot,
Gravitational Search Algorithm,
Particle Swarm Optimization,
Simulated Annealing Algorithm.

##### 2071 Multiobjective Optimization Solution for Shortest Path Routing Problem

**Authors:**
C. Chitra,
P. Subbaraj

**Abstract:**

**Keywords:**
Multiobjective optimization,
Non-dominated SortingGenetic Algorithm,
Routing,
Weighted sum.

##### 2070 A Control Model for Improving Safety and Efficiency of Navigation System Based on Reinforcement Learning

**Authors:**
Almutasim Billa A. Alanazi,
Hal S. Tharp

**Abstract:**

Artificial Intelligence (AI), specifically Reinforcement Learning (RL), has proven helpful in many control path planning technologies by maximizing and enhancing their performance, such as navigation systems. Since it learns from experience by interacting with the environment to determine the optimal policy, the optimal policy takes the best action in a particular state, accounting for the long-term rewards. Most navigation systems focus primarily on "arriving faster," overlooking safety and efficiency while estimating the optimum path, as safety and efficiency are essential factors when planning for a long-distance journey. This paper represents an RL control model that proposes a control mechanism for improving navigation systems. Also, the model could be applied to other control path planning applications because it is adjustable and can accept different properties and parameters. However, the navigation system application has been taken as a case and evaluation study for the proposed model. The model utilized a Q-learning algorithm for training and updating the policy. It allows the agent to analyze the quality of an action made in the environment to maximize rewards. The model gives the ability to update rewards regularly based on safety and efficiency assessments, allowing the policy to consider the desired safety and efficiency benefits while making decisions, which improves the quality of the decisions taken for path planning compared to the conventional RL approaches.

**Keywords:**
Artificial intelligence,
control system,
navigation systems,
reinforcement learning.

##### 2069 A Nondominated Sorting Genetic Algorithm for Shortest Path Routing Problem

**Authors:**
C. Chitra,
P. Subbaraj

**Abstract:**

The shortest path routing problem is a multiobjective nonlinear optimization problem with constraints. This problem has been addressed by considering Quality of service parameters, delay and cost objectives separately or as a weighted sum of both objectives. Multiobjective evolutionary algorithms can find multiple pareto-optimal solutions in one single run and this ability makes them attractive for solving problems with multiple and conflicting objectives. This paper uses an elitist multiobjective evolutionary algorithm based on the Non-dominated Sorting Genetic Algorithm (NSGA), for solving the dynamic shortest path routing problem in computer networks. A priority-based encoding scheme is proposed for population initialization. Elitism ensures that the best solution does not deteriorate in the next generations. Results for a sample test network have been presented to demonstrate the capabilities of the proposed approach to generate well-distributed pareto-optimal solutions of dynamic routing problem in one single run. The results obtained by NSGA are compared with single objective weighting factor method for which Genetic Algorithm (GA) was applied.

**Keywords:**
Multiobjective optimization,
Non-dominated Sorting Genetic Algorithm,
Routing,
Weighted sum.

##### 2068 Module and Comodule Structures on Path Space

**Abstract:**

*kQ*, there is a trivial

*kQ*-module structure determined by the multiplication of path algebra

^{a}*kQ*and a trivial

^{a }*kQ*-comodule structure determined by the comultiplication of path coalgebra

^{c}*kQ*. In this paper, on path space

^{c}*kQ*, a nontrivial

*kQ*-module structure is defined, and it is proved that this nontrivial left

^{a}*kQ*-module structure is isomorphic to the dual module structure of trivial right

^{a}*kQ*-comodule. Dually, on path space

^{c}*kQ*, a nontrivial

*kQ*-comodule structure is defined, and it is proved that this nontrivial right

^{c}*kQ*-comodule structure is isomorphic to the dual comodule structure of trivial left

^{c}*kQ*-module. Finally, the trivial and nontrivial module structures on path space are compared from the aspect of submodule, and the trivial and nontrivial comodule structures on path space are compared from the aspect of subcomodule.

^{a}**Keywords:**
Quiver,
path space,
module,
comodule,
dual.

##### 2067 A Review on Comparative Analysis of Path Planning and Collision Avoidance Algorithms

**Authors:**
Divya Agarwal,
Pushpendra S. Bharti

**Abstract:**

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.

**Keywords:**
Autonomous mobile robots,
obstacle avoidance,
path planning,
and processing time.

##### 2066 Adding Edges between One Node and Every Other Node with the Same Depth in a Complete K-ary Tree

**Authors:**
Kiyoshi Sawada,
Takashi Mitsuishi

**Abstract:**

**Keywords:**
complete K-ary tree,
organization structure,
shortest path

##### 2065 The Problem of Using the Calculation of the Critical Path to Solver Instances of the Job Shop Scheduling Problem

**Authors:**
Marco Antonio Cruz-Chávez,
Juan Frausto-Solís,
Fernando Ramos-Quintana

**Abstract:**

A procedure commonly used in Job Shop Scheduling Problem (JSSP) to evaluate the neighborhoods functions that use the non-deterministic algorithms is the calculation of the critical path in a digraph. This paper presents an experimental study of the cost of computation that exists when the calculation of the critical path in the solution for instances in which a JSSP of large size is involved. The results indicate that if the critical path is use in order to generate neighborhoods in the meta-heuristics that are used in JSSP, an elevated cost of computation exists in spite of the fact that the calculation of the critical path in any digraph is of polynomial complexity.

**Keywords:**
Job Shop,
CPM,
critical path,
neighborhood,
meta-heuristic.

##### 2064 An Improved Transfer Logic of the Two-Path Algorithm for Acoustic Echo Cancellation

**Abstract:**

**Keywords:**
Acoustic echo cancellation,
Echo return lossenhancement (ERLE),
Two-path algorithm,
Transfer logic

##### 2063 A Characterized and Optimized Approach for End-to-End Delay Constrained QoS Routing

**Authors:**
P.S.Prakash,
S.Selvan

**Abstract:**

**Keywords:**
QoS,
Delay,
Routing,
Optimization