II: Searching, Planning and Scheduling

Question 1

What is a vital part of artificial intelligence? Why?

Answer 1

Searching, planning and scheduling which are popular algorithms and techniques used in computer science to find solutions to tasks and to plan activities in a given space. All three are necessary for solving problems in the different AI areas, since these are used for searching problems, scheduling tasks and planning actions.

Question 2

Give an example for an area where searching, planning and scheduling can be used:

Answer 2

An agent-based system working on a problem in the environment, such as finding a goal from a given input, moving around either with a plan or without searching for a solution in a problem space where a schedule may affect the agent’s behavior.

Question 3

What are search algorithms?

Answer 3

Search algorithms use strategies to search for solutions within a given data set in a problem domain. These algorithms share a basic structure but vary when it comes to search strategies. These algorithms traverse the paths (formed in either a tree or graph) that lead to the goal in a systematic order.

Question 4

In what way does search algorithms traverse?

Answer 4

They traverse/search in data structures and visit paths in a systematic order. They are formed either as trees or graphs that are structured to ensure that the search will cover the entire space in an unorganized and non-redundant manner.

Question 5

How are trees structured?

Answer 5

Trees are ordered structures with a finite number of nodes, where the initial state is the root note, and the goal state is the desired end nod or the path to the end node. Search algorithms explore the contents by moving in the tree: in other words, between levels in the tree moving between nodes.

Question 6

What are graphs?

Answer 6

Graphs are data structures with nodes or so called vertices but do not have to be ordered not do they have end nodes as solutions. The initial state is used as a starting point ,or starting node, from which the search algorithm starts searching for a solution by moving between the neighboring nodes.

Question 7

What happens with a directed graph compared to a bi-directed graph?

Answer 7

Directed graphs the movement goes between nodes without directions while in bi-directed graphs the directions go both ways between two neighboring nodes.

Question 8

Are search algorithms efficient?

Answer 8

Search algorithms have different levels of efficiency. The performance of search algorithms depends on the content and complexity of the domain, such as the size of data sets with search space and depths. Performance can also be affected by the branching factor (the average number of child nods) and computability in time. The domain can be a simple and small search space, with a small number of solutions.

Question 9

What are uninformed search algorithms?

Answer 9

Uninformed search, or blind search, is an umbrella term for algorithms that search without additional information about the contents. They can traverse a tree but do not have extra info about the states or the search space, which means that they have to force their way through the space using brute-force to find a solution.

Question 10

What are brute-force search algorithms?

Answer 10

These are a type of algorithm of uninformed search algorithms; they are guaranteed to find a solution if done systematically, a solution exists and the space is finite. The search systematically enumerates all possible candidates for the solution and then checks whether each candidate satisfies the problem statement.

Question 11

Are uninformed search algorithms and brute-force search algorithms general?

Answer 11

Yes! Since they do not require knowledge of the content when they enumerate nodes in the three and they are considered general-purpose search algorithms that can be applied to a variety of search problems.

Question 12

What are some well-known uninformed search algorithms?

Answer 12

Dijkstra algorithm (debated?)

Breadth-first search algorithm

Depth-first search

Bidirectional search

Uniform-cost search algorithm

Question 13

What are Dijkstra’s algorithms?

Answer 13

Dijkstra’s algorithm is a graph search algorithm used to find the shortest path from a starting node to all other nodes in a weighted graph. It maintains a priority queue to keep track of the tentative distances from the start node to each node. The algorithm iteratively selects the node with the smallest tentative distance, updates the distances of its neighboring nodes, and marks the current node as visited. This process continues until all nodes have been visited, resulting in the shortest path from the start node to all other nodes being determined based on the accumulated distances.

Question 14

Are Dijkstra’s algorithms uninformed search algorithms?

Answer 14

Technically they can be seen as uninformed search algorithms since they have a universal graph property for positive weights BUT some argue that the graph property is heuristic and thus can be considered informed search algorithms.

Question 15

What are some breadth-first search algorithms? What are the advantages and disadvantages of BFS?

Answer 15

Breadth-first search algorithms (BFS) traverse and search one level of the tree at a time, thus searching in breadth before moving to the next level in the tree. BFS can be used to perform a graph search but are mostly used for tree searches. It ALWAYS provides the shortest path to the solution (tree-wise, not weight-wise). It has a FIFO queue data structure which means that the nodes that have already been visited are stored.

Advantages: If the goal exists, it will find it using the shortest path, from the root to the goal. It cannot skip a level. Good for finding alternative paths through the search space and it can avoid infinite loop problems.

Disadvantages: Since each level of nodes is saved for creating the next one, this algorithm consumes a lot of memory space and takes a long time to solve with deeper-levels.

Question 16

What are depth-first search algorithms? What are the advantages and disadvantages?

Answer 16

A depth-first search (DFS) algorithm is similar to the breadth-first approach but dives into the tree, hence searching in depth. From the root node, a depth-first search algorithm explores one branch first, the “deepest node” in the tree branch, and then moves toward the next deepest node in that branch. It works well for both a tree search and a finite graph search. DFS is implemented using a last-in-first-out (LIFO) which means that the last node is tested first to be able to go in depth.

Advantages: If the branch search space is deep with a long path through the space and the branching factor is high, a DFS can perform better than a breadth-first search algorithm. It requires less memory space than BFS.

Disadvantages: A goal can not be found, it will not terminate and will instead go on an infinite search loop. Since it only looks for ONE solution it can often not be the shortest path.

Question 17

What is bidirectional search? What are the advantages and disadvantages?

Answer 17

Bidirectional search is a search algorithm that starts simultaneously from both the initial state and the goal state, aiming to find the shortest path or solution by exploring the search space in two directions. It involves expanding nodes and searching for matches or intersections between the forward and backward searches.

Advantages: This approach can reduce the search space and improve efficiency compared to traditional unidirectional searches, especially in large and complex search problems.

Disadvantage: If weights are used for the edges, a bidirectional search algorithm may not be feasible, or possible, in terms of searching backward through possible states

Question 18

What is uniform-cost search? What are the advantages and disadvantages?

Answer 18

Uniform-cost search is a search algorithm that explores the search space by considering the cost of reaching each state from the initial state. It prioritizes nodes with lower path costs, gradually expanding the search frontier. It guarantees to find the optimal solution when the cost function is non-negative. The algorithm uses a priority queue to select the node with the lowest cumulative cost at each step. This allows it to systematically explore the search space while considering the cost of each path, making it suitable for problems where finding the lowest-cost solution is crucial.

Advantages: Can solve any general graph for optimal cost. This algorithm will in every state of the path choose the one with the least costs.

Disadvantages: returns the first completed path and does not search further.

Question 19

What are informed search algorithms?

Answer 19

Informed scratch algorithms apply available information about the search space; for example, how to reach the goal node, how far it is to the goal node and the path cost. This information guides the way through the states in the problem space toward the goal. It informs the search about the direction to a goal, thereby exploring the most promising node.

Question 20

What are some well-known informed search algorithms?

Answer 20

Best-first search algorithm

A* search algorithm

Hill-climbing search

Event-driven algorithm

Question 21

What are the best-first search algorithms? What are the advantages and disadvantages?

Answer 21

Best-first search algorithms are graph search algorithms that prioritize exploring nodes based on an evaluation function that estimates their desirability. These algorithms select the most promising node according to the evaluation function and continue the search from there.

Advantages of best-first search algorithms include their efficiency in finding a solution quickly and their ability to handle large search spaces.

The main disadvantage is their tendency to be influenced by the evaluation function, which may lead to suboptimal solutions if the function is not well-designed or if it does not accurately represent the problem domain.

Question 22

What are the A* search algorithms? What are the advantages and disadvantages?

Answer 22

A* search algorithm is a best-first, tree and graph search algorithm that combines a best-first heuristic search with a uniform-cost search. It is the most popular AI search algorithm of all algorithms. It is similar to Djikstra however the big difference between the two is the fact that A* uses a best-first approach and decides which vertex to explore next, where Djikstra all vertices are connected to a node.

Advantage: Complete and optimal

Disadvantage: Complexity problem when branching factor is high. If the lowest cost value does not lead to the goal, A* turns into problems. Speed is highly dependent on the accuracy of the heuristic algorithm.

Question 23

What are hill-climbing search? What are the advantages and disadvantages?

Answer 23

Hill-climbing search is a local search algorithm that starts from an initial solution and iteratively moves to a neighboring solution that improves the objective function. It aims to find the highest point (maximum or minimum) in the solution space. It uses a greedy search approach.

Advantages: hill-climbing includes its simplicity and efficiency in finding local optima.

Disadvantage: stuck at local optima, unable to explore other potentially better solutions. It lacks the ability to backtrack and may not find the global optimum. It is also sensitive to the initial solution and may converge to suboptimal solutions.

Question 24

What are event-driven algorithms? What are the advantages and disadvantages?

Answer 24

An event-driven algorithm is a programming paradigm where the flow of execution is determined by events or messages rather than a sequential order. It involves waiting for events to occur and triggering appropriate actions in response.

Advantages: responsiveness, scalability, and modular design. They are well-suited for handling concurrent and asynchronous tasks.

Disadvantages: complex to design and debug. They may suffer from event handling order issues and event dependencies. Additionally, event-driven programming requires careful management of resources and event queues to ensure efficient execution.

Question 25

What is planning used for?

Answer 25

Planning is to achieve goals by carrying out actions in a certain order. Plans are used for movement and routes for instance, robots and automatic vehicles where strategies are part of the planning.

Question 26

What does simple planning mean?

Answer 26

Simple planning concentrates on problems where most actions leave the environment unchanged. Hence, the actions are about moving in the world without nudging the objects.

Question 27

What does NP stand for?

Answer 27

NP stands for “nondeterministic polynomial time,” referring to the class of decision problems that can be solved in polynomial time by a nondeterministic Turing machine. These problems are efficiently verifiable, meaning that given a potential solution, it can be checked in polynomial time.

Question 28

What is a NP-complete problem and a NP-hard problem?

Answer 28

NP-complete problems are a subset of NP problems that have the property that any other problem in NP can be transformed into them in polynomial time. In other words, if a polynomial time algorithm exists for any NP-complete problem, it can be applied to solve all other NP problems efficiently.

NP-hard problems, on the other hand, are a broader class of problems that are at least as hard as the hardest problems in NP. They may or may not be in NP themselves, but they share the same level of computational complexity as NP-complete problems. This means that if there is a polynomial time algorithm for any NP-hard problem, it would imply the existence of a polynomial time algorithm for all NP problems.

Question 29

What is the traveling salesman problem?

Answer 29

The traveling salesman problem (TSP) is a common optimization problem but can also be used for path planning. TSP is about a salesman who must visit a number of cities, going from an initial state to a goal state, and when moving around, the salesman cannot revisit any of the cities. The salesman must also use the shortest path when traveling, and also find the optimal object in the set of objects (combinatorial optimization). An NP-complete problem.

Question 30

What are NP-hard problems?

Answer 30

NP-hard problems are optimization problems, not decision problems, and just as for NP: complete problems, no efficient algorithm has been found.

Question 31

What is a means-end analysis?

Answer 31

A means-ends analysis starts with a determined goal. Actions are then chosen to reduce some differences between the current state and the goal state. The operation on the current state will produce a new state. An example of a means-end analysis is STRIPS (Stanford Research Institute Problem Solver)

Question 32

How does STRIPS work?

Answer 32

STRIPS is an automated planning computer system. STRIPS carries out actions in a limited space using a means-end computer system. STRIPS carry out actions in a limited space using means-ends analysis which simulates a robot moving blocks. STRIPS program models the problem using an initial state, a set of goal states and a set of actions.

Question 33

What is constraint programming? What are the weaknesses and strengths?

Answer 33

Constraint programming is a computational approach that focuses on modeling and solving problems by representing constraints and relationships between variables. It involves defining a set of variables and constraints that restrict the possible values the variables can take. By systematically exploring the space of potential solutions and using specialized algorithms, constraint programming aims to find feasible assignments that satisfy all the constraints. It is particularly useful for solving optimization problems, scheduling tasks, and handling combinatorial challenges.

Advantages of constraint programming lie in its ability to handle complex constraints, express problem structures naturally, and provide flexibility for specifying problem domains.

Disadvantages is that it may face challenges with scalability for large problems or in cases where the constraints are difficult to express concisely.