Robot AI

Robot AI

Post just about everything that isn't directly related to Spring here!

Moderator: Moderators

Post Reply
User avatar
Wisse
Posts: 263
Joined: 10 Jul 2006, 17:50

Robot AI

Post by Wisse »

Hi again -.-

Me and four other classmates are set to build a robot for Eurobot 2011: Chess'UP! Robot is supposed to be completely autonomous while playing 1v1 game against foe robot on specified playing table with specified playing objects. If anyone wants more details on that I'll be happy to oblige.

I've come here because I need some advice, guidelines or just simple directions in building AI for the task. Since we're mechanical engineering (mechatronics) under-graduates, we don't have any real formal training about the issue (AI, algorithms...). One of the guys on the team does happen to be professional programer tho, while the rest of us are also capable of producing some useful code if given enough time.

Just to be clear. I've already done some quick research, but mostly on pathfinding. I'm happy to search more info on my own as I'm not that lazy, but I think that things could go much faster if you guys point me towards some good reading or give me any kind of advice, since I suspect that there's quite a lot of knowledge floating around in Spring community.

I started this thread in Off topic because it has nothing to do with Spring explicitly.

Short summary of game mechanics:
Game is played on following table:
Image
Each robot is assigned to one color, red or blue. You have 90 seconds to move that yellow playing objects. You can also build towers to get more points. You only get points for objects placed on your color, which makes stealing valid tactics!

Let's assume, for further discussion, that our robot knows positions of every playing element and foe robot at any time.

Points of interest:
- Decision making
- Pathfinding
- Misc

Tech specs:
- Programming language: C# (not debatable)
- Fully fledged PC (C2D E5500, 4GB RAM, SSD)

Time frame:
- 3 to 4 months :(


Decision making
I've build Battle ship "AI" in C before and I've done some simple decision making in other apps, but mostly using IF and Case statements. That worked great, but only for discrete decisions. The code also became quite hefty really fast, while enabling only limited number of decisions.

I now want to figure out, what's the best approach to AI from efficiency stand point. Our game is not very complex, but it's very very dynamical, which calls for unconventional decisions at the right time. I don't want to write everything down with IF statements. Things like machine learning are far far in the backlog and will be considered only if we make some unexpected progress.

Where do we start? What kind of terminology is used in AI programming (for more effective searching)? How complex do you think our solution could be in given time frame and amount of prior knowledge?

Pathfinding
As I mentioned earlier, I already did some quick pathfinding research. I immediately came across Dijkstra's algorithm and it's derivative A*. I think I have good enough understanding of A* to implement it in one way or another. I figure it's the right choice for our application and it shouldn't be problematic in CPU usage aspects also, because we only have 2 robots, 15 playing elements and rather small surface.

What do you thing about A* for our task? Any literature recommendations? Any alternatives?

Misc
"Decision making" is such a general title that I covered many points of interest with it. I'll see how this topic develops and try to provide with more specifics if needed, breaking everything down to simpler tasks.

Thank you!
Wisse
User avatar
knorke
Posts: 7971
Joined: 22 Feb 2006, 01:02

Re: Robot AI

Post by knorke »

what does your robot look like? how fast/precise can it move mechanical wise?
for navigating waypoints:
http://en.wikipedia.org/wiki/Travelling ... an_problem
instead of a complete ai maybe make a state machine:
http://en.wikipedia.org/wiki/Finite-state_machine
User avatar
Wisse
Posts: 263
Joined: 10 Jul 2006, 17:50

Re: Robot AI

Post by Wisse »

Robot looks like little vehicle with only 2 wheels. It will be able to turn around it's center point (example). Construction is still in progress.

Precision will be about 1mm I guess.
User avatar
Teutooni
Posts: 717
Joined: 01 Dec 2007, 17:21

Re: Robot AI

Post by Teutooni »

Wisse wrote:point me towards some good reading
http://en.wikipedia.org/wiki/Artificial ... n_Approach

I'm taking an AI course atm, and that is the textbook we use. Haven't gotten my hands on one though (course started few weeks ago...).
User avatar
KaiserJ
Community Representative
Posts: 3113
Joined: 08 Sep 2008, 22:59

Re: Robot AI

Post by KaiserJ »

wouldnt the best idea be to have your robot quickly move to the edge of the enemy dispensing area, wait for the enemy bot, and shove him off the table? or is this not a contact sport
User avatar
SinbadEV
Posts: 6475
Joined: 02 May 2005, 03:56

Re: Robot AI

Post by SinbadEV »

When I made "robots" to play games in HS we drove them with remote controls and my team almost always lost so I can't give advice on that front... :roll:

That said, I found a really fun thing in C# (well .NET in general) when I needed to do some fun mathematical simulations... you can use your if and case statements to build a "script" and compile it and execute it as a method all at run time... it speeds up the execution of code significantly without you having to learn how to program any better.

I don't know if it helps you but I figured I'd mention it.
User avatar
Wisse
Posts: 263
Joined: 10 Jul 2006, 17:50

Re: Robot AI

Post by Wisse »

KaiserJ wrote:wouldnt the best idea be to have your robot quickly move to the edge of the enemy dispensing area, wait for the enemy bot, and shove him off the table? or is this not a contact sport
Troll much? Intentional contacts are not allowed.


@All above: Thx for info! We're looking into it. Off course we would appreciate even more.
Google_Frog
Moderator
Posts: 2464
Joined: 12 Oct 2007, 09:24

Re: Robot AI

Post by Google_Frog »

Wisse wrote:Troll much? Intentional contacts are not allowed.
How do they judge intentional, could you feign incompetence?
User avatar
Wisse
Posts: 263
Joined: 10 Jul 2006, 17:50

Re: Robot AI

Post by Wisse »

They test your robot against dummy to see if you have collision prevention methods in place. You mustn't hit dummy at any time.

Collisions do happen during competition tho and it's up to judge to decide what kind of measure will be taken. Usually they let it pass as long as you didn't inflict any kind of damage to foe robot, or forced it to stall.

I'm not sure what this has to do with AI. I didn't plan to debate tactics here after all.
User avatar
Neddie
Community Lead
Posts: 9406
Joined: 10 Apr 2006, 05:05

Re: Robot AI

Post by Neddie »

Well, the functionality of the AI you develop will reflect the tactics you favour.

I'm worried about your key assumption, where your robot is omniscient within the scope of the game. I mean, perhaps you have a method of ensuring it is, but even if you're using omnidirectional optics and shape/colour recognition, it could develop blind spots as the game progresses and pieces stack. This might even be a valid tactic - walling off the other robot by placing pieces near it, preventing it from navigating effectively.

I've never constructed an AI, but I have read about architecture and it was one of my interests several years ago. I've been working on some projects of late in a team environment (Don't Ask) and have realized that when it comes to software, you have to weigh the difficulty of a task against the utility of the product and prioritize key options. That is to say, formulate the least complex yet effective decision making system you can, prototype it, and then you can expand it with conditionals to handle less and less common tasks. That is a design standpoint, not a performance standpoint, but maybe it will help.
User avatar
Wisse
Posts: 263
Joined: 10 Jul 2006, 17:50

Re: Robot AI

Post by Wisse »

It's true that AI will reflect the tactics, but that's one part, which I'm not willing to openly discuss. I don't mind others knowing our approach and our hardware, because I hope that we'll eventually publish this (months before competition). Tactics on the other hand will have to stay private as it's fairly easy to build counter tactics. There are other very very capable teams competing, which means that we'll sometimes have to rely on wits alone in order to even stand a chance.

We are trying hard to make robot as omniscient as possible. Of course there will be blind spots, which we have to take into account.

Your advice is sound and we're all in favor of that approach from the beginning.
What I want to know, which is also what drove me to consult you guys, is how to approach AI development from the start in order to keep it as simple as possible but still upgradable. Upgradable is the strongest point here, that's why we need to start (or at least try) building platform in the right direction. If we're confident that it's upgradable we can start with only few very basic tasks and improve on those as we learn more and more about the topic from more and practical tests.
Post Reply

Return to “Off Topic Discussion”