# Real-Time Hybrid Navigation System-Based Path Planning and Obstacle Avoidance for Mobile Robots
## 4 Path Planning  
### Modified A-Heuristic Algorithm (Path Finding)  
A-star searching is the most popular grid-based path-planning algorithm because it is effective and low-cost for processing times. A-star is similar to [PERSON]'s algorithm, but it uses a heuristic approach that makes A-star searching faster than others without it. The A-heuristic algorithm searches an optimal path by giving a prior map, starting point and destination point. It adds the heuristics function to the weight of every candidate solution. By guessing the distance of every possible route to the target point, it can skip checking many undesirable solutions and make the algorithm faster. The weight of each point can be estimated by the equation below. \[f_{n}=g_{n}+h_{n} \tag{4}\]  
where \(h_{n}\) is the distance between a current checking point to the target point; \(g_{n}\) is the length of the route between the initial point and the current checking point that contains the last checking point; \(f_{n}\) is the total weight of the current checking point. This research uses the A-star algorithm for path planning of mobile robot given the prior data. The data were taken before and converted to a binary map which can be expressed as the below matrix. \[\textbf{M}_{i,j}=\left\{ \begin{array}{cl}1&(i,j)\in obsSet\\ 0&otherwise\end{array} \right. \tag{5}\]  
A-star searches for the optimal path based on a grid-based map. However, we cannot search point-by-point because the memory of the processor will be exceeded and require a long processing time for a large map. For this reason, a grid is generated based on the robot's position and size. Every spot in the grid contains many points; this is the sub-binary matrix of the entire map. Its size equal to twice the size of robot. For convenience, we consider each spot as the point of reduced-resolution map and be evaluated by the sum of all value of points in spot. The spot matrix (6) acts as the binary map with value 1 (spot contains partial obstacle) and value 0 (free collision spot). \[Spot_{x,y}= \begin{cases}1&\sum\limits_{(i,j)\in[x-s,x+s]\times[y-s,y+s]}\textbf {M}_{i,j}>0\\ 0&otherwise\end{cases}  \tag{6}\]  
If robot searches spot-by-spot on the map, the case that the next spot and the current spot lie on the diagonal line, the partial unobservable route appeared during the check (Figure 2). To overcome this problem, one square searching window is defined by four spots; the robot is in the middle of this searching window instead of the spot (Figure 3a). By searching spot-by-spot, the search window can handle the partially unobservable route in the diagonal line for robot (Figure 3b). When the searching window comes to any spot, it will evaluate whether the spot does or does not contain a obstacle. If a spot contains an obstacle, the search window does not evaluate that anymore. In this work, we also accelerate the searching speed of A-heuristic algorithm by using parallel handling. The A-star algorithm concurrently checks multiple windows (multi-agents) at the same time. These agents must meet the requirements:  
* Each agent's current checking window does not have the same location with the other in the current checking set;
* Current checking set has the lowest total f-score in open set;
* Number of current checking windows does not exceeded the processing time. Each current checking window takes into account 8 neighbor windows. The set of all neighbor windows may have redundant windows due to overlap. If any neighbor window overlaps with another in the neighbor set, the A-star will consider its g-score. The algorithm will select the neighbor window that has the lowest g-score in the overlapping window set to take account in the next step. Other steps in the multi-agent A-star algorithm are similar to the origin. However, these agents share the open and closed sets.