A* Path finding for an object

[Theodoro_Cardoso]

Hi,

I’m trying to use the A* path finding algorithm to make a robot navigate between two known locations in a 2D environment…

It was easy to make the example work and it is a very useful tool, the challenge now is to modify the vi to describe the robot as an object, and calculate the best path for it.

The example give us the path for a single “square”. Is there any way to change this to a more “complex” shape?

                      

This is the example working.

The second pic is the real model, made on ms paint. Where the blue point represents the robot center and the green parts are the robot wheels, that are the only things that can’t crash the obstacles.

ps: increasing the obstacles size wouldn't solve it due to the possibility of avoiding small obstacles (like holes on the ground) with the robot center (making it go between the wheels).

Hope we can find a way to modify the algorithm on LabVIEW, thank you for helping.

Best Regards.

Theo

[JamesSouv]

Hello,

If I understand you correctly, you want the robot to navigate between two known locations in a very complex path and finding the best path?

Can I ask you some questions?

- What do you mean by: complex path?

- Could you also replace those 5 squares? I mean, wouldn’t be more appropriate to represent them with one single square covering the whole surface, since you want to describe the robot as an Object?

- Finally, since you wish to modify the algorithm could you please attach your VI?

[Theodoro_Cardoso]

---

JamesSouv escreveu:

Hello,

If I understand you correctly, you want the robot to navigate between two known locations in a very complex path and finding the best path?

Can I ask you some questions?

- What do you mean by: complex path?

- Could you also replace those 5 squares? I mean, wouldn’t be more appropriate to represent them with one single square covering the whole surface, since you want to describe the robot as an Object?

- Finally, since you wish to modify the algorithm could you please attach your VI?

---

Hey James, thank you for helping.

- An example of path can be seen on the image below.

I've made it on ms paint and hope that it is understandable. Notice that the robot wheels can move in any direction (mecanum wheels)

- Replacing the squares, that are actually 4 (the blue one is just the center of the robot and it doesn't have to avoid the obstacles), would make it harder or even impossible to go along the path. If you look carefully to the image above, you'll see that in some cases the only option we have is to go through the obstacle by placing it under the robot center (between the wheels).

- The VI is attached to the post.

I'm grateful for your help and sorry about the lack of information.

[Theodoro_Cardoso]

It's all about this code, the vi is called A Star Plan.vi and it is attached to this previous post too. 

I'm trying to study the block diagram but I'm struggling to understand it.

Basically what we got to do is to change the map on every single step, modifying the walkable/unwalkable state of the tiles every time depending on where the robot is.

If someone could help me to do it or at least undestand what's going on that code, I would be very grateful.

Thank you. 

[JamesSouv]

Hello Theodoro,

Thanks for posting your VI,

One can see that you took your time to explain what you plan to do.

Unfortunately, none of your subVIs were attached to the A Star Complex Object.vi

(this would make it easier for other users to have a look inside)

Well, my suggestion in this case would be to use the A* path finding VI as it is, combined with an intelligent AvoidObstacle.vi (for example, that you would program on your own) which will only be in used, in case an obstacle is on the way. There you would calculate: if you have to go around the obstacle or if you can roll over it.

After Obstacle is avoided, you could reinitialize the position and call the A* path finding.vi again. This logic would go repeatedly, till you got to your destination.