So I've made a self-driving car in Unity. The car is using the Hybrid A* pathfinding algorithm along with other algorithms to find its way around a confined area, such as a parking lot. You can test it here or here. The old version was working fine, but one can always improve. The updates in this version are:
- Added lines showing the waypoints
- Fixed a bug where the wrong value was added to the sum or errors in the PID controller, so the car is now following the path much better
- Added a cost for switching driving direction, like forward -> reverse, because it would be annoying to sit in a car that constantly is switching driving directions
- Fixed a bug where the smooth path algorithm optimized the distance to obstacle in 3d space and not 2d space
- Added an improved obstacle-intersection algorithm which is faster and more accurate. It's now using rectangle-rectangle intersection instead of circle-circle intersection
- Added UI where you can display the grid and the flow field
- When optimizing the final path, it's now optimizing the distance to the average of the surrounding obstacles and not just the closest obstacle
- Cleaned up the code
- Added flow fields as heuristic and for obstacle detection, which makes the pathfinding much faster
- Made so that the Hybrid A star can expand to a cell if this expansion has a lower cost than previously
- Improved path following so the car is slowing down gradually before it reaches the end or a turning point such as "reverse -> forward". Previously you could often see how the car crashed into walls because it was driving too fast
This is the flow field the car is using to faster detect if it's colliding with an obstacle:
The area is divided into cells, and the darker the cell is, the further away it is from an obstacle. So if you want to check if a car is colliding with an obstacle while generating the path, you can see in which cell it is and see how far away from an obstacle it is. If it can't possible be colliding with an obstacle, then it's not colliding with an obstacle and you don't need to use a slow rectangle-rectangle intersection algorithm to check if it's colliding with an obstacle.
Update 2017-07-26
I realized that a good idea might be to close cells depending on the heading the car had when entering the cell. So the car can drive to the same cell even if it is closed if it hasn't arrived to that cell before with the same heading. The result looks like some abstract art:
...but the algorithm is now finding more solutions and the car can even turn around on its spot. The problem is that sometimes this solution is much slower, so maybe a combination between the slow and the faster algorithm can be used?
Update 2017-07-26
I realized that a good idea might be to close cells depending on the heading the car had when entering the cell. So the car can drive to the same cell even if it is closed if it hasn't arrived to that cell before with the same heading. The result looks like some abstract art:
...but the algorithm is now finding more solutions and the car can even turn around on its spot. The problem is that sometimes this solution is much slower, so maybe a combination between the slow and the faster algorithm can be used?
Comments
Post a Comment