Pathfinding, when used in video games and artificial intelligence, typically means an object or entity’s ability to navigate its surroundings. This also works for robotics, though there is one distinct difference: navigating a space where they don’t know where they’re going. Like a blind baby crawling for the first time. In video games, this is a relatively mundane obstacle that every game A.I. has to wrestle, but in robotics, this has some trappings. As a video game, little is at risk when an entity is pushed through a corner and some minor graphical “clipping” occurs, but when you’re talking about a million dollar team project representing years of dedication… well, it matters where you’re going and how safely you get there.
Video Games, the First Approaches
Typically, early video games used barrier or border systems and collision detection to determine a lot of their pathfinding, along with direct path approaches (which are when enemies just move straight for the character without much other consideration, much like Pac-Man or Ghosts in Super Mario Brothers). There was also the Set Pattern method, meaning that enemies didn’t really differ much from game session to game session, as they did in Space Invaders or again, Super Mario. There’s the random methods used by Asteroids, where they would just float around after being blasted, and the scripted or triggered events. These often worked in groups and each game’s artificial intelligence may use several different methods to approach their pathfinding needs. Often different enemy types will use different pathfinding options to change their behavior.
Video Games, A*
Then there’s the A* (or A-Star) approach to pathfinding, which has become a more accurate way to determine a path, using nodes and values related to terrain and other factors to determine the “easiest way” or of any route is available at all. This is by far the most popular method for most modern games, but has one downfall that robotics don’t typically have the benefit of, and that is that they know where their map is. In A* this is represented by a Node Map, which tells the A.I. or pathfinding system where the nodes are, which areas are blocked or off limits, where trigger areas are or spawn points. These Node Maps also often give the A.I. some general idea of default movements or paths to follow as they jump from Node to Node, often recalculating portions of the path as events change.
Video Games, Using Rays as a More Modern Approach
Rays are a more modern response to the pathfinding problem. In this system, each character has a virtual ray that is cast a short distance in front of them, and then the ray is tested for collision, which is how most driving games have worked things for a long time. Using rays of various lengths and using an implied line if sight that is constantly projected at varying intervals, with a constantly adjusting path is more along the lines of a modern video game and allows developers to work with terrain that isn’t pre-generated, but rather rendered randomly or updated as game-events change landscapes and terrain. The use of rays as opposed to a node map means that each individual character in the game or system has their own individual look at the map and can remember individual locations or events and otherwise tag locations for later use, like a quick and easy path home.
Robotics, Controlled
The area of robotics where they are designed to be interacted with or rather, by humans, is where video games and robotics are the most similar. Instead of controlling a computer game character, the player, or user in this case, controls the robot itself. The control may be through something such as a remote control device like a PlayStation controller or even a more typical RC Car or plane style controller. It could also be a suit, such as a Heinlein-esque Starship Troopers power suit or even an arcade-style riding game with servos, where the player or user is directing the action. Pathfinding in this scenario is irrelevant because it is handled by a user rather than an A.I., but a control interface is required in its place.
Robotics, Patterned
This is the “Space Invaders” scenario from above, but applied to robotics. This is also the way that most robots function in today’s market. Patterned movements are great for repetitive tasks just that those required in most manufacturing facilities, it’s no wonder that today’s manufacturers are utilizing more and more robots that are designed for very specific and complex actions, which are almost always pre-programmed for the robot to do, at very specific pressure points and calibrations. Pathfinding with these devices is depends solely on the manufacturer and the intended use of the device, but often uses one of the other methods in conjunction with its known bank of preset patterns or robotic tasks it can perform.
Robotics, Random
The purely random approach to robotic pathfinding is one at least worth investigating. It involves things like motorized balls or wheels that run simple devices like sweepers or toys. These items often simply move in a direction until they can’t or until they fall over. Their path finding is more or less “point and go” without much regard for what may lay in that direction or regard as to how it will get there. They rely on being used in the manner designed and for a specific purpose, but without much versatility.
Robotics, Visual
A relatively new, and certainly more complex and evolving, approach to robotic pathfinding relies on cameras and giving the robot some capacity for sight or vision. The complexity of the pathfinding expected generates the difficulty and overall scope of the projects, ranging from camera quality, speed of the robot or device and type of terrain. Using a camera is difficult when determining speed because of the sheer amount of information that has to be processed and monitored can make travel at high rates unsafe. This method typically utilizes rays, as do modern video games, in order to create their own paths around or over their desired terrain. A lot of this aspect of pathfinding requires that the robot know a good amount of information about itself. This information needs to be accurate and needs a way of being updated otherwise errors, changes or damage could be catastrophic.
Robotics, Mapping
This method of pathfinding also utilizes the ray method and is also often used with other methods of pathfinding in order to maximize its usefulness. With this method, the A.I. attempts to create a map of what it knows of the environment. This is also similar to the Ray method in that software is typically utilized to determine a safe boundary for the robot to navigate with no expected issues. This information is then saved and used to track progress, mark locations or simply reference a journey. This can be accomplished using cameras along with the vision method above, or it can be done using GPS, radar or any other method. Maps created this way are useful, not only for the robot itself, but as critical intel for remote locations such as underwater mapping or getting information about mines or tunnels.
Conclusion
Video games and robotics share so much in how they cause people to interact with computer systems. Whether or not it’s for fun, or for education, or to help increase production, the intelligence required to rotate servos, spin wheels and navigate a physical machine is oddly similar and integrated with how a virtual character would navigate a level in your favorite video game, but with some differences. A lot of this depends on how much time developers feel like putting into their game’s AI, just like it matters how much time the robot’s creator wants to invest in their own pathfinding algorithms. Much of this has been demonstrated by the car industries and various university projects around the world, with DARPA sponsoring a number of AI pathfinding competitions with rather strict rules, requirements and restrictions.
Comments