Path finding is an important sub task in mobile robotics and Homeland Security applications and has been subjected to extensive research. This paper analyses a variety of search algorithms used for path finding and planning. Using the Breve simulation environment, a general search algorithm and then the A algorithm have been implemented. An improvement to the A algorithm is introduced and presented. In this paper it has been proved through experimental results that the performance of the A algorithm improves considerably after adding an additional heuristic.
Dynamic path planning has also been implemented in this paper by allowing the vehicle to check for changes in the environment at every simulation time step and recalculate paths if there is a change in the environment. In the past ad-hoc sensor networks have been used in homeland security. In this paper ad-hoc sensor networks have been modeled using the patch class in the Breve simulation tool and path finding techniques have been used in this environment. Time and space complexity analysis of the various algorithms implemented in this paper have been presented.KEY WORDS Robotics, artificial intelligence, path planning, homeland security, search algorithms, sensor networks. 1.
Introduction The problem of dynamic collision free path planning is vital to mobile robots and robots used in homeland security applications. The area of homeland robotics has assumed a great importance in the present age and robots are now being used extensively to rescue survivors from dangerous environments and when dealing with hazardous substances.The robots are used for tasks that rescuers or canines are unable to perform, for example to either investigate in spaces that are too small for humans to pass through, or in areas consumed by fire with limited breathable air in an attempt to reach a survivable void. The output of a search algorithm is either a failure or a solution. The efficiency of a search algorithm can be evaluated in four ways [1] Search algorithms have been used extensively to solve various problems like the Queens problem, the dining philosophers problem etc.In this paper, we restrict ourselves to the use of search algorithms for path finding problems.
Path finding techniques can be grouped into local methods and global methods [2]. One well known local planning method is the potential field method. In this method the robot follows the gradient of a force field. The field is generated by attractive potentials from a start position towards a target and by repulsive potentials that point away from obstacles. The potential field method has a low computational requirement.
In contrast, global methods need complete information about the world and hence would require relatively large computational power. The probabilistic roadmap which is a skeletonization method offers more possible routes and thus deals better with wide open spaces. The graph is created by randomly generating a large number of configurations, and discarding those that do not fall into free space. We then join any nodes by an arc if it is easy to reach one node from the other. Theoretically this method is incomplete, because a bad choice of random points may leave us without any paths from the start to the target [3].
1. 2 Simulation The Breve simulation environment was used to implement path finding techniques [5]. Breve is a free, open-source software package which makes it easy to build 3D simulations of decentralized systems and artificial life organisms. Time complexity analysis of the different search algorithms to find optimal paths was performed using a timer function in the Steve language, which is part of Breve. Time complexity analysis of the various search algorithms showed the efficiency of the different algorithms. Space complexity analysis of the search algorithms was also performed.
Space complexity analysis showed not only the efficiency of the different algorithms but also shows why a particular algorithm fails. Dynamic path finding and dynamic placement of sensors (light sensitive objects in the simulation) were also used in the simulation. 1. 3 Outline of the paper This paper is organised as follows. The search algorithms and heuristics implemented in this paper are discussed briefly in section 2.
Section 3 gives a short description of the aspects of Homeland security implemented in this paper.Section 4 discusses the details of the implementation done using Breve. A few snapshots of the simulation performed in this paper are also shown in section 4. Time and space complexities of the algorithms are shown in the form of tables and graphs containing the experimental data obtained through the simulations implemented in Breve in section 5. Section 6 gives the conclusions and possible future work.
2 Search Algorithms Used in Path Planning In this study we have compared the general search algorithm to the A* algorithm and a modified A* algorithm that makes use of preset heuristics.
