Method and Apparatus for Path Planning Based on Obstacle Density

Method and Apparatus for Path Planning Based on Obstacle Density

This technology is an autonomous driving path planning method that divides image space into cells to calculate the density of static and dynamic obstacles. It then performs hierarchical/non-hierarchical clustering and applies a genetic algorithm (GA) to generate obstacle-avoidance paths.

Existing genetic algorithm-based path planning focuses solely on finding the shortest path, leading to increased computational load as workspace size grows. Furthermore, it fails to adequately account for dynamic obstacle information, resulting in persistent collision risks during movement.

This technology converts images into grayscale occupancy (static) and brightness information (dynamic) to calculate density. It then reduces data complexity through k-means clustering and derives an optimal path by applying a genetic algorithm that integrates obstacle density, path distance, and penalties for infeasible paths into the fitness function. This improves routing performance by accounting for workspace size and dynamic obstacle information, making it suitable for applications in rehabilitation training, gait assistance, and medical/welfare services.

‍

‍

Key Features:

• Obstacle density calculator that divides images into cells and calculates the obstacle density for each cell
• Clustering unit that groups each cell into one or more clusters
• Path planning output unit that executes a genetic algorithm using obstacle density and cluster information to generate a path plan
• Configuration that calculates density using grayscale occupancy for static obstacles and empty spaces, and pixel brightness for dynamic obstacles