Getting closer to the goal is generally considered good, but it may lead to dead ends or non-optimal choices.
Knowing the minimum path length to the goal, the search algorithm records the length of path already extended and always extends the shortest path first until all paths are longer than the known shortest length.
Branch & Bound
With the same principle, if the shortest path is not known yet (no “Oracle”) paths are extended to the goal and recorded. Other paths are extended until the are as long or longer than the current shortest path to the goal.
The algorithms extends the first path and then sorts them by length.
Branch & Bound + Extended List
In addition to the branch and bound algorithm, new branches that lead back to node previously extended with a longer path are discarded.
Branch & Bound + Admissible Heuristic
The estimated remaining distance to the goal is added to the path extended. Only the shortest path extended + remaining estimated distance is extended until the goal is reached. All longer paths are discarded.
In the algorithm, instead of sorting extensions to put the shortest paths (leading to many calculations), only test if the shortest path leads to the goal.
In certain cases (especially not about maps), the Admissible Heuristic may lead to problems. The consistency heuristic uses a stronger condition, namely that the distance to the goal from a given node x, minus the distance to the goal from another node y, in absolute value, has to be inferior to the distance between x and y.
Search trees represent all the possibilities to search for the quickest path without coming back to previous paths. They are particularly used for quickest paths on maps with nodes (intersections), but not exclusively. They are primarily about choices, and finding the best sequence of choices.
British Museum Algorithm = complete expansion of all paths
Depth First vs Breadth First Search Algorithms
Depth First Search Algorithm starts by going down one level from the left by convention until the goal is reached. The program goes back up to the previous node if the goal is not reached, a process called “back up” or “backtracking“.
Breadth First Search Algorithm expands the search level by level, exploring all possibilities of one level before going down.
Both Depth First and Breadth First Algorithms use enqueued lists to extend the paths to goals and discard paths that lead to points that have already been extended.
Hill Climbing Search Algorithm
The search tree is always extended towards the node that is closer to the goal.
Hill Climbing is an informed search making use of certain heuristic information.
Beam Search Algorithm
A beam search algorithm is limiting the number of nodes extended at each node. It only extends nodes that go towards the goal, according to certain heuristics.
En-queuing the next nodes if the goal is not reached, the algorithms process as follow:
Depth First: new nodes go to front of the queue
Breadth First: new nodes go to front of the queue
Hill Climbing: sort the node closest to the goal first
Beam: keep only a small number of nodes in the queue
Best First Search Algorithm
Chooses of all en-queued nodes to extend the one that is closest to the goal.
Search algorithms can be used in continuous spaces. However, Hill Climbing can encounter certain problems, such as:
getting blocked at a local maximum
the telephone pole problem: getting confused at a flat level between high rising parts of the space
especially in high dimensional spaces, getting fooled by a particular configuration of space borders that prevent extensions as all paths seem to lead away from the goal
An ant’s apparently complex behavior stems from the obstacles in its environment to avoid on its way home.
Rule-Based Expert Systems
Rule-based “expert” systems are deductions systems, they can answer questions about their behaviors as they are a form of goal trees.
Forward-chaining rule-based expert systems work from characteristics to deduce a result by a set of rules. Backward-chaining rule-based expert systems verify a proposition is true by going back to the check its characteristics through the rules.
Heuristics of knowledge engineering
How to set the program’s rules:
Deal with specific cases: know all details of each specific case, not vague, general ideas from people (potato chips, tomatoes vs “squishy”)
Understand the vocabulary items that make two cases different (frozen vs canned)
Analyze when the program breaks down to understand the missing rule.
Take a complicate problem and transform it into a simpler problem.
Start with safe transformations, the ones you are sure will work in any case. Then apply heuristic transformations, the ones that could work.
The problem simplification schema, may create “and node“, where the problem forks in several sub problems and “or node” where the problem may be solved with either one or another transformation. The resulting schema is usually called a “problem reduction tree“, “and/or tree” or “goal tree“.
In an “or node”, it helps to understand the depth of functional composition (number of transformations to be applied after and “or” options of the branch) and the simplicity of solving each options to complete the problem resolution.
Everything depends on the domain of the problem and the knowledge required to solve it. Knowledge about knowledge, meta-knowledge, is power to solve problems.
Start by evaluating what kind of knowledge is involved.
Understand how the knowledge is represented. Each category of knowledge has its own way of being represented.
Know how the knowledge is used.
Know how much knowledge is required to solve the problem.
Know what exactly knowledge does to solve the problem.
Algorithms, enabled by constraints, exposed by representations, that support the building of models targeted at thinking, perception and action, and the loops that tie them together.
Artificial Intelligence is applied through problem solving procedures, methods, techniques and algorithms.
How to approach a problem
Generate solutions and test to obtain positive or negative results.
This approach involved building generators with certain properties: not redundant (should not give the same solution twice), they should also be informable (able to select a category and disregard other)
Being able to name what you’re talking about gives you power over it, to understand and solve problems. Naming things grants power over concepts.
Difference between trivial and simple
Trivial ideas implies that they are worthless, useless. In AI, the most simple ideas are often the most powerful.
The benefits of language
Enables to tell stories
Enables to marshal the resources of the perceptual apparatus. It lets us imagine things that we never saw before.