Author Topic: D star light  (Read 10895 times)

0 Members and 1 Guest are viewing this topic.

Offline JesseWellingTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
D star light
« on: June 16, 2007, 03:37:05 AM »
Found this. not quite sure what the 'light' is yet.

enjoy

Here is a make file btw:
Quote
CFLAGS          = -O3
LFLAGS          = -O3
CC              = gcc

OBJ             = heap.o maze.o dstarlite.o
dstarlite:      $(OBJ)
                $(CC) $(LFLAGS) -o dstarlite $(OBJ)

.cc.o:
                $(CC) $(CFLAGS) -c $<

clean:
                rm *.o
« Last Edit: June 16, 2007, 03:39:15 AM by JesseWelling »

Offline rgcustodio

  • Robot Overlord
  • ****
  • Posts: 217
  • Helpful? 0
  • Use "Search" and ye might find answers!
Re: D star light
« Reply #1 on: June 16, 2007, 08:13:30 AM »
Kewl. D* Lite is an incremental heuristic search method. Lookie here:
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf

Quite usable with maze solving robots.
« Last Edit: June 16, 2007, 08:14:02 AM by rgcustodio »
The best thing one can do when it's raining is to let it rain. - H. W. Longfellow

understanding is the path to enlightenment

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: D star light
« Reply #2 on: June 16, 2007, 05:31:50 PM »
hmmm without reading through all the code carefully . . . what sensors does it expect you to use? i dont see a way to preprogram a maze in to the solver . . .

Offline Kohanbash

  • Supreme Robot
  • *****
  • Posts: 430
  • Helpful? 1
Re: D star light
« Reply #3 on: June 16, 2007, 11:32:19 PM »
Quote
Found this. not quite sure what the 'light' is yet.
The D* light refers to being computationally light and more efficient than D*

Quote
hmmm without reading through all the code carefully . . . what sensors does it expect you to use?

It appears to be indifferent to sensors it is just looking for an obstacle map. Interesting... you can feed it "fake" obstacles and see how it reacts.



Robots for Roboticists Blog - http://robotsforroboticists.com/

Offline JesseWellingTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: D star light
« Reply #4 on: June 18, 2007, 12:53:30 AM »
The beauty is that you need *no* map to start with. Just a way to sense your coordinates (GPS or dead reckoning, or any combination of the two should work well.) and obstacles that can not be traversed.
 
In a fairly sparse environment a LOS Bug algorithm would work slightly faster but D* with localization is pretty good for teaching your robot how to go from any where in the house, to your refrigerator and back, and never have an exactly accurate map. And the D* algorithm won't have any problems with local minimums (known as wells) like a P-field might. Although it does need tweaking to make it work in an inexact environment, so I'm trying reading about a subsumption architecture that combines D* with a P-fieldesque approach for object avoidance.

slow going....ug....

Offline RoenZ

  • Jr. Member
  • **
  • Posts: 16
  • Helpful? 0
Re: D star light
« Reply #5 on: July 07, 2007, 08:12:42 AM »
Does anyone know how to implemented it in Delphi???
Thx

Offline JesseWellingTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: D star light
« Reply #6 on: July 07, 2007, 05:50:08 PM »
I just found out the algorithm I really need to use. it's called.... dun dun dun.... Field D* of all things. It works by doing an linear approximation of path between nodes to travel between them. It's very 1337. I have a good paper (1.8MB pdf) by Dave Ferguson and Anthony Stentz of CMU (Admin might know them of them) explaining it. If any one is interested just pm me with an e-mail address and I'll send it to you.

As for the Delphi question: Make the cell struct an object and go from there. I've never worked with Delphi (seems like a pretty niche language compared to C, C++ or Java) So I have no Idea but insofar as it is an object oriented language I'd start with any structs and make them objects and then make object methods and functions and then a heap container for said objects and so on.

Offline henry

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: D star light
« Reply #7 on: July 12, 2007, 05:09:36 AM »
hi...I'm college student and now I'm doing my final project in robotic...
I use D*lite in my mobile robot for path planning...
now...
I confused on the increment of open list and the sorting to find the grid which has min priority to be explored first...
I don't have any idea...where I should place the function
I'm doing my final project in delphi 7.0

can anybody help me...

Offline henry

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: D star light
« Reply #8 on: July 17, 2007, 12:12:30 AM »
any idea  ???

Offline JesseWellingTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: D star light
« Reply #9 on: July 18, 2007, 08:13:20 PM »
I'm studying the papers on it.... I'll let you know when I know.

Offline henry

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: D star light
« Reply #10 on: July 19, 2007, 05:27:35 AM »
Thanks... ;D

I have made this algorithm in delphi..but I haven't tried...

maybe I will tell you after I tried..

by the way..
where I can get the article about D*lite??
I'm search the article which explain each step so I can compare my program with the algorithm..

thanks..




Offline henry

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: D star light
« Reply #11 on: July 23, 2007, 01:17:52 AM »
hi...
I got a problem for the initial rhs and g value for each grid....
how can I get the infinite value???
I use single type variable for rhs and g value..because it can be a decimal value...
the range for single is between 1.5x10^-45 until 3.4x10^38
can I use 3.41x10^38 for the infinite value??

need advise..  :)

regrads
henry 

Offline JesseWellingTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: D star light
« Reply #12 on: July 27, 2007, 09:10:36 PM »
Just use your maximum value or create some kind of flag, Which would increase the size of your program by a lot if you are making a big maze but if you are using a PC with >256mb of ram it shouldn't matter that much.

 


Get Your Ad Here