Misplaced Pages

#897102

31-503: One of their early projects was Shakey the Robot , the first general-purpose mobile robot . More recently, the center funded early development of CALO and Siri . The center has also provided the military with various technology. This artificial intelligence -related article is a stub . You can help Misplaced Pages by expanding it . Shakey the Robot Shakey the Robot was

62-478: A breadth-first search would find a route if given enough time, other methods, which "explore" the graph, would tend to reach the destination sooner. An analogy would be a person walking across a room; rather than examining every possible route in advance, the person would generally walk in the direction of the destination and only deviate from the path to avoid an obstruction, and make deviations as minor as possible. Two primary problems of pathfinding are (1) to find

93-562: A better solution: delete U-shaped lakes from the map", he said. The idea was first described by the video game industry , which had a need for planning in large maps with a low amount of CPU time . The concept of using abstraction and heuristics is older and was first mentioned under the name ABSTRIPS (Abstraction-Based STRIPS ) which was used to efficiently search the state spaces of logic games. A similar technique are navigation meshes (navmesh), which are used for geometrical planning in games and multimodal transportation planning which

124-510: A path between two nodes in a graph ; and (2) the shortest path problem —to find the optimal shortest path . Basic algorithms such as breadth-first and depth-first search address the first problem by exhausting all possibilities; starting from the given node, they iterate over all potential paths until they reach the destination node. These algorithms run in O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} , or linear time, where V

155-402: A start node and an "open set" of candidate nodes. At each step, the node in the open set with the lowest distance from the start is examined. The node is marked "closed", and all nodes adjacent to it are added to the open set if they have not already been examined. This process repeats until a path to the destination has been found. Since the lowest distance nodes are examined first, the first time

186-401: A weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic , and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found. If there is a path of length x between the start and finish, and

217-687: Is a generalization of pathfinding. Many multi-agent pathfinding algorithms are generalized from A*, or based on reduction to other well studied problems such as integer linear programming. However, such algorithms are typically incomplete; in other words, not proven to produce a solution within polynomial time. Some parallel approaches, such as Collaborative Diffusion , are based on embarrassingly parallel algorithms spreading multi-agent pathfinding into computational grid structures, e.g., cells similar to cellular automata . A different category of algorithms sacrifice optimality for performance by either making use of known navigation patterns (such as traffic flow) or

248-514: Is acceptable and even desirable, in order to keep the algorithm running quickly. Pathfinding has a history of being included in video games with moving objects or NPCs. Chris Crawford in 1982 described how he "expended a great deal of time" trying to solve a problem with pathfinding in Tanktics , in which computer tanks became trapped on land within U-shaped lakes. "After much wasted effort I discovered

279-427: Is the closest. It will assign a cost of 3 to it, and mark it closed, meaning that its cost will never be reevaluated. Therefore, Dijkstra's cannot evaluate negative edge weights. However, since for many practical purposes there will never be a negative edgeweight, Dijkstra's algorithm is largely suitable for the purpose of pathfinding. A* is a variant of Dijkstra's algorithm with a wide variety of use cases. A* assigns

310-499: Is the number of vertices, and E is the number of edges between vertices. The more complicated problem is finding the optimal path. The exhaustive approach in this case is known as the Bellman–Ford algorithm , which yields a time complexity of O ( | V | | E | ) {\displaystyle O(|V||E|)} , or quadratic time. However, it is not necessary to examine all possible paths to find

341-401: Is utilized in travelling salesman problems with more than one transport vehicle. A map is separated into clusters . On the high-level layer, the path between the clusters is planned. After the plan was found, a second path is planned within a cluster on the lower level. That means, the planning is done in two steps which is a guided local search in the original space. The advantage is that

SECTION 10

#1732863346898

372-446: The shortest path problem , within graph theory , which examines how to identify the path that best meets some criteria (shortest, cheapest, fastest, etc) between two points in a large network. At its core, a pathfinding method searches a graph by starting at one vertex and exploring adjacent nodes until the destination node is reached, generally with the intent of finding the cheapest route. Although graph searching methods such as

403-673: The visibility graph method for finding Euclidean shortest paths among obstacles in the plane. In 1969 the SRI published "SHAKEY: Experimentation in Robot Learning and Planning", a 24-minute video. The project then received media attention. This included an article in the New York Times on April 10, 1969. In 1970, Life referred to Shakey as the "first electronic person"; and in November 1970 National Geographic Magazine covered Shakey and

434-406: The best general algorithms which operate on a graph without preprocessing. However, in practical travel-routing systems, even better time complexities can be attained by algorithms which can pre-process the graph to attain better performance. One such algorithm is contraction hierarchies . A common example of a graph-based pathfinding algorithm is Dijkstra's algorithm . This algorithm begins with

465-400: The capability to execute all the actions within the plan personally. An example mission for Shakey might be something like, an operator types the command "push the block off the platform" at a computer console. Shakey looks around, identifies a platform with a block on it, and locates a ramp in order to reach the platform. Shakey then pushes the ramp over to the platform, rolls up the ramp onto

496-411: The destination is found, the path to it will be the shortest path. Dijkstra's algorithm fails if there is a negative edge weight. In the hypothetical situation where Nodes A, B, and C form a connected undirected graph with edges AB = 3, AC = 4, and BC = −2, the optimal path from A to C costs 1, and the optimal path from A to B costs 2. Dijkstra's Algorithm starting from A will first examine B, as that

527-545: The fields of robotics and artificial intelligence, as well as computer science in general. Some of the more notable results include the development of the A* search algorithm , which is widely used in pathfinding and graph traversal , the process of plotting an efficiently traversable path between points; the Hough transform , which is a feature extraction technique used in image analysis , computer vision , and digital image processing ; and

558-399: The first general-purpose mobile robot able to reason about its own actions. While other robots would have to be instructed on each individual step of completing a larger task, Shakey could analyze commands and break them down into basic chunks by itself. Due to its nature, the project combined research in robotics, computer vision , and natural language processing . Because of this, it was

589-728: The first project that melded logical reasoning and physical action. Shakey was developed at the Artificial Intelligence Center of Stanford Research Institute (now called SRI International ). Some of the most notable results of the project include the A* search algorithm , the Hough transform , and the visibility graph method. Shakey was developed from approximately 1966 through 1972 with Charles Rosen , Nils Nilsson and Peter Hart as project managers. Other major contributors included Alfred Brain, Sven Wahlstrom, Bertram Raphael , Richard Duda , Richard Fikes , Thomas Garvey, Helen Chan Wolf and Michael Wilber. The project

620-556: The future of computers. The Association for the Advancement of Artificial Intelligence 's AI Video Competition's awards are named "Shakeys" because of the significant impact of the 1969 video. Shakey was inducted into Carnegie Mellon University 's Robot Hall of Fame in 2004 alongside such notables as ASIMO and C-3PO . Shakey has been honored with an IEEE Milestone in Electrical Engineering and Computing. Shakey

651-415: The geometrical space are exceedingly large. The first step for a hierarchical path planner is to divide the map into smaller sub-maps. Each cluster has a size of 300x200 nodes. The number of clusters overall is 10x10=100. In the newly created graph the amount of nodes is small, it is possible to navigate between the 100 clusters, but not within the detailed map. If a valid path was found in the high-level-graph

SECTION 20

#1732863346898

682-437: The minimum distance between a node and the finish is greater than x, that node need not be examined. A* uses this heuristic to improve on the behavior relative to Dijkstra's algorithm. When the heuristic evaluates to zero, A* is equivalent to Dijkstra's algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When

713-403: The next step is to plan the path within each cluster. The submap has 300x200 nodes which can be handled by a normal A* pathplanner easily. Multi-agent pathfinding is to find the paths for multiple agents from their current locations to their target locations without colliding with each other, while at the same time optimizing a cost function, such as the sum of the path lengths of all agents. It

744-419: The number of nodes is smaller and the algorithm performs very well. The disadvantage is that a hierarchical pathplanner is difficult to implement. A map has a size of 3000x2000 nodes. Planning a path on a node base would take very long. Even an efficient algorithm will need to compute many possible graphs. The reason is, that such a map would contain 6 million nodes overall and the possibilities to explore

775-431: The optimal one. Algorithms such as A* and Dijkstra's algorithm strategically eliminate paths, either through heuristics or through dynamic programming . By eliminating impossible paths, these algorithms can achieve time complexities as low as O ( | E | log ⁡ ( | V | ) ) {\displaystyle O(|E|\log(|V|))} . The above algorithms are among

806-597: The platform, and pushes the block off the platform. Mission accomplished. Physically, the robot was particularly tall, and had an antenna for a radio link, sonar range finders, a television camera, on-board processors, and collision detection sensors ("bump detectors"). The robot's tall stature and tendency to shake resulted in its name: We worked for a month trying to find a good name for it, ranging from Greek names to whatnot, and then one of us said, 'Hey, it shakes like hell and moves around, let’s just call it Shakey.' The development of Shakey provided far-reaching impact on

837-431: The robot to interact with. Shakey had a short list of available actions within its planner. These actions involved traveling from one location to another, turning the light switches on and off, opening and closing the doors, climbing up and down from rigid objects, and pushing movable objects around. The STRIPS automated planner could devise a plan to enact all the available actions, even though Shakey himself did not have

868-524: The value of the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance, as the same comparison result can often be reached using simpler calculations – for example, using Chebyshev distance over Euclidean distance in two-dimensional space .) As the value of the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many applications (such as video games) this

899-723: Was funded by the Defense Advanced Research Projects Agency (DARPA) based on a SRI proposal submitted in April 1964 for research in "Intelligent Automata". Now retired from active duty, Shakey is currently on view in a glass display case at the Computer History Museum in Mountain View, California . The project inspired numerous other robotics projects, most notably the Centibots . The robot's programming

930-445: Was primarily done in LISP . The Stanford Research Institute Problem Solver (STRIPS) planner it used was conceived as the main planning component for the software it utilized. As the first robot that was a logical, goal-based agent, Shakey experienced a limited world. A version of Shakey's world could contain a number of rooms connected by corridors, with doors and light switches available for

961-459: Was showcased in the BBC's Towards Tomorrow: Robot (1967) documentary. Pathfinding Pathfinding or pathing is the search, by a computer application, for the shortest route between two points. It is a more practical variant on solving mazes . This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph . Pathfinding is closely related to

Artificial Intelligence Center - Misplaced Pages Continue

#897102