Steve_Rayhawk comments on AI Challenge: Ants - Less Wrong

17 Post author: lavalamp 03 November 2011 03:31PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (49)

You are viewing a single comment's thread.

Comment author: Steve_Rayhawk 07 November 2011 02:15:29PM *  5 points [-]

I would not expect to win without a method that I could see to approximate or to exceed linear-programming formulations of multi-agent path planning, for example here (2005/2008) or here (2001). Those methods don't fully cover the stochasticity of resource gathering or the adversariality of combat, but they partly cover resource-finding and patrolling (when up-to-date visual information about unknowns is an objective) and deployment, and they provide a framework into which to fit tradeoffs among options evaluated by more specialized models, such as for combat, exploration, or gathering.

One approximation would be a relaxation of the ant indicator function to a basis of wavelet-like vectors (for example diffusion kernels) on the graph of connected land squares. (The basis vectors should overlap smoothly, because under a rigorous relaxation, non-overlapping basis vectors would allow approximated ants to teleport across the support of basis elements.)

Comment author: lavalamp 07 November 2011 05:20:20PM 1 point [-]

Lots of food for thought there. Clearly I didn't have enough math in college.

For global ant allocation and food gathering, it's very possible that the approach you're describing is the best you could practically do. For more local combat situations, though, I don't think that's clear at all-- if I had infinite computing resources, I'd be using an appropriate adaptation of minimax.

Anyway, you gave me some words for concepts and some new concepts, so upvote for you.