Giter VIP home page Giter VIP logo

habrador / self-driving-vehicle Goto Github PK

View Code? Open in Web Editor NEW
323.0 14.0 94.0 13.28 MB

Simulation of path planning for self-driving vehicles in Unity. This is also an implementation of the Hybrid A* pathfinding algorithm which is useful if you are interested in pathfinding for vehicles.

Home Page: https://www.habrador.com/

License: MIT License

ShaderLab 0.76% C# 99.24%
unity unit3d selfdriving self-driving-car pathfinding autonomous-vehicles autonomous-car autonomous-navigation astar open-source

self-driving-vehicle's Introduction

Self Driving Vehicle

Let's say you are standing somewhere in a room and would like to find the shortest path to a goal. You can see a few obstacles, such as a table, that you would like to avoid. The easiest way to solve the problem (if you are a computer) is to divide the room into many small squares (cells) and then use the common A* (A Star) search algorithm to find the shortest path.

But what if you are a car and can't turn around 360 degrees like a human can, then you have a problem! Well, at least until you learn the Hybrid A Star search algorithm. With that algorithm you will be able to find a fully drivable path to the goal!

Click for YouTube video of the algorithm in action:

Link to youtube video

If you just want to play around with it you can download a build of the project here for Windows: https://habrador.itch.io/hybrid-a-star

Tell me how the algorithm works

You can read more about it here: https://blog.habrador.com/2015/11/explaining-hybrid-star-pathfinding.html

Is this something actually being used by car companies?

Yes! Tesla mentioned the algorithm in a Tesla AI Day presentation (roughly at 1 hour 20 minutes). So if you ever wondered how the Tesla "Smart Summon" feature works then now you know! Tesla has included a short description of the Smart Summon feature (which is part of the Full Self-Driving Capability (FSD) version of Tesla Autopilot) in the Model Y Manual. We can assume it's the same implementation for other Tesla models, such as Model S.

  • "Smart Summon works with the Tesla mobile app when your phone is located within approximately 6 meters of Model Y." My implementation works over distances of greater than 6 meters.

  • "Smart Summon may not stop for all objects (especially very low objects such as some curbs, or very high objects such as a shelf) and may not react to all traffic. Smart Summon does not recognize the direction of traffic, does not navigate around empty parking spaces, and may not anticipate crossing traffic." My implementation has fixed obstacles only, and they all have the same height. I actually planned to add moving objects and traffic lanes with direction, but will not do so because Tesla's implementation can't handle them.

  • "Touch the crosshair icon then drag the map to position the pin on a chosen destination. Press and hold the GO TO TARGET button. Model Y moves to the destination." My implementation is not just moving to a destination, but also with a specific target direction, such as the left door ends up infront of you.

FAQ

  • What software do I need? To make this project work you need Unity. I've used Unity 2017-2021 but other versions should work as well.

  • Is it working on a navmesh? No, it's not! The algorithm needs a grid with cells to be able to remove unnecessary nodes, or you will end up with an infinite amount of nodes.

TODO

  • The car can follow the generated paths with great accuracy, but the truck with trailer is not that good at following the path. That has to be fixed!

self-driving-vehicle's People

Contributors

habrador avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

self-driving-vehicle's Issues

Exact Reeds-Shepp waypoints instead of approximation

Hi, I found that waypoints calculation at long distances are way too inaccurate and also costly.

There is exact calculation of waypoints without "accuracy" tuning. Too busy to create a proper pull request, so here is the code:

private static List<ReedSheppPathfindingCar> AddWaypoints(
	PathWords word,
	PathSegmentLengths pathSegmentLengths,
	ReedSheppPathfindingCar carStart,
	ReedSheppPathfindingCar carEnd,
	float wpDistance,
	float turningRadius,
	bool generateOneWp)
{
	// Find the car settings we need to drive through the path
	List<SegmentSettings> pathSettings = PathSettings.GetSettings(word, pathSegmentLengths);

	// Each segment starts from the second subsegment to prevent waypoints duplication. So, we need to add first waypoint manually
	List<ReedSheppPathfindingCar> waypoints = new List<ReedSheppPathfindingCar>();
	waypoints.Add(new ReedSheppPathfindingCar(carStart.Position, carStart.HeadingInRad, pathSettings[0].Gear, pathSettings[0].Steering));

	// Track last waypoint
	ReedSheppPathfindingCar lastWaypoint = waypoints[^1];

	// Loop through all 3-5 path segments
	foreach (SegmentSettings segmentSettings in pathSettings)
	{
		int subSegments = (int)Math.Ceiling(segmentSettings.Length * turningRadius / wpDistance);
		float interpolationPerSubsegment = wpDistance / (segmentSettings.Length * turningRadius);

		Vector3 segmentStartPosition = lastWaypoint.Position;
		float segmentStartHeading = lastWaypoint.HeadingInRad;

		if (segmentSettings.Steering == ReedSheppPathfindingCar.Steering.Straight)
		{
			float direction = segmentSettings.Gear == ReedSheppPathfindingCar.Gear.Back ? -1f : 1f;
			Vector3 delta = direction * segmentSettings.Length * turningRadius
				* new Vector3(Mathf.Sin(segmentStartHeading), 0f, Mathf.Cos(segmentStartHeading));
			Vector3 segmentEndPosition = segmentStartPosition + delta;

			for (int i = 1; i <= subSegments; i++)
			{
				float interpolation = Mathf.Clamp01(i * interpolationPerSubsegment);
				Vector3 position = Vector3.Lerp(segmentStartPosition, segmentEndPosition, interpolation);
				waypoints.Add(new ReedSheppPathfindingCar(position, segmentStartHeading, segmentSettings.Gear, segmentSettings.Steering));

				if (generateOneWp)
				{
					return waypoints;
				}
			}
		}
		else
		{
			float reverseIfLeft = segmentSettings.Steering == ReedSheppPathfindingCar.Steering.Left ? -1f : 1f;
			float reverseIfBack = segmentSettings.Gear == ReedSheppPathfindingCar.Gear.Back ? -1f : 1f;

			float steeringClockwise = reverseIfLeft * reverseIfBack;
			float steeringAngle = segmentSettings.Length * steeringClockwise;

			float displacementAngle = segmentStartHeading + Mathf.PI / 2f * reverseIfLeft;
			Vector3 displacement = new Vector3(Mathf.Sin(displacementAngle), 0f, Mathf.Cos(displacementAngle));

			for (int i = 1; i <= subSegments; i++)
			{
				float interpolation = Mathf.Clamp01(i * interpolationPerSubsegment);
				float currentSteering = steeringAngle * interpolation;

				float circleAngle = segmentStartHeading - Mathf.PI / 2f * reverseIfLeft + currentSteering;
				Vector3 circle = new Vector3(Mathf.Sin(circleAngle), 0f, Mathf.Cos(circleAngle));
				Vector3 delta = (circle + displacement) * turningRadius;

				Vector3 position = segmentStartPosition + delta;
				float heading = segmentStartHeading + currentSteering;
				waypoints.Add(new ReedSheppPathfindingCar(position, heading, segmentSettings.Gear, segmentSettings.Steering));

				if (generateOneWp)
				{
					return waypoints;
				}
			}
		}
		lastWaypoint = waypoints[^1];
	}

	// The accuracy of the last waypoint is about 1.E-5 for the position and 1.E-7 for the angle.
	// So, there no need for a correction, but better be safe then sorry.
	waypoints[^1] = new ReedSheppPathfindingCar(carEnd.Position, carEnd.HeadingInRad, lastWaypoint.CurrentGear, lastWaypoint.CurrentSteering);
	return waypoints;
}

Solve pathfinding problem for truck and trailer positions

The video shows that the position of the truck's trailer is not achieved perfectly.

Even more general: How to expand an agent's state?

  • I think Astar can search not only possible kinematic states[position, velocity, rotation angle, angular velocity]

Perhaps before we ask this question, we can think about how to reduce the number of calculations.
Maybe cut some logical branches in early stage or combine those branches that can be treated as one.

Something wrong with FlowField neighbors to the corner obstacles check

Assets/Scripts/Pathfinding/Utility/Flow field/FlowField.cs FindNeighboringNodes

IntVector2 cellPos_n1 = new IntVector2(node.cellPos.x + n1.x, node.cellPos.z + n1.z);
IntVector2 cellPos_n2 = new IntVector2(node.cellPos.x + n2.x, node.cellPos.z + n2.z);

cellPos_n1 and cellPos_n2 are still the corners, but not corner's neighbors, replace to:?

IntVector2 cellPos_n1 = new IntVector2(cellPos.x + n1.x, cellPos.z + n1.z);
IntVector2 cellPos_n2 = new IntVector2(cellPos.x + n2.x, cellPos.z + n2.z);

// IntVector2 cellPos_n1 = new IntVector2(node.cellPos.x + n1.x, node.cellPos.z + n1.z);
// IntVector2 cellPos_n2 = new IntVector2(node.cellPos.x + n2.x, node.cellPos.z + 

if (IsCellPosWithinGrid(cellPos_n1, mapWidth) && IsCellPosWithinGrid(cellPos_n2, mapWidth) && (!nodeArray[cellPos_n1.x, cellPos_n1.z].isWalkable || !nodeArray[cellPos_n2.x, cellPos_n2.z].isWalkable))
{
    //This is not a valid neighbor so remove it from neighbors
    neighborCells.Remove(cellPos);
}

@Habrador

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.