Algorithms and Abstractions of Them
The basic search strategies enumerated in the question are indeed algorithms, but abstract ones. We shall see below why, in actual practice, these abstractions are realized by any number of more concrete algorithms including the detail necessary in practical application.
The abstract searching algorithms are not limited to these five either. There are hundreds of variations extending these five abstract algorithms described in the literature.
Some are re-entrant, meaning that they can be invoked again and capitalize on information persisted between invocations. These continuously learning algorithms and associated knowledge representations are of particular importance for practical robotics.
The first re-entrant search strategy successfully demonstrated in a robot was more sophisticated than any of the strategies mentioned in this question. It was a maze-learning electro-mechanical mouse named Theseus, constructed by Claude Shannon in 1950 at Bell Labs.1 Although it used an algorithm, it was not a programmed algorithm because the CPUs of the time would have required a mouse larger than a bus to execute the algorithm. It was a searching circuit constructed of relays, a battery, and a two motors.
Let's first define terms.
- A robot is an artificial device that exerts some impact on its physical environment.
- An algorithm is a definable structure comprised of actions the exact sequence of which may be either fixed or conditioned upon state which may be conditioned upon one or more of the actions.
- A tree search algorithm is an algorithm that searches a graph of vertices and directed edges, where all vertices have either zero or one incoming edge, for some vertex or vertices based on some definite set of criteria.
- A graph search algorithm is an algorithm that searches a graph of vertices and directed edges for some vertex or vertices based on some definite set of criteria.
Note that a tree is a special case of a graph.
For unveil the meaning behind the basic abstract search acronyms, simply expanding them reveals much.
- BFS — breadth first search
- DFS — depth first search
- UFC — uniform cost search
- DLS — depth limited search
- IDS — iterative deepening search
What Differentiates Abstract Search Algorithms
At an even higher level of abstraction, each of these and the dozens more not mentioned in the question are based on the control of two aspects of the search.
- Conditions of search termination
- Determinants of what vertex to test next
Various combinations of termination criteria and traversal determination impact search metrics. Note that finding one match may not be cause to terminate if the intention is to find all matches and submit them to a queue for processing, a common system design pattern used in industrial and household robots.
All of these quantitative metrics used to select the best termination criteria and traversal determination scheme are probabilistic distributions because a priori knowledge of the location of matches is always incomplete or zero.1 If that were not so, there would be no need to search. Each of these distributions of course have associated maximum and mean values.
- Resource requirement probability distribution
- Time probability distribution
- CPU utilization distribution
- Memory utilization distribution
These distributions and their means and maximums along with a number of other factors drive the selection of search algorithm.
- Hardware configuration
- Exploitable parallelism in hardware
- Operating system
- Execution model
- Efficiency of compilation result
- Number of vertices
- Topology of the network
- Distribution of edge fan-out
- Attributes of each vertex
- Attributes of each edge
Returning to the point that the acronyms in the question are abstractions of practical algorithms, several other kinds of details are part of the strictly definable algorithms that correspond to directions required to run the search on computer hardware in some language Details of the structures representing the graph and possibly a graph library interface exposed through an API include these.
- Methods for edges traversal
- Methods for determination of cost
- Methods for matching of vertices
- Ways to avoid redundancy
- Ways to avoid endless loops in cyclic graph structure (cycles)
- Persistence of information (storage, indexing, recall)
- Whether cycles are prohibited and what mechanism prohibits them
- Whether the graph is modified during the search
- Whether clues (deliberate) can exist along the search path
- Whether traversal modifies search likelihoods (incidental)
The choice of algorithm is commonly based on the characteristics of the search space and what can be known prior to and during the search. These change the expectation space and point in the direction of one search abstraction or another, the details of which can be chosen afterward.
If the vertices that match are more likely to be close to the vertex at which the search begins, then the breadth first search may be best. Since breadth first searches tend to use more memory than a depth first search, if the objective is to find the full set of matching vertices randomly located, a depth first is the better choice.
Terminating the search at a given depth makes sense if the cost of the search is considered comparable to success at matching. There may be a point when searching further is considered too unlikely to be fruitful to incur the cost.
Where are all these algorithms are used?
In robots whose designers assessed resource availability and the importance of the goal and decided upon the correct termination criteria and traversal determination for the particular task.
which algorithm is mostly used in Robots.
There is no global rule that spans all things robots commonly do or are hoped to perform in the future. There are a few common matches between search algorithms and common tasks however.
- Since backtracking in physical space is inefficient, depth first searches are more than breadth first searches when the testing of locations requires physically travelling to them.
- Visual systems tend to do a breadth first search, since changing camera angle produces a higher reliability in perusal of recognized objects from close up than random travel to get close to additional objects for recognition purposes.
In the case of audio data arriving at the robot's microphone or microphones, an additional search type may be used. The nearby potential noise sources may already be discounted and distant sounds with dynamic complexity may be searched first. One might call this reverse depth first search, and there may be ways to invert it so that a breadth first algorithm may be applied first. Such tricks are common in biological neural systems and can be leveraged in robots.
It is very rare when any of the searches mentioned in the question will produce a robust robotic algorithm. There are several reasons.
- The pertinent graph of vertices, edges, and their associated attributes contained in the memory of the robot (whether in dynamic memory, automatic memory, or persisted) is subjective. It is either 100% reliable nor 100% accurate with respect to the environmental state. Technically, it can never be. This subjective representation will change in real time as the robot moves and discovers new information.
- When the robot interacts with the environment, it will often do so with the intention of modifying the objective reality the graph represents that, whether successful or not, will likely change the graph.
- The value of computing resources may change due to change in the environment or the availability of energy for propulsion and computing.
- Windows of opportunity may have finite start and end times that may possibly be variable and may possibly be unknown. The urgency of a task may modify what search algorithms should be used.
- Urgency may be a function of the number of queued tasks.
In these cases, the information gained from one algorithm may need transferal to the initial state of another algorithm to avoid redundancy in vertex testing.
Explain with example.
Here are two.
Human beings use a hybrid of all these algorithms. Young humans go out to locations based on partial information and search in a predominantly breadth first way. As objectives are clarified, a depth first approach may prevail, but not completely, since the number of vertices that can be tested are capped not by depth or cost but by the need to return to home to eat or sleep, the decision of which could be postponed. Later in life, the search path is traversed without leaving the home and the path is traversed without checking many vertices.
Tactical planning is closely related to uniform cost search. Such is most useful when the intention of the search is to remain hidden until reconnaissance and planning is complete. This is a tactical approach that leverages what can be obtained about costs to minimize the time of the search in the hope that adversaries that may not be aware of the existence or location of the objective do not use the robot's search behavior to gain such information.
 A robot may have bits of knowledge from past travels, collaborative connections with other devices, or as a result of forward recognizance via visual, IR, UV, or auditory senses. For instance, Claude Shannon's maze-learning electro-mechanical mouse, Theseus, gained knowledge of the maze and the location of the objective with each placement into the maze.