Problem Solving:
Problem-solving in AI refers to the capability of Artificial Intelligence systems to find solutions to complex problems using various computational techniques. It involves breaking down a problem into smaller parts, analyzing possible solutions, and selecting the best one based on certain criteria.
Problem solving in Artificial Intelligence is the ability of AI systems to analyze data, identify patterns, and develop solutions to complex problems. AI-driven problem solving can tackle complex problems and offer solutions beyond what traditional methods can achieve.
Formulating Problems in AI:
In artificial intelligence, problem formulation is the process of defining a problem in a way that an AI system can understand and solve it efficiently. Formulating a problem in AI is the process of defining a real-world problem as a computational problem that an AI system can solve.
Formulating problems in AI is a critical step in developing effective solutions. It involves translating real-world challenges into a structured format that can be understood and processed by AI systems.
Effective problem formulation in AI is essential for developing successful solutions. Before an AI system can solve a problem, it must first be formulated in a way that an algorithm can process. This involves defining the problem, identifying constraints, and determining how the AI should search for a solution.
Elements of Problem Formulation in AI (Components of Problem Formulation in AI):
A problem in AI is typically defined by the following elements:
Initial State: The starting point of the problem-solving process.
Example: In a maze-solving problem, the initial state is the agent’s starting position.
Goal State: The desired outcome or objective the AI must achieve.
Example: Reaching the exit of a maze.
State Space: The set of all possible states the problem can have.
Example: All possible positions in a chess game.
Actions (Operators): The set of possible actions, an AI can take to move from one state to another.
Example: In a robot navigation problem, actions could be “move left,” “move right,” “move forward,” etc.
Transition Model: A description of how actions change the current state into a new state.
Example: If the AI moves right in a maze, the new position updates accordingly.
Path Cost: The cost associated with moving between states (e.g., distance, time).
Example: In GPS navigation, path cost could be the distance or time required to reach the destination.
Constraints: Conditions that must be satisfied for a solution to be valid.
Example: In scheduling problems, constraints may include “no two tasks can be scheduled at the same time.”
Types Of Problems in AI:
In Artificial Intelligence (A), problems can be categorized as ignorable, recoverable, or irrecoverable. AI systems are designed to solve problems by mimicking human intelligence.
Ignorable Problems: These are problems where certain solution steps can be skipped or ignored without affecting the overall outcome.
Recoverable Problems: Problems where mistakes can be corrected or undone, allowing flexibility in the problem-solving process.
Irrecoverable Problems: Problems where actions are permanent (irreversible) and require careful planning.
States and Operators:
In Artificial Intelligence, “states” represent different configurations or situations within a problem, while “operators” are the actions that can be taken to transition between these states.
In short, we can say, a state describes the current situations, and an operator is a function that allows us to move from one state to another.
State Space:
A state space is a set of all possible states that it can reach from the current state. In Artificial Intelligence, a state space is a model of all possible configurations of a problem.
Search Strategies:
Search strategies or Search Algorithms in Artificial Intelligence, are algorithms that help to solve search problems. They are used to find solutions in a search space.
Search in AI:
Search is a fundamental concept in AI that involves exploring possible solutions to find the best or optimal one. Search in AI refers to the process of navigating through a problem space to find a solution. The AI agent explores possible states and actions using a search strategy.
Example: Finding the shortest route on Google Maps involves searching through multiple paths to find the best one.
Types of Search Algorithm:
Based on the search problems, we can classify the search algorithm as
- Uninformed Search
- Informed Search
Uninformed Search Algorithms:
Uninformed search algorithms explore the state space without prior knowledge about the goal location. They rely only on the structure of the problem.
The uninformed search algorithm does not have any domain knowledge, such as closeness, location of the goal state, etc. These algorithms do not use problem-specific knowledge and explore the state space blindly. This algorithm is also known as the Blind Search algorithm or brute-force algorithm.
Examples:
Breadth-First Search (BFS)
It is one of the most common search strategies. A breadth-first search generally starts from the root node, examines the neighbour nodes, and then moves to the next level. It uses the First-in, First-out (FIFO) strategy as it gives the shortest path to achieving the solution. The BFS algorithm starts with the start state, moves to the next level, and visits each node until it reaches the goal state.
- Explores all nodes at the current level before moving to the next.
- Guarantees the shortest path if all costs are equal.
- Uses a queue (FIFO) data structure for exploration.
Example: Used in shortest path problems where all moves have equal cost.
Advantages:
- BFS will never be trapped in any unwanted nodes.
- If the graph has more than one solution, then BFS will return the optimal solution with the shortest path.
Disadvantages:
- BFS stores all the nodes in the current level and then moves them to the next level. This requires a lot of memory.
- BFS takes more time to reach the goal state, which is far away.
Depth-First Search (DFS)
The depth-first search uses Last-in, First-out (LIFO) strategy and hence it can be implemented by using stack. DFS uses backtracking. It starts from the initial state and explores each path to its greatest depth before it moves to the next path.
- Explores as far as possible along one path before backtracking.
- Uses a stack (LIFO).
- May get stuck in infinite loops unless depth limits are set.
Example: Solving mazes by going deep into one path before trying alternatives.
Advantages:
- It takes lesser memory as compared to BFS.
- The time complexity is lesser when compared to BFS.
- DFS does not require much more search.
Disadvantages:
- DFS does not always guarantee to give a solution.
- As DFS goes deep down, it may get trapped in an infinite loop.
Uniform Cost Search (UCS)
Uniform cost search is considered the best search algorithm for a weighted graph or graph with costs. It searches the graph by giving maximum priority to the lowest cumulative cost. Uniform cost search can be implemented using a priority queue.
- Expands the least-cost node first, based on the path cost function.
- Guarantees the optimal solution.
- Uses a priority queue sorted by path cost.
Example: Finding the shortest path in Google Maps.
Advantages:
- This algorithm is optimal as the selection of paths is based on the lowest cost.
Disadvantages:
- The algorithm does not consider how many steps it takes to reach the lowest path. This may result in an infinite loop also.
Informed Search:
Informed search algorithms use heuristic functions to guide the search toward the goal, making them more efficient. These algorithms use problem-specific knowledge (heuristics) to find solutions faster. The informed search algorithm is also called Heuristic Search.
Informed search algorithms use domain-specific knowledge to improve efficiency, use heuristics to guide the search process more efficiently. In contrast to uninformed search algorithms, informed search algorithms require details such as distance to reach the goal, steps to reach the goal, and cost of the paths, which makes this algorithm more efficient.
Examples:
Greedy Best-First Search
Greedy best-first search uses the properties of both depth-first search and breadth-first search. It traverses the node by selecting the path that appears best at the moment. The closest path is selected using the heuristic function.
- Expands the node that appears closest to the goal based on a heuristic function h(n).
- Uses a priority queue based on h(n).
- May not find the optimal solution.
Example: Navigating a maze by always moving toward the goal.
Advantages:
- More efficient compared with breadth-first search and depth-first search.
Disadvantages:
- In the worst-case scenario, the greedy best-first search algorithm may behave like an unguided DFS.
- There are some possibilities for greedy best-first to get trapped in an infinite loop.
- The algorithm is not an optimal one.
A* Search Algorithm:
A* search algorithm is a combination of uniform cost search and greedy best-first search algorithms. It combines the advantages of both with better memory usage. It uses a heuristic function to find the shortest path. A* search algorithm uses the sum of the node’s cost and heuristic to find the best path.
- Uses both path cost g(n) and heuristic h(n):
f(n)=g(n)+h(n)
Where g is the cost function of the path from the initial state to the node n and h is the heuristic function that estimates the cost from n to the goal state.
- Guarantees the optimal solution if h(n) is admissible (never overestimates).
Example: AI in video games calculating the shortest route for a character.
Advantages:
- This algorithm is best when compared with other algorithms.
- This algorithm can be used to solve very complex problems, and it is an optimal one.
Disadvantages:
- It does not always produce shortest path.
- It is not practical for various large-scale problems.
Comparison of Uninformed and Informed Search Algorithms
Uninformed search is also known as blind search, whereas informed search is also called Heuristics Search. Uniformed search does not require much information, whereas informed search requires domain-specific details. Compared to uninformed search, informed search strategies are more efficient, and the time complexity of uninformed search strategies is greater. Informed search handles the problem better than blind search.