With the continuous development and application needs of robots, games and intelligent navigation, maze-solving algorithms have also begun to be researched in relation to traditional graph-search algorithms. The three maze-solving algorithms and their corresponding results in this paper are DFS, BFS and A*, and they are all based on graph-search methods for 2D-grid mazes. A* is based on the Manhattan distance. Experiments are carried out on the three types of mazes (sparse, dense and complex) and the three scales (10x10, 20x20 and 50x50), and the main indicators are execution time, path length, visited nodes and scalability. BFS and A* both return the shortest path; however, A* has visited fewer nodes than BFS. For example, 419 vs. 1480 in the 50x50 maze; DFS can find the maze in the shortest time but has a longer path. As OCaml has pattern matching and recursion, it can be used to implement the above search algorithm.

Show more

The classical helm graph is obtained from a wheel graph by attaching a single pendant edge to each vertex on its outer cycle. While the chromatic index of the classical helm graph has been determined previously, that for nonuniform pendant extensions remains unexplored. In this paper, we introduce the asymmetric pendant helm graph, a natural generalization in which each outer vertex may carry an arbitrary number of pendant edges. We prove that every asymmetric pendant helm graph is Class 1, with the chromatic index equal to the maximum degree. The proof is constructive and yields an optimal linear-time edge coloring algorithm. As special cases, the result recovers known conclusions for classical helm graphs, wheel graphs, and uniform multi-pendant helm graphs. We further validate the proposed construction computationally using ten representative graph instances.

Show more

Robot path planning is a fundamental problem in robotics enabling autonomous robots to navigate safely, efficiently and naturally from a start position to a target position. In real robotic systems, path planning is not only about finding a collision-free path, but also about generating motions that satisfy the robot's physical, sensory, and task constraints. In this essay, the main robot path planning methods, including graph search, artificial potential field methods, sampling-based planning, local obstacle avoidance, and trajectory optimization are reviewed. Their respective strengths, limitations, and applicable scenarios are examined, with particular attention to how these approaches address issues such as computational complexity, environmental structure, and real-time responsiveness. It also addresses present day issues such as uncertainty, dynamic environments, computational efficiency and physical feasibility, emphasizing that no single method is sufficient for all robotic applications. Practical systems increasingly rely on hierarchical integration to balance global navigation with local reactivity. Finally, the essay argues that the future of robot path planning will be dominated by hybrid systems that combine global planning, local replanning, optimization, and learning-based prediction, enabling robots to operate more safely, intelligently, and adaptively in complex real-world environments.

Show more

This paper aims to investigate and solve maze-solving problems by implementing the Breadth-First Search (BFS) algorithm and the Left-Hand Wall-Following algorithm, providing references for maze navigation of small embedded robots. In this study, the OCaml programming language is adopted. This paper implements both the BFS and Left-Hand Wall-Following algorithms to solve three mazes of different sizes (30×28, 30×17, 30×16). The total moving steps and the shortest valid paths are recorded. The time and space complexity of the two algorithms are calculated, and comparative tables are generated for analysis. Experiments show that the Left-Hand Wall-Following algorithm has a constant space complexity of O(1) with stable memory consumption. However, its generated path length can reach 2.5 to 10 times the theoretical shortest path, and it is only applicable to simple mazes. In contrast, BFS can stably output globally optimal paths and adapt to all types of complex mazes, yet its memory overhead grows linearly with maze size. The two algorithms fit distinct application scenarios and can be selected flexibly according to equipment memory constraints and requirements for optimal paths.

Show more