Obstacle avoidance - which is best?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Obstacle avoidance - which is best?

Alex-421
Hi,

I was wondering if anyone can share a smart/efficient algorithm for
obstacle avoidance when talking about mobile robots that need to get
to a certain point in environment that has obstacles (again turtles or
other robots). I have implemented an algorithm that when a robot
detects an obstacle (or other robot) ahead it changes randomly the
direction. However, that isn't working that well since they (the
robots) also try to get to a certain coordinate.

My code:

to avoid-obstacles
  ask robots
  [
    ifelse detect-obstacle?
    [
      set heading random 360
    ]
      move-towards-goal
    ]        
  ]
end

to-report detect-obstacle?
  ifelse any? other robots in-cone 4 45 or any? other obstacles
in-cone 4 45 or [pcolor] of patch-ahead 1 = gray
    [report true]
    [report false]
end

to set-direction
  ask patches [set goal distancexy-nowrap -99 0]
end

to move-towards-goal
  fd 1
  face-downhill
  move-randomly
end

to face-downhill
  face min-one-of neighbors [goal]
end

I have only one type of obstacles and the walls of the tunnel (the
robots are moving in a tunnel) but I could have clustered obstacles
that look like wall. The robots eventually get around such, but do it
quite slowly and stupidly by always changing to a random direction
instead of going around.

Please, if anyone can share a better obstacle avoidance algorithm,
don't be shy, do so :) Thanks!

Reply | Threaded
Open this post in threaded view
|

Re: Obstacle avoidance - which is best?

Kristy Martin
You might find the Games section in the Models Library useful.

On Wed, May 14, 2008 at 10:22 AM, Alex <[hidden email]> wrote:

>   Hi,
>
> I was wondering if anyone can share a smart/efficient algorithm for
> obstacle avoidance when talking about mobile robots that need to get
> to a certain point in environment that has obstacles (again turtles or
> other robots). I have implemented an algorithm that when a robot
> detects an obstacle (or other robot) ahead it changes randomly the
> direction. However, that isn't working that well since they (the
> robots) also try to get to a certain coordinate.
>
> My code:
>
> to avoid-obstacles
> ask robots
> [
> ifelse detect-obstacle?
> [
> set heading random 360
> ]
> move-towards-goal
> ]
> ]
> end
>
> to-report detect-obstacle?
> ifelse any? other robots in-cone 4 45 or any? other obstacles
> in-cone 4 45 or [pcolor] of patch-ahead 1 = gray
> [report true]
> [report false]
> end
>
> to set-direction
> ask patches [set goal distancexy-nowrap -99 0]
> end
>
> to move-towards-goal
> fd 1
> face-downhill
> move-randomly
> end
>
> to face-downhill
> face min-one-of neighbors [goal]
> end
>
> I have only one type of obstacles and the walls of the tunnel (the
> robots are moving in a tunnel) but I could have clustered obstacles
> that look like wall. The robots eventually get around such, but do it
> quite slowly and stupidly by always changing to a random direction
> instead of going around.
>
> Please, if anyone can share a better obstacle avoidance algorithm,
> don't be shy, do so :) Thanks!
>
>  
>
Reply | Threaded
Open this post in threaded view
|

Re: Obstacle avoidance - which is best?

Alex-421
unfortunately, in the game's library there is no model with obstacle
avoidance, unless i'm horribly mistaken

Reply | Threaded
Open this post in threaded view
|

Re: Re: Obstacle avoidance - which is best?

James Steiner-2
Obstacle avoidance, in the case of your model, is more like
path-finding, in that you don't know in advance the size or shape of
the obstacles, and your agents need to plan a route to pass by or
around or (perhaps?) to back up and try again.

So, you may actually need the complexity (in terms of code length and
extra turtles or whatever) of something like an a* path finder.

But, here is a link to a model on turtlezero.com that has particles
flowing around each other. They are given limited options about how to
move then they are blocked, and keep trying until they get where they
need to go. However, they do often spend a lot of time waiting for
other things to get out of the way.

http://www.turtlezero.com/models/models.php?model=homing-particles-obstacles&mode=framed

click Setup. Click GO. Once the particles settle a bit, click "lottery"

~~James


On Wed, May 14, 2008 at 7:51 PM, Alex <[hidden email]> wrote:
> unfortunately, in the game's library there is no model with obstacle
> avoidance, unless i'm horribly mistaken
Reply | Threaded
Open this post in threaded view
|

Re: Obstacle avoidance - which is best?

Hengeveld, Geerten
In reply to this post by Alex-421
Hi Alex,

first, if you have a patch as the goal. And put it in a turtle-owned
variable, you do not need to calculate the distance to the goal for each
patch. (that would save time in initialisation if your number of
timesteps x number of robots < number of patches. and it makes the
algorithm flexible to be used for robots with different goals.)

second. If you do work with the goal as patch-owned. make all walls set
their goal to goal + 1000; that way you will never face a wall.

third. I sort-of read in your current syntax that your robots are
bounded to the grid (the move towards patch centres). Why not just make
a lt or rt 90 if there is an obstacle ahead and check again? that way
they will not face backward unless they are actually surrounded. if you
want them to move to more floating point locations, you could
offcourselet them
ifelse (random 1) [rt 90 - random-float 45][rt - 90 + random-float 45]
(avoiding the centre of your cone where the obstacle is. keeping a
margin) (use 45 degrees if you want them to be more goal oriented!)

Hope this sort of messed up e-mail helps you any further

Geerten

PS for the goal finding, check the a* algorithm, James must have a dozen
or so examples of that one on his website