Propositional Logic Quiz

Search Strategies for Solving Problems

• Uninformed Search: Algorithms relying solely on the problem definition for information. They generate successors and differentiate between goal and non-goal states. Strategies that evaluate a non-goal state in comparison to another non-goal state based on their promise are called informed or heuristic searches.

Search Strategies

• Breadth-First Search: A systematic approach, expanding the root node first, then all other nodes. It explores all nodes at depth d before exploring nodes at depth d+1.

  • Pros: Exhaustive, complete, and optimal (if path cost is a non-decreasing function of depth). Optimal, because the cost of a path is a non-decreasing function of depth.
  • Cons: Time complexity of O(bd1), which can be exponential. High memory requirement.

• Depth-First Search: This strategy expands a node at the deepest level of the tree, moving down until a solution is found or no further expansion is possible. It backtracks to explore other branches if no solutions are found at the current branch.

  • Pros: Low memory requirements.
  • Cons: Not complete and not optimal, as it may get stuck in infinitely deep parts of the search space.

• Uniform-Cost Search: This strategy expands the path with the lowest cumulative cost at each step. It prioritizes exploration of nodes promising earlier solution finding.

  • Pros: Complete and optimal.
  • Cons: Time complexity is O(b^c/e). High memory requirement.

• Depth-Limited Search: It's a variant of depth-first search with a constraint on the maximum depth it can explore. This helps mitigate issues with infinite depths.

  • Pros: Lower memory requirements than unlimited depth-first.
  • Cons: Not complete, not optimal. Depth needs to be carefully set.

• Iterative Deepening Search: This combines depth-limited and depth-first approaches by incrementally increasing the depth limit for each iteration of the depth-first search. This ensures that solutions, if available, will eventually be found.

  • Pros: Combining systematic search (depth-first) with completeness (breadth-first).
  • Cons: Some nodes are repeated during iterations, but it has a space and time complexity profile that is similar to the space of breadth-first search. Time complexity of O(b^d).

• Bidirectional Search: This strategy runs two breadth-first searches simultaneously: one forward from the initial state, and one backward from the goal state. The search terminates when the two searches meet at a common node.

  • Pros: Time complexity reduces to O(b^d/2), potential for an exponential speedup over uninformed searches.
  • Cons: Finding the goal is not guaranteed if the forward and backward searches don't cross. Only applicable to problems where a return path can be found.

Avoiding Repeated States

• Repeated states can hinder solvability in a search problem.

Search with Imperfect Information

• Sensorless Problems: If an agent lacks sensors, it might start in one of several possible initial states, and each action could lead to multiple successor states. This complicates the search space.
• Contingency Problems: Agents in environments that are partially observable receive new information after each action, representing various possibilities.
• Adversarial Problems: Uncertainty arises from the actions of other agents, making the problem adversarial.
• Exploration Problems: If the environment's states and actions are unknown, an agent needs to explore to discover them. Exploration problems can be seen as the most complex contingency problems.

Example: The Vacuum Cleaner World

• Demonstrates sensorless agent decision-making. The agent lacks sensors, but can execute actions like moving Right/Left, Sucking up dirt. To navigate the environment the agent must take actions to achieve a desired result, with varied possible outcomes.