LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

AD* on Voronoi

Solved!
Go to solution

is there anyone who knows AD* on Voronoi ? there is only AD* on Occupancy Grid. But i can't use occupancy grid in my project

 

thank you very much

0 Kudos
Message 1 of 7
(2,817 Views)

Hi zhoudeng,

 

So that I can fully understand your problem and advise you better, would you be able to tell me what your overall project is and then what you are trying to achieve using a Voronoi diagram?

Also, can you advise on what software & versions you are using please?

 

Many thanks,

Ali Bailey

National Instuments

Best regards,
Ali Bailey
National Instruments

----------------------------------

Don't forget to Kudos useful posts!
0 Kudos
Message 2 of 7
(2,790 Views)

@ali Bailey wrote:

Hi zhoudeng,

 

So that I can fully understand your problem and advise you better, would you be able to tell me what your overall project is and then what you are trying to achieve using a Voronoi diagram?

Also, can you advise on what software & versions you are using please?

 

Many thanks,

Ali Bailey

National Instuments


thank you very much.

 

i am using labview robotics 2010. basically, this version contains an example vi called 'A* on Voronoi', so that I can use this program to generate a shortest trajectory that I can use to guide my DaNI robot to navigate through A to B in the map.

 

now it seems that the environment (map) that my robot will navigate in is to some degree dynamic.. however, as we know, A* on Voronoi is a path planning algorithm based on static map.

 

so i want to use Anytime D* and I want to use Voronoi. 

 

 

thank you again.

 

Reagards,

 

DENG ZHOU

0 Kudos
Message 3 of 7
(2,781 Views)
Solution
Accepted by topic author zhoudeng

There are a few discrete algorithms at work here. The Voronoi tesselation finds a series of lines that are equidistant from a set of points. This will give you paths that are as far from obstacles as possible. It does not give you the shortest paths because it is usually possible to "hug" an obstacle or two in your path and shave off some distance.

 

The Voronoi tesselation is also reasonably expensive and it can be extremely dissimilar for incrementally different maps. This means that it usually makes little sense to run AD* on it as the extra state information stored is quickly made obsolete when the next Voronoi iteration runs.

 

In a dynamic environment, if I used Voronoi then I would try to prune as much as possible with the aim that I have a relatively simple graph and then run A* on it.

0 Kudos
Message 4 of 7
(2,772 Views)

@S_Kamath wrote:

There are a few discrete algorithms at work here. The Voronoi tesselation finds a series of lines that are equidistant from a set of points. This will give you paths that are as far from obstacles as possible. It does not give you the shortest paths because it is usually possible to "hug" an obstacle or two in your path and shave off some distance.

 

The Voronoi tesselation is also reasonably expensive and it can be extremely dissimilar for incrementally different maps. This means that it usually makes little sense to run AD* on it as the extra state information stored is quickly made obsolete when the next Voronoi iteration runs.

 

In a dynamic environment, if I used Voronoi then I would try to prune as much as possible with the aim that I have a relatively simple graph and then run A* on it.


u r saying that it's not practicle using AD* based on Voronoi Map right? I agree with that. I will be using a simple map then. or I will think about using  AD* on Occupancy Grid. 

 

the reason that i use voronoi is due to the sensors i use. i use encoders, ultrasonic sensors, RFID module, compass. as u can see, i don't have sensors like Lidar or kinect that can map the environment for me. thus i will manually map the environment, which is easy if i use voronoi method. 

 

the reason that i want to use AD* is becuase while the robot is moving in the environment, people or other robots may move around which may block the path. 

 

i suppose AD* deal with dynamic environment, in other words, the robot travels through A to B while explore the environment and find out a way simultaneously.

 

thank you for your reply.

0 Kudos
Message 5 of 7
(2,764 Views)

To elaborate further AD* is useful when there are incremental updates to a map. As you state it is well suited to cases where new obstacles are detected in a occupancy grid etc. It also works when edges are added\removed\change costs in a directed graph. But the key idea is that it is storing a lot of intermediate data in an A* like calculation and then correcting only what has changed based on the update. This is only worthwhile if the update is relatively small.

 

A voronoi graph can change pretty drastically when you add a point in the middle of a previously empty area. I am not sure how you would update the existing directed graph but even if you manage to do so the AD* algorithm will likely find it has to throw away most if not all of its stored knowledge. There is then no replanning advantage to AD* and significant initial planning and memory disadvantages.

0 Kudos
Message 6 of 7
(2,761 Views)

right. actually i have finished voronoi program and it works fine for me. but i don't want to stop there since it's not an ideal solution.

 

i am looking at AD* now. however, the problem is ultrasonic sensor doesn't provide me good resolution about the environment around it. therefore, i decide to manually map the static environment in the format of occupancy grid. and use this map as an input for the AD*. but the AD* example takes the scanned information as input, how can i use my own map instead ?  

0 Kudos
Message 7 of 7
(2,756 Views)