Algorithm for Building Structures with Virtual Robots
by David Kerr
Overview: The user builds a three-dimensional structure with blocks, which is destroyed. A group of virtual robots work together to rebuild the structure in the shortest time possible. The physics are simulated using a subset of rigid body dynamics. The environment is similar to that shown in GoalBot.
Algorithm:
There are two major components of the algorithm:
1) Global planner: This is the overall plan, a list of blocks to move and a choice of which agent will move it.
2) Individual planner: Each individual agent is required to move a block from point A to point B, in the fastest time possible.
There is only one global planner, and [1..n] individual planners. The algorithm uses depth-first search using variable heuristics running in parallel, picking the best result from among the matches. This is akin to dynamic multi-threaded pathfinding. See WinPath for my implementation of A* using multiple heuristics.
Adaptability: This algorithm requires time to complete (ie the time it takes each agent to move a block), time in which the environment might change. As such, the algorithm does not make a solid plan. Instead, it replans at each step in time, to account for possible changes. For example an obstacle might be placed in front of an agent, or the user may explode the structure again. In every case the algorithm must adapt as it is running.
Applications: This could have applications in the real world, where robots on Mars would have to build a space station, while accounting for environmental changes. It could also be used in virtual reality games, where artificial intelligences build shelters and assemble virtual structures for the user.
Modifications: Since the agents are given a specific desire (Move Block from A to B), the agent could be given alternate desires (Keep Health Above 500), and the reasoning process may result in interesting behaviours.
Algorithm in Detail
The algorithm and source code is not public.
If you wish to learn more, contact me for information.
I would like to do this or some similar project for a University Masters of AI Degree.
David Kerr