Search

A comparative study was conducted using Python and Pmaze to evaluate the performance of DFS, BFS, and A* search algorithms in path planning for a maze. The main objective of the project was to compare the efficiency of these algorithms in terms of path cost and algorithmic complexity. No physical robot was used in this study as it focused solely on the analysis of search algorithms. This study contributes to the advancement of knowledge in the field of path planning by exploring different approaches for mazes using Python and Pmaze. [ABSTRACT FROM AUTHOR]

An optimized robot path-planning algorithm is required for various aspects of robot movements in applications. The efficacy of the robot path-planning model is vulnerable to the number of search nodes, path cost, and time complexity. The conventional A-star (A*) algorithm outperforms other grid-based algorithms because of its heuristic approach. However, the performance of the conventional A* algorithm is suboptimal for the time, space, and number of search nodes, depending on the robot motion block (RMB). To address these challenges, this paper proposes an optimal RMB with an adaptive cost function to improve performance. The proposed adaptive cost function keeps track of the goal node and adaptively calculates the movement costs for quickly arriving at the goal node. Incorporating the adaptive cost function with a selected optimal RMB significantly reduces the searches of less impactful and redundant nodes, which improves the performance of the A* algorithm in terms of the number of search nodes and time complexity. To validate the performance and robustness of the proposed model, an extensive experiment was conducted. In the experiment, an open-source dataset featuring various types of grid maps was customized to incorporate the multiple map sizes and sets of source-to-destination nodes. According to the experiments, the proposed method demonstrated a remarkable improvement of 93.98% in the number of search nodes and 98.94% in time complexity compared to the conventional A* algorithm. The proposed model outperforms other state-of-the-art algorithms by keeping the path cost largely comparable. Additionally, an ROS experiment using a robot and lidar sensor data shows the improvement of the proposed method in a simulated laboratory environment. [ABSTRACT FROM AUTHOR]

An optimized robot path-planning algorithm is required for various aspects of robot movements in applications. The efficacy of the robot path-planning model is vulnerable to the number of search nodes, path cost, and time complexity. The conventional A-star (A*) algorithm outperforms other grid-based algorithms because of its heuristic approach. However, the performance of the conventional A* algorithm is suboptimal for the time, space, and number of search nodes, depending on the robot motion block (RMB). To address these challenges, this paper proposes an optimal RMB with an adaptive cost function to improve performance. The proposed adaptive cost function keeps track of the goal node and adaptively calculates the movement costs for quickly arriving at the goal node. Incorporating the adaptive cost function with a selected optimal RMB significantly reduces the searches of less impactful and redundant nodes, which improves the performance of the A* algorithm in terms of the number of search nodes and time complexity. To validate the performance and robustness of the proposed model, an extensive experiment was conducted. In the experiment, an open-source dataset featuring various types of grid maps was customized to incorporate the multiple map sizes and sets of source-to-destination nodes. According to the experiments, the proposed method demonstrated a remarkable improvement of 93.98% in the number of search nodes and 98.94% in time complexity compared to the conventional A* algorithm. The proposed model outperforms other state-of-the-art algorithms by keeping the path cost largely comparable. Additionally, an ROS experiment using a robot and lidar sensor data shows the improvement of the proposed method in a simulated laboratory environment.

It might be quite difficult to search for words or phrases in the many file formats that are based on various operating systems. To deal with this level of heterogeneity in different file systems, several academics have put up a number of alternative strategies. Given that data is stored in various formats and is controlled by several operating systems, such solutions, however, proved to be extremely time-consuming. The suggested techniques work best when the data is kept in a single source. The idea of bottlenecking and the resulting heterogeneity in file systems are two main issues with looking for a certain collection of data objects (folder, file, or directory) across many platforms (Windows, Linux, and so forth). We made an effort to suggest fundamental searching methods that may deal with the issue of heterogeneity while increasing efficiency and maintaining dependability. Our method makes use of a concept known as tree-based breadth first search (BFS) and depth first search techniques (DFS) to limit to an absolute minimum the amount of I/O operations that might be required in the heterogeneous environment. The experiment was run on Windows and Linux computers, and it was discovered that by using these strategies, the heterogeneity issues may be greatly decreased, leading to some encouraging outcomes. [ABSTRACT FROM AUTHOR]

The spanning trees of a graph constructed by the graph searches BFS and DFS are some of the most elementary structures in algorithmic graph theory. BFS-trees are first-in trees, i.e., every vertex is connected to its first visited neighbor. DFS-trees are last-in trees, i.e., every vertex is connected to its most recently visited neighbor. It is known since the 1980s that the problem of deciding whether a given spanning tree of a graph is a BFS-tree or a DFS-tree can be solved in linear time. Here, we will show that swapping the search-tree paradigms between these searches makes the problem hard, i.e., it is NP -complete to decide whether a spanning tree of a graph is a first-in-tree of a DFS or a last-in-tree of a BFS. To the best of our knowledge the latter result is the first hardness result for the recognition of last-in-trees for some graph search. Additionally, we study the complexity of both problems on split graphs. • Hardness of the recognition of last-in trees of BFS. • Hardness of the recognition of first-in trees of DFS. • Linear-time algorithm for the recognition of first-in trees of DFS on split graphs. • Better understanding of the last-in trees of generic search. [ABSTRACT FROM AUTHOR]

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. [ABSTRACT FROM AUTHOR]

Carpoolng is a sysytem which the passenger can share the vehicale nad by this means the traffic also duces due to red ucing the no of vehicle on the the roa the government government organization has started the implementatio of carpooling system. To implement this system various Approaches has beendeveloped but becomes essentials that the Selection of optimal distance for pickingthe ger for improvi passenger for improving the recital of the system so in the research work, we use graph traversal technique to find the effective path and it is testedto find the opiimal solution The experimentl results of the proposed metdodology our approac showng approa more efficient than the existing approach. [ABSTRACT FROM AUTHOR]

Research on space efficient graph algorithms, particularly for st-connectivity, has a long history including the celebrated polynomial time, O(lg n) bits1 algorithm in undirected graphs by Reingold J. JACM. 55(4) (2008), and polynomial time, n/2Θ(lgn) bits algorithm in directed graphs by Barnes et al. SICOMP. 27(5), 1273-1282 (1998). Recent works by Asano et al. ISAAC (2014) and Elmasry et al. STACS (2015), reconsidered classical fundamental graph algorithms focusing on improving the space complexity. Elmasry et al. gave, among others, an implementation of breadth first search (BFS) in a graph G with n vertices and m edges, taking the optimal O(m + n) time using O(n) bits improving the naïve O(n lg n) bits implementation. Similarly, Asano et al. provided space efficient implementations for performing depth first search (DFS) in a graph G. We continue this line of work focusing on improving the space requirement for implementing a few classical graph algorithms. Our first result is a simple data structure that can maintain any subset S of a universe of u elements using just u + o(u) bits and supports in constant time, apart from the standard insert, delete and membership queries, the operation findany that finds and returns any element of the set (or outputs that the set is empty). It can also enumerate all elements present currently in the set in no particular order in O(k + 1) time where k is the number of elements currently belonging to the set. While this data structure supports a weaker set of operations than that of Elmasry et al. STACS (2015), it is simple, more space efficient and is sufficient to support a BFS implementation optimally in O(m + n) time using at most 2n + o(n) bits. Later, we further improve the space requirement of BFS to at most n lg 3 + o(n) bits albeit with a slight increase in running time to O(m lg nf(n)) time where f(n) is any extremely slow growing function of n, and the o term in the space is a function of f(n). We also discuss a similar time-space tradeoff result for finding a minimum weight spanning tree of a weighted (bounded by polynomial in n) undirected graph using n + O(n/f(n)) bits and O(m lg nf(n)) time, for any function f(n) such that 1 ≤ f(n) ≤ n. For DFS in a graph G, we provide an implementation taking O(m + n) time and O(n lg m/n) bits. This partially answers at least for sparse graphs, a question asked by Asano et al. ISAAC (2014) whether DFS can be performed in O (m + n) time and using O(n) bits, and also simultaneously improves the DFS result of Elmasry et al. STACS (2015). Using our DFS algorithm and other careful implementations, we show how one can also test for biconnectivity, 2-edge connectivity, and find cut vertices and bridges of a given undirected graph within the same time and space bounds; earlier classical linear time algorithms for these problems used Ω(n lg n) bits of space. [ABSTRACT FROM AUTHOR]

This paper presents the investigation and comparison of TLC model checking method (TLA Checker) properties. There are two different approaches to method usage which are considered. The first one consists of a transition system states attendance by breadth-first search (BFS), and the second one by depth-first search (DFS). The Kripke structure has been chosen as a transition system model. A case study has been conducted, where composite web service usage scenario has been considered. Obtained experimental results are aimed at increasing the effectiveness of TLA+ specifications automated verification.

In this paper, we consider the problem of the recognition of various kinds of orderings produced by graph searches. To this aim, we introduce a new framework, the Tie-Breaking Label Search (TBLS), in order to handle a broad variety of searches. This new model is based on partial orders defined on the label set and it unifies the General Label Search (GLS) formalism of Krueger et al. (2011), and the “pattern-conditions” formalism of Corneil and Krueger (2008). It allows us to derive some general properties including new pattern-conditions (yielding memory-efficient certificates) for many usual searches, including BFS, DFS, LBFS and LDFS. Furthermore, the new model allows easy expression of multi-sweep uses of searches that depend on previous (search) orderings of the graph’s vertex set. [ABSTRACT FROM AUTHOR]

This paper presents the investigation and comparison of TLC model checking method (TLA Checker) properties. There are two different approaches to method usage which are considered. The first one consists of a transition system states attendance by breadth-first search (BFS), and the second one by depth-first search (DFS). The Kripke structure has been chosen as a transition system model. A case study has been conducted, where composite web service usage scenario has been considered. Obtained experimental results are aimed at increasing the effectiveness of TLA+ specifications automated verification. [ABSTRACT FROM AUTHOR]

The goal of real-time mobile robots is to travel in the shortest path between two points in a navigation environment. Autonomous navigation allows robots to planning this path without the need for human intervention. In this paper, Autonomous navigation mobile robot system has been simulated by MATLAB which a camera is used to snapshotting robot environment represented by maze while image processing techniques are used for extracting maze parameters. These parameters are used to planning the shortest path between start point and target based on Depth-first Search (DFS) and Breadth-first Search (BFS) searching algorithms.

End-vertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is interesting to consider if these vertices can be recognized in polynomial time or not, as first studied in Corneil, Köhler and Lanlignel 2010. A graph search is a mechanism for systematically visiting the vertices of a graph. At each step of a graph search, the key point is the choice of the next vertex to be explored. Graph searches only differ by this selection mechanism during which a tie-break rule is used. In this paper we study how the choice of the tie-break in case of equality during the search, for a given graph search including the classic ones such as BFS and DFS, can determine the complexity of the end-vertex problem. In particular we prove a counterintuitive NP-completeness result for Breadth First Search solving a problem raised in Corneil, Köhler and Lanlignel 2010. [ABSTRACT FROM AUTHOR]

We consider an alternative expression of the Shapley value that reveals a system of compensations: each player receives an equal share of the worth of each coalition he belongs to, and has to compensate an equal share of the worth of any coalition he does not belong to. We give a representation in terms of formation of the grand coalition according to an ordering of the players and define the corresponding compensation vector. Then, we generalize this idea to cooperative games with a communication graph in order to construct new allocation rules called the compensation solutions. Firstly, we consider cooperative games with arbitrary graphs and construct rooted spanning trees (see Demange, J Political Econ 112:754-778, ) instead of orderings of the players by using the classical algorithms DFS and BFS. If the graph is complete, we show that the compensation solutions associated with DFS and BFS coincide with the Shapley value and the equal surplus division respectively. Secondly, we consider cooperative games with a forest (cycle-free graph) and all its rooted spanning trees. The compensation solution is characterized by component efficiency and relative fairness. The latter axiom takes into account the relative position of a player with respect to his component in the communication graph. [ABSTRACT FROM AUTHOR]

We consider communication situations games being the combination of a TU-game and a communication graph. We study the average tree (AT) solutions introduced by Herings et al. (Games Econ Behav 62:77-92, 2008; Games Econ Behav 68:626-633, 2010). The AT solutions are defined with respect to a set, say $${\fancyscript{T}}$$, of rooted spanning trees of the communication graph. We prove the following results. Firstly, the AT solution with respect to $${\fancyscript{T}}$$ is a Harsanyi solution if and only if $${\fancyscript{T}}$$ is a subset of the set of trees introduced in Herings et al. (2010). Secondly, the latter set is constructed by the classical DFS algorithm and the associated AT solution coincides with the Shapley value when the communication graph is complete. Thirdly, the AT solution with respect to trees constructed by the other classical algorithm BFS yields the equal surplus division when the communication graph is complete. [ABSTRACT FROM AUTHOR]