# A Single RF Emitter-Based Indoor Navigation Method for Autonomous Service Robots
## 6 Mapping and Path Planning
### Path Planning  
In our current system, the navigation is separated into two components representing the macro and micro level decisions: path planning and motion planning. The path planning component combines the local area information from the environment map and the target localisation information from the RSS data streams together. The path planning module uses this information to determine the path to be taken by the robot in order to reach the desired goal and avoid being trapped in dead ends. For macro-level decisions, the map of the local environment created by the SLAM module is used, with the current estimated target position placed on this map. The path planning module will then attempt to find a path from the current position to the target position. There are many different methods of path planning. The shortest path algorithms most commonly used include breadth-first search, [PERSON]'s algorithm, and A* [40]. Breadth-first search involves branching to all of the neighbouring cells until the goal is found [41]. [PERSON]'s algorithm behaves like breadth first, but also calculates the cost of traversal to each point, selecting a path that has both the shortest distance and the lowest cost [40]. This is beneficial when not all grid cells have the same cost, such as paths that need additional manoeuvring procedures or avoiding obstacles. The A* algorithm also uses the cost of traversal of each cell in the same manner as [PERSON]'s, but additionally determines which neighbouring cell to explore first depending on a heuristic. This heuristic is typically an estimate of the distance to the goal. This allows the algorithm to be directed toward the goal and is therefore more efficient. As breadth-first search does not allow cost to be based on more than just distance, this is not well suited to this application. Since A* with its heuristic is more efficient than [PERSON]'s algorithm, we selected A* for the purpose of this research to find the shortest path. For simplicity, the movement was locked to the grid cells of the SLAM occupancy grid. This means that the robot only needs to move in one of the four cardinal directions relative to the starting point, rotating in 90\({}^{\circ}\) increments and driving straight forward or back as needed. The A* pathfinding algorithm uses a best first style search, prioritising exploration of paths which give the lowest total estimated cost. When calculating the total estimated cost, the algorithm sums the current cost of a path with the estimated remaining cost. This remaining cost uses heuristics for guiding the search to reduce the time taken to find the optimal path. The heuristic uses the Manhattan distance between the current position of the path and the target position, giving the total difference in x and y positions. This provides a reasonable estimate of the remaining cost when the cost of a path is determined by the number of cells traversed and ensures the optimal known path is found. The implemented A* algorithm takes into account a number of factors in addition to the number of cells when determining the cost of a path. Each map cell has a cost of 100, 1, or 2, depending on if the cell is occupied, unoccupied, or unknown, respectively. This incentivises taking a path with known occupancy over a path with unknown cells. As each grid cell is smaller than the robot, there is a possibility that there may be a path that is considered to be viable that the robot cannot actually fit through. In order to mitigate this, the map should assign a higher cost to cells with multiple obstacles near them. This is calculated by summing the cell in question, along with its four adjacent cells. This encourages the robot to take paths that are further away from obstacles, which may lead to slightly less direct paths but decreases the likelihood of taking an invalid path and getting stuck.