AI Navigation

Path Planning and Global Coverage

I focused on developing a path planning system using the Weighted A* algorithm. The algorithm efficiently searches for the shortest path by evaluating surrounding nodes in eight directions and employing Manhattan distance as the heuristic function. Despite some trade-offs in optimality for faster search speeds, our results demonstrated the effectiveness of the method across various scenarios.

I also implemented the DARP algorithm for global coverage, designed for multi-robot systems. DARP divides the map into equal areas, ensuring complete coverage with minimal overlap.

Path Planning

A* Algorithm

Starting the Search

The search begins by initializing an OpenList and a CloseList. The OpenList starts with just one node, the starting point (A). As the algorithm progresses, more nodes are added to the OpenList, representing possible paths. The algorithm examines the nodes adjacent to the starting point A, ignoring any obstacles, and adds reachable nodes to the OpenList, setting A as their parent node. The starting point is then removed from the OpenList and added to the CloseList, which contains nodes that are no longer needed.

Path Sorting

The algorithm proceeds by finding the optimal path using the formula F = G + H. Here, G represents the cost of moving from the start point to a given node, and H is the estimated cost from that node to the goal. The algorithm continuously searches the OpenList, selects the node with the smallest F value, moves it to the CloseList, and checks its neighboring nodes. If a better path is found (i.e., one with a smaller G value), the parent node is updated, and the F and G values are recalculated. The process repeats until the optimal path is found.

Results

Small_easy:
560 steps, 1.118 seconds

Medium_easy:

986 steps, 95.76 seconds

Big_easy:

1868 steps, 15792 seconds

Small_medium:

654 steps, 1.319 seconds

Medium_medium:

1686 steps, 3300 seconds

Big_medium:

1806 steps, 20579 seconds

Small_hard:

624 steps, 159.095 seconds

Medium_hard:

1162 steps, 2171 seconds

Big_hard:

1976 steps, 5961 seconds

Global Coverage

DRAP Algorithm

The DARP algorithm primarily uses a cyclic coordinate descent optimization method to update each robot's path iteratively. The goal is to achieve optimal multi-robot Coverage Path Planning (mCPP). In implementation, the starting and ending positions are used as the initial positions for the two robots (agents) or only one robot.

Results

Singal Robot