Hello I''m in a robot soccer class this semester for my senior project. Its a one on one tournament in which you build tiny robots that push a golf ball into a net on the other side. So i''ve decided to come here and ask a couple questions on what you guys think would be the best way to do path finding and scoring. Remembering that this needs to be fast as well as effective. Currently we are running at 30 frames a second.(ntsc standard) and we really don''t want to slow our frame rate down to do mathmatically intensive processing. I''ve been searching this forum and reading about the A* algorithm. I''m still not that sure how it works but i''m working on it. Does anybody have suggestions on which algorithms to use or what they think will be best? Any advice is appreciated.

Is that like, real robot soccer (i.e. you build it), or simulated robot soccer?

Oh yeah, and as I recall, the A* algorithm is meant for node-based navigation, so it will only do you good if you're in a predefined maze or similar.

Edited by - feagle814 on February 10, 2002 4:36:34 PM

Are we talking about REAL robots? If so, then A* will be the least of your worries (probably even irrelevant)... Your problem will be to make sense of the poor sensorial information available, trying to figure out exactly where the robot is are and where it''s facing.

Then, you can use simple reactive rules to guide the robot. Take a look at flocking algorithms and Craig Reynolds work.

Alex

---

Artificial Intelligence Depot - Maybe it''s not all about graphics...

Regardless of whether you are simulating robo-soccer or building actual robots, your planning/control system will need to have at least two distinct levels: high level planning and low level, reactive planning.

At the high level, your agent will need to formulate plans like: move from current location to ball, push ball AND move to net, push ball into net; or perhaps move to ball, hit ball to player X. At the low level your agent will need to deal with unexpected obstacles (other players, walls, the ball, etc) that block its path. This can be handled in a reactive manner.

For the moment, don''t worry so much about HOW you will implement particular elements of your agent, but rather consider the overall design philosophy; i.e., how much will the agent be a deliberative planner and how much a reactive planner.

There are many papers available on these issues, ironically many of them by teams that compete in the Robo-cup soccer tournaments. Check out www.robocup.org for links.

Cheers,

Timkin

Yes this is real robots. Its actually my senior project. There are 10 teams at my school 4 per team. The prototype robots are already built and we have already had a prototype competion. Our vision system is the fastest there is and has a variance of about .4 pixels SO the robot positions and ball position are pretty acurate.

Currently our a.i. is made up of a bunch of states/conditions. We check conditions and decided if we need to change to a different state like getting the ball. Of course we have reactive plays like if your stuck against an opponent or a wall they take precedence over the state plays.

Currently we do some math and stuff to get ourselves behind the ball on the opposite side of our scoring goal with out colliding with it but i was try to search and find out if there are better path finding alogirthms for this type of dynamic enviornment. We have a waypoint stack that you can push on points and pop them off to give a sense of path but we need a solid way to fill up that stack.

any other suggestions...i will look at the previous suggestions give by those above.

I''m not going to give too much away since this is a project where your team is supposed to learn and discover things, but consider discretising your action space and performing search (or decision making) in that, rather than discretising the state space and searching through that.

Cheers,

Timkin