# A* search results in path too close to obstacles

I have a configuration space as below with several obstacles. Green circles are all the points I need to go to. Blue line is the path returned from A* search.

However, I am looking for path that's smoother and away from obstacles. what can I do?

• Welcome to Robotics:SE. What other options have you looked at so far? You might find it helpful to review the site tour and Help Centre and, in particular, How to Ask. Dec 3 '18 at 22:36
• I have looked at several options but not sure exactly what I need. trapezoidal decomposition, visibility graph, navmesh, Marching Squares , Delaunay triangulation. Is there a book i can buy? Dec 3 '18 at 22:53
• Smoothing the trajectory and get a distance to the obstacles are both knowledge based requirements. They have to be realized in the existing sourcecode. Which kind of software is used for the A* planner? Is already a Domain specific language in use? Or it is a vanilla algorithm coded in matlab? Dec 5 '18 at 12:27
• I am using github.com/qiao/PathFinding.js Dec 6 '18 at 23:33
• @socialMatrix According to the sourcecode, it's a pathplanning library written in Javascript which provides algorithm for A*, Breadth-first-search and others. To make the path smoother and stay away from the obstacles a new widget in the GUI is needed which has to be parsed by the selected algorithm. The provided algorithm have each 150-200 lines of code in Javascript, so it will be a nice programming task to add an additional parameter. For prototyping purposes, Javascript is great, so it make sense to stay within the same language. Dec 7 '18 at 20:44

Suppose you are working in a 2D environment and that you have an obstacle of the size 2x2. When doing planning (graph search, etc.), you increase the size of the obstacle to, for example, 3x3. Then when you find a path, the path is guaranteed to be at least of the distance 1 away from the actual obstacle.

As for a smoother path, you may apply some shortcutting procedure on the path found by your path planner. Searching for shortcutting or trajectory shortcutting should give you a number of results.

• I was thinking to use delaunay triangulation to generate navmesh -> A* on navmesh -> simple funnel for smoothing. I tried padding but in some instances it resulted in blockage (since obstacles were too close) Dec 6 '18 at 23:40
• Do I need to do this? Dec 10 '18 at 20:56
• @socialMatrix if your planning problem is not too high-dimensional, you can do that. It wouldn’t guarantee any clearance, though. Regarding padding, unless you have some points that you need to go that are actually touching the obstacles, you can always reduce the padding size to avoid blocking. Dec 12 '18 at 2:15

Most planning algorithms reduce your robot to a point and plan a path for that point. The arising problem is exaclty what you are facing. As suggested before, obstacle padding is one of the methods, but generally, the configuration space has been proposed to solve this problem.

Configuration space is a more advanced and more general way of padding obstacles. The obstacles are enlarged by the dimentions of the robot, considering also the robot's orientation. A more detailed description can be found here.

In order to smooth your paths:

• you can introduce penalties in A* for non-smooth portions of the path. However, since A* can only plan in discreet envionments, some degree of discontinuity will alwazs be present
• you can use methods which take into account the dynamic limits of your system (dynamic window)
• make A* plan an even more coarse path and fit splines on those waypoints to make sure that the obtained path is smooth
• you can post-process the paths to smooth them out with a filter

Smoothing will introduce slight deviations in the path, so make sure to consider possible collisions after smoothing also.

• To my understanding, configuration space approach is not a generalization of obstacle padding. It is a different space where the planning problem takes place. For example, when planning motions for a 6-DOF robot, the configuration space is then $\mathbf{R}^6$. In that space, the robot is represented by a point. Planning motion in configuration space does not help guarantee any clearance between the robot and obstacles. Dec 5 '18 at 14:54
• I was thinking to use delaunay triangulation to generate navmesh -> A* on navmesh -> simple funnel for smoothing. I tried padding but in some instances it resulted in blockage (since obstacles were too close) Dec 6 '18 at 23:41
• Do I need to do this? Dec 10 '18 at 20:56