International Journal of Innovative Research in Science, Engineering and Technology
MenuISSN ONLINE(2319-8753)PRINT(2347-6710)
ISSN ONLINE(2319-8753)PRINT(2347-6710)
M.Bala Subramanian1, Dr.K.Sudhagar2 and G.RajaRajeswari3
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology
Identifying an optimal path for a mobile robot agent is considered to be one of the key challenges for researchers in the field of robotics. A mobile robot agent participating for mission critical application will explore into an unknown environment will be challenging criteria, considering its contraints such as time, cost, energy, exploration distance etc.. When the mobile robots agent decides its action, it is necessary to plan its movement more precisely and optimally. This paper presents the use of search algorithm in identifying the optimal path along with its navigation controlling mechanism of a mobile robot agent navigational systems. The mobile robot agents are modelled to work independently through its intelligence without any human intervention. This paper aims on studying the movement details of an robot agent participating in dynamically changing environment using Breadth First Search (BFS) algorithm. The systemevaluation is validated using Graphical User Interfcae (GUI) based test bed for robots called Robosim and the efficiceny of the system is measured via simulation resutls through a defined complex arena. Simulation results proven that the applyuing the BFS algorithm in a unknown envirnoment explores much faster then heuristic based other path palnning algorithms
Keywords |
| Mobile Robot Agent, Path Planning, BFS algorithm, A* algorithm, RoboSim |
INTRODUCTION |
| Autonomous Mobile robots (AMR) are physical agent that move and interact continuously while participating in a static navigation system, does not know the path that RA to be follow. In order to achieve and obtain the target position, the RA should update its current location details along with the environmental information that it gains while in exploration process. So, that the navigation control system will perform an optimal path input feeding mechanism. There are several algorithms used to obtain a path in such environments. Over last few decades, there were several number of algorithms were proposed by many researchers for path planning in static and dynamics environment. The characterization of algorithms is made with respect to the length of generated path and with respect to the time spent to obtain it. These two criteria are independent of each other. The shortest path does not necessarily imply the minimum time, or vice versa. The graph search algorithm, are the most known solutions for this problem. These algorithm uses directed or undirected graph trees. In addition these algorithms were used in most of the computer based simulated or online games and in GPS systems for to identifying shortest and lower cost path [1][4]. |
LITERATURE REVIEW |
| With the latest advancement on Artificial Intellignce (AI), RA is deployed in the task of searching and rescuing operation in an uncertain or dynamic environment. The searching effficiency is considered to be high priority task in this mission critical application. A typical RA navigation system includes a high intelligence path planning module which determine appropirate path for a RA based on the current map and the corresponding obstacle avoidance algorithm which will determines a suitable direction of motion exploration based on the obtained data. Path planning consideres a model or map of the environment to detrermine the geometric path point for the RA to track from its initial starting postion to the target or goal position. |
| San et-al proposed a sensor based path planner methodology to handle both local and global path planning [3]. Qualid et-al proposed a methoid using DVFF approach bsedon D* algorithm, [4 ,5, 6, 7]. The common path planning method such as genetic algorithm [7], A* algorithm [8], particle swarm optimazation [9], D * search algorithm, Moore algorithm were discussed. shi-gang, HUi, Wang, Li yang made a simulation study on application of both the D* and A* algorithm in intelligent trasnfer system as well as robotic path planning [8]. Tolga,Sezgin made an experinmental study by implementing various algorithm, in identifying the optimal path for a mobile robots on a grid based map [11]. The RA are initially positioned at the center of the objective environment and control agents start to work without having any preliminary information about the environment. It will depend on the composing process. According to its current position and following the defined exploration algorithm the RA starts its exploration process In parallel and independently of what this agent is doing, the agent that avoids obstacles calculates other velocity values according to infrared sensor values that are included in the navigation control architecture[2]. This paper aimed at RA in uncertain environment using the BFS algorithm can realize RA to precisely turn away from dynamic obstacles, and if discovering new obstacle in the original path then the RA redesign path, until it achieve its target. |
PROBLEM DEFINITION |
| The multi-robot path planning problem is defined as follows: given a set of n RA in k-dimensional work space, each with an initial starting configuration and a desired target configuration, determine the path each RA should take to reach its goal, while avoiding collisions with obstacles and other RA in the workspace [12]. The collision free path planning for a MRA among static obstacles are formally considered as: Let ‘m’ be a rigid RA in a static workspace Ws = Rk, where k=2 or k=3. The workspace is populated with obstacles. A configuration q is a complete specification of the location of every point on the RA geometry. The configuration space C represents the set of all the possible configurations of M with respect to Ws. Let O ⊂ WS represent the region within the workspace populated by obstacles. Let the closed set M(q) ⊂ WS denote the set of points occupied by the RA when it is in the configuration q ∈ C. Then, the C-space obstacle region, Cobs is defined as: |
 |
BREADTH FIRST SEARCH (BFS) ALGORITHM |
| BFS algorithm works with the method branching from the starting cell to the neighbour cells (just traversable cells), (untraversable cells and cells out of boundaries are discarded) until the goal cell is found [13]. It is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbour the currently visited node. The BFS algorithm begins at a root node and inspects all the neighbouring nodes. Then for each of those neighbour nodes in turn, it inspects their neighbour nodes which were unvisited, and so on. In this traversal process, every node in the graph, we assign the direction to each edge from discoverer S to discovered D. The discoverer source point ‘S’ is considered as a ‘master/parent’ of ‘subordinate/child’ D, since each node has exactly one master/parent node, except root node. |
 |
SIMULATION RESULTS |
| A large amount of simulation software is available for RA systems, and it is already being used extensively. The majority of the RA simulation tools focus on the motion of the robotic manipulator in different environments. As the motion simulation has a central role in all simulation systems they all include the kinematics or dynamic models of robot manipulators [10]. Which type of models will be used depends on the objective of the simulation system. All these simulators are with the goal of creating an artificial robot environment, as real as possible, considered to be the test bed for the implementing the mobile robotic algorithms. The effectiveness of the above defined approach is tested and evaluated in RoboSim simulation environment, which shows potential results in the reality and nonexistence of anonymous obstacles. |
| This paper presents a algorithm based on cell branching method, called Breadth First Search (BFS) algorithm for a MRA on grid map based dynamic environment using RoboSim Simulator tool. RoboSim is a Java based robotics simulation utility that is easy to understand some basic concepts of movement and path planning algorithms. RoboSim comes with various modules, which enables the researchers by learning about the path planning and smoothing concepts. |
| The working environment is defined based on the input grid size. Using this pre-defined GRID world, the BFS algorithm constructs a path between the starting point and the goal point. It is shown that, when a MRA start executing its current navigational plan and it continuously sense the obstacles for next movement. Once the obstacles are sensed the RA sends the signal to its associated master agents and the newly constructed path is passed through communication channel to the RA. The input for this simulation is defined as grid coordinates. Fig. 1 defines a grid map of 7 X 7 cells, using World Builder of RoboSim and the starting node of the MRA is spotted with red color and the black node represent obstacles and node with green spot shows as target point. The MRA motion analysis or path trace details are shown in Fig. 2, 3, 4. |
 |
| MRA, defined with its initial position and the movement from initial to target positions are captured along with the path trace details for different scenarios, under different parametric function. Fig. 2 shows the exploration of MRA applied with BFS algorithm, and without allowing any diagonal motion. Fig. 3 uses exploration of MRA applied with BFS algorithm, allowed with diagonal motion and Fig 4 shows exploration of A* algorithm for comparative purpose. |
 |
 |
| It has been observed that, When A* algorithm computes f(n), the square of distance will be much higher than the cost g(n) and it will end up with an overestimating heuristic. Also after applying different heuristic value for path calculation it has been observed that the MRA explores as optimal as possible, using BFS algorithm depends on heuristic selection. |
CONCLUSION |
| This paper exhibits a comprehensive study on BFS algorithm, by performing various simulation experiments. To realize the efficiency of the BFS algorithm, it is simulated via Java based simulation tool called RoboSim. The experimental results shows that BFS algorithm can realize the path planning under the dynamic environment very optimal and successfully avoid the obstacles, and reach to its target point. However, when applying different heuristic function, it has been observed that the results are getting differed. This algorithm will be further investigated and will be deployed in real time RA, participating in mission critical application. |
References |
|