On Sunday, March 31, 1996 at 1:30:00 PM UTC+5:30, Avi Pilosof wrote:

I'm studying AI, and we just got our final assignment.

One of the problems within it is to navigate a robot such that it
picks up objects and arranges them in a given pattern, avoiding
obstacles in its way. The destination point is known in advance.

This problem is not a gaming problem for me, but it certainly
seems to belong in this group, since I can easily see it applying
in a game situation.

I have alot of time before this is due, and I want to get it working
using a good method.

Meanwhile, we have had two methods hinted at (to avoid obstacles):

a) Brute force: If you hit a wall, turn a little, and keep
going. This will eventually work, but is less than
inspiring.
b) Find a good path, THEN follow it.

I don't want to use (a) unless I really have to, since it's very
el-cheapo.

I would much rather find a good way to do (b), but I'm not sure how
to go about it.

I have briefly considered 2 methods:

i) Ray casting - backwards. I'm not sure exactly how I
would do this, but I was thinking to start from the
destination, and try casting towards the robot. Upon
failure, try to offset the angle of casting a little,
until you've gone full circle (increment both +ive
and -ive with each cycle). This gives me the first
ray, but I then have to cast more rays (recursively)
until the robot is hit. But once the initial ray finds
a "way out" around the obstacles, where does the next
ray begin, etc?

ii)Graph algorithms. I was thinking to define a graph
of randomly (??) distributed vertices around the
destination, and where there is no obstacle from one
vertex to another, an edge exists. This would lend
itself to a shortest-route algo. I'm VERY vague about
this method, since it doesn't seem very concrete.

Anyway, my request is for hints and pointers and algorithm
names.

I'm **NOT** asking for a solution, I would just like some direction,
and perhaps a reference. Are my ideas worthwhile? Are they junk? etc...

I would really appreciate any response (especially via e-mail).

TIA.

###################################################################

Avi Pilosof - avip@cse.unsw.edu.au
- http://www.cse.unsw.edu.au/~avip/

You cannot propel yourself forward by patting yourself on the back.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)