A* pathfinding

Typically: "How do I... ", "How can I... " questions
Post Reply
Electr0
Posts: 17
Joined: 21 Nov 2013, 16:53

A* pathfinding

Post by Electr0 » 12 Jan 2014, 19:49

Does anyone already implement this algorithm in V-REP?

how to make a grid cell for heuristic calculations? and how to make robot believe that he is in one cell of the grid?

coppelia
Site Admin
Posts: 7199
Joined: 14 Dec 2012, 00:25

Re: A* pathfinding

Post by coppelia » 13 Jan 2014, 10:52

Hello,

you can easily do this, the most important step would be to discretize the world. For that, you have several possibilities, such as:
  • by using a vision sensor watching down onto the floor. You can add filter components in order for the vision sensor to produce only black or white pixels (e.g. black=empty, white=occupied). The resolution of your vision sensor will be the size of the grid.
  • by using a proximity sensor that you sweep across your terrain in order to sample out empty grid areas.
Cheers

Eric
Posts: 186
Joined: 11 Feb 2013, 16:39

Re: A* pathfinding

Post by Eric » 13 Jan 2014, 18:46

Hi,

In order to get the grid coordinates based on the robot position (i.e. its Cartesian position), you can also do

Code: Select all

xg= math.floor(x/gridSize)
yg= math.floor(y/gridSize)
where xg and yg are the robot s coordinates in grid space, gridSize, the size in meter of each cells, x and y re the Cartesian coordinates of the robot

Cheers

PS: A sample scene that does that can be downloaded at:
https://dl.dropboxusercontent.com/u/942 ... isplay.ttt

Electr0
Posts: 17
Joined: 21 Nov 2013, 16:53

Re: A* pathfinding

Post by Electr0 » 14 Jan 2014, 01:46

thank you for your answers

but when I open the scene that Eric post, it shows a initial message that I'm not using the latest version of the v-rep and thus parts of the scene will not be displayed.

but I have the latest version, I think, what is happening?

coppelia
Site Admin
Posts: 7199
Joined: 14 Dec 2012, 00:25

Re: A* pathfinding

Post by coppelia » 14 Jan 2014, 12:06

Hello,

the reason for this is that Eric is using a beta version of next release. But that should still load fine in V-REP 3.0.5 (or even in V-REP 3.0.4, but colors might be slightly wrong in that case).

Cheers

Electr0
Posts: 17
Joined: 21 Nov 2013, 16:53

Re: A* pathfinding

Post by Electr0 » 14 Jan 2014, 14:30

so the only things that is wrong are the colors?

Eric
Posts: 186
Joined: 11 Feb 2013, 16:39

Re: A* pathfinding

Post by Eric » 14 Jan 2014, 16:36

Hi!

I saved the scene with a 3.0.5 in order to prevent the message to show up.

The scene behaves the same way. It consists of a very simple scene where you can move around the youBot robot using its control interface (that appears when you click on the youBot). When the robots moves around, a red plane is moved to the grid where the robot is located, and overlays the the robot s position in grid coordinates.

It shows how to "make robot believe that he is in one cell of the grid", or more exactly transform the robot s Cartesian coordinates into grid coordinates.

The code that does that is in the script attached to the defaultFloor. I hope it helps

Cheers

Eric

Electr0
Posts: 17
Joined: 21 Nov 2013, 16:53

Re: A* pathfinding

Post by Electr0 » 14 Jan 2014, 21:04

it helps a lot ;)


so from here i can start implement the A* algorithm?

i understand all the theory, but i'm a little bit confused with the code, the first point is to create two vectors to put the values of xg yg and the other to put the xg and yg with the lowest cost (F) right?

Jacky
Posts: 14
Joined: 29 Jan 2019, 23:14

Re: A* pathfinding

Post by Jacky » 30 May 2019, 22:54

Hi, Dear Eric:

Sorry for bothering sincerely, I have also met same issues for A star algorithm, can you please share the vrep sence if there was possible?


Yours Sincerely
Jack

Post Reply