China
Africa
Explore chapters and articles related to this topic
Architecture
Published in Hanky Sjafrie, Introduction to Self-Driving Vehicle Technology, 2019
Route planning typically uses special algorithms for solving a common graph theory problem called the shortest path problem. The problem can be defined as finding the shortest path between two nodes in a graph. One of the best-known shortest path algorithms is Dijkstra’s algorithm [6] as shown in Figure 4.1. The algorithm starts by initializing the distance value of all nodes to infinity. For all directly reachable nodes from the starting node a new distance value or cost is calculated, and the value is updated if the distance is shorter. This process iterates through the entire graph until all nodes have been traversed. The shortest path to any destination can now be determined by summing the cost of the node and the set of registered edges to reach that node. Faster algorithms, such as Contraction Hierarchies [9], perform some precomputation steps to speed up the process.
Performance Modeling and Analysis Using VHDL and SystemC
Published in Wai-Kai Chen, Computer Aided Design and Design Automation, 2018
Robert H. Klenke, Jonathan A. Andrews, James H. Aylor
The search for the shortest path utilizes a well-known algorithm. Search algorithms exist for both single-source shortest path and all-pairs shortest path. One of the first and most commonly used algorithms is Dijkstra’s algorithm [46], which finds the shortest path from a specified node to any other node in the graph. The search for all-pairs shortest path is also a well-investigated problem. One such algorithm by Floyd [47] is based on work by Warshall [48]. Its computation complexity is O(n3) when n is the number of nodes in the graph, which makes it quite practical for moderate-sized graphs. The implementation of this algorithm is based on Boolean matrix multiplication and the actual realization of all-pairs shortest paths can be stored in an n × n matrix. Utilizing this algorithm required some enhancements to make it applicable to mixed-level modeling. For example, if some of the inputs to the interpreted element are known (from the performance model), then the path should include transitions that include these known input values.
Graph theory based optimum routing path selection method for wireless sensor network
Published in Debatosh Guha, Badal Chakraborty, Himadri Sekhar Dutta, Computer, Communication and Electrical Technology, 2017
Bobby Sharma, Nitunjit Brahma, Himangshu Choudhury
Due to lack of energy, nodes in WSN may behave abnormally which finally effects the objective of WSN. Energy Efficiency is important role of the Wireless Sensor Networks Researchers (Kannadhasan 2013, Lai 2009). The shortest path problem for routing is one of the classical problem. By identifying shortest path, it tries to minimise the cost. Out of several traditional shortest path algorithms, BFS, Dijkstra’s, Bellman Ford algorithms etc. are popular. For a centralised as well as client-server based architecture, such algorithms are very much useful. But for autonomous network, such algorithm requires some additional processing statements by which it can understand the shortest path of autonomous network. In (Buratti 2011), authors mentioned that vertex covering plays an important role in link failure monitoring, location identification, clustering and data aggregation etc.
A cloud-fog architecture for physical-internet-enabled supply chain
Published in Supply Chain Forum: An International Journal, 2022
Mansour Mededjel, Ghalem Belalem, Abdelkader Neki
Shortest-path search approaches can be classified into two broad categories: those based on exact algorithms such as the ones introduced by Bellman-Ford, Dijkstra and Floyd-Warshall (Bellman 1958; Dijkstra 1959; Floyd 1962); and those based on heuristics to speed up the solution search. The application of a heuristic approach is more advocated in logistics and transportation applications. This is due to the various requirements related to this kind of application, such as finding an immediate (or real-time) solution, or the need to repeatedly recalculate the best path in the case of distributed routing for example. Accuracy is also important in this case. A balance between efficiency and accuracy would be a suitable solution that can be achieved by the A-star algorithm (Hart, Nilsson, and Raphael 1968). This algorithm, which combines the heuristic approach based on BFS (Best First Search) and the formal approach based on the Dijkstra algorithm, is the most popular of all heuristic algorithms.
Approach an autonomous vessel as a single robot with Robot Operating System in virtual environment
Published in Journal of International Maritime Safety, Environmental Affairs, and Shipping, 2022
Jaewoo Choi, Byongug Jeong, Gerasimos Theotokatos, Tahsin Tezdogan
A-star, Dijkstra, dynamic augmented multi-object particle swarm optimisation (PSO), and EEA algorithms have been developed and often applied for global navigation. Both A-start and Dijkstra are grid map-based path planning, which has benefits in computation time and avoidance of local optimum. A Dijkstra path algorithm was introduced in 1959 by EW Dijkstra, which was to find the shortest routes between nodes. The Dijkstra algorithm selects the node with the smallest sum of weights from the starting node to the current node and includes the path in the shortest path. This process is repeated until all nodes are selected. Searching all the nodes makes this algorithm inefficient. The A-star algorithm is proposed by improving the inefficiency of the Dijkstra algorithm. A-star algorithm gives priority to nodes that are supposed to be better than others by using a heuristic function. Because of this, the A-star algorithm has higher efficiency. Even though the earlier A-star algorithm only targets minimising the path length in a grid map, the algorithm has been improved. In order to overcome the weakness of the A-star algorithm that the path does not conform with the motion constraint of the robot, enhanced A-star algorithms considering orientation restriction were proposed by Fernandes et al. and Wang et al (Fernandes et al. 2015; Wang and Xiang 2018).
Exploring public bicycle network structure based on complex network theory and shortest path analysis: the public bicycle system in Yixing, China
Published in Transportation Planning and Technology, 2019
Sheng Wei, Jiangang Xu, Haitao Ma
The shortest path problem is a classical algorithm problem in graph theory, which aims to find the shortest path between two nodes in a graph (composed of nodes and paths). Many shortest path algorithms have been proposed in the literature, such as the Dijkstra search algorithm (cf. Ramalingam and Reps 1996). In this paper, in order to improve accuracy, the shortest path analysis of the two stations is carried out using Applications Programming Interfaces (APIs) of the Highmoralmap map, which provides accurate road data and an algorithm for computing the shortest path. The processes are as follows. First, convert the topographic map coordinates of the public bicycle stations to the Highmoralmap map projection coordinates and then calculate the shortest path between two public bicycle stations using the APIs of the Highmoralmap map.