Skip to content

JA3. Learning Journal 3

Statement

  • Part 1:
    • You are an employee of a tour and travel company. One of the clients is planning for a world tour and seeks your help for determining the best route for his travel.
    • Create a report to give to your client and include answers to both questions A and B.
    • A. Create a list of various factors you will use for selecting the most efficient searching techniques for determining the best path for your client. Be sure to justify your selection by providing a detailed explanation.
    • B. Think about a situation where another technique different from the one chosen by you in part A above, works more efficiently. Discuss situation and the proposed search technique by covering the characteristics that make this technique it more suitable for the situation.
  • Part 2:
    • Using A* algorithm, find the most cost-effective path to reach from start state “A” to final state “J” for the graph below. Be sure to provide calculations for all nodes traversed in the path.
    • The numbers written on edges represent the distance between the nodes.
    • The numbers written on nodes represent the heuristic value.

Answer

Part 1

A. Create a list of various factors you will use for selecting the most efficient searching techniques for determining the best path for your client.

The problem of traveling the world can be modeled as a graph problem where the nodes represent the cities and the edges represent possible routes between them; hence the problem becomes a traversing the nodes of a graph assuming the client wants to visit all the cities. A simple way to solve the problem is to use a greedy best-first search relying on a breadth-first search (BFS) strategy and a heuristic function to determine the next city to visit.

In simple terms, assuming the list of cities are finite and known beforehand, the solution checks all cities connected to the current city and apply the heuristic function to determine the next city, and then from there, the same process is repeated until all cities are visited. We may need to maintain a list of visited cities to avoid visiting the same city twice.

The factors that affect the effectiveness of the search technique include technical side that involves graph complexity, number of cities, memory and other resource limitations; and problem-related side that involves the client’s preferences which are then translated into the heuristic function. Here are some factors to consider:

  • Budget: The budget set for staying in each city.
  • Travel budget: The budget allocated for the travel.
  • Stay duration: The number of days the client wants to stay in each city.
  • Travel duration: The time it takes to travel between cities.
  • Distance: The distance between cities.
  • Preferred activities: The client’s preferences for what to do in each city.
  • Preferred mode of transport: If a client prefers ground over air travel.

The above factors are example, and their usage are subject to the availability of information; for example, I can not use travel duration if I do not have access to the airport’s schedule. The heuristic function can be a weighted sum of the above factors, and the weights can be adjusted based on the client’s preferences to return a positive integer value to rank the cities in the next level, and choose the city with the highest value.

B. Think about a situation where another technique different from the one chosen by you in part A above, works more efficiently.

One situation where another technique different from the greedy best-first search works more efficiently is when the client has more limited resources (e.g., budget or time) and want overall more optimized path; that is, looking for the single next step in a greedy manner does not suffice. In this case, an A* search algorithm can be more suitable.

The A* search algorithm is an informed search algorithm that uses the same heuristic function to estimate the cost of the cheapest path from the current node to the goal node; but, instead of looking 1 city ahead, it looks for more, say 5. From the current city, we do a breadth-first search to gather all cities connected, but then for each city, we do a depth-first search on the next 5 cities passing these info to the heuristic function to determine the best path.

The A* search is still a greedy algorithm, but it is more informed as it looks ahead for more than just the next city. Its limit of 5 also prevents going deep into the graph and hence, it is more efficient in terms of memory and time. The planner takes more cities into consideration and hence, it has more information to make a better decision that is not very short-sighted.

Part 2

To solve this problem using the A* algorithm, we will use a breadth-first search strategy followed by a depth-first search of size 1 to determine the best path. In other words, for each node we will look at all connected nodes and compute the total cost of this node and 1 node ahead, and then we choose the node with the lowest cost.

We will start by creating cost table for most of available paths; this serves as a reference for easy computing the cost of each path below.

Path Distance (g) Heuristic (h) f = g + h
AF 3 10 + 6 = 16 19
AFG 3 + 1 = 4 16 + 5 = 21 25
AFH 3 + 7 = 10 16 + 3 = 19 29
AFGI 4 + 0 = 4 21 + 1 = 22 26
AFHI 10 + 2 = 12 19 + 1 = 20 32
AFGIJ 4 + 3 = 7 22 + 0 = 22 29
AFGIE 4 + 5 = 9 22 + 3 = 25 34
AFHIJ 12 + 3 = 15 20 + 0 = 20 35
AB 6 10 + 8 = 18 24
ABD 6 + 2 = 8 18 + 7 = 25 33
ABC 6 + 3 = 9 18 + 5 = 23 32
ABDE 8 + 0 = 8 25 + 3 = 28 36
ABCE 9 + 5 = 14 23 + 3 = 26 40
ABDEJ 8 + 5 = 13 28 + 0 = 28 41
ABCEJ 14 + 5 = 19 26 + 0 = 26 45

Notes:

  • The distance GI is missing form the graph, so it is assumed to be 0.
  • The heuristic value for J is 0.

This is the first step, we are at node A and we have two possible paths: AF and AB; looking for 1 node ahead, each from B,F also connects to (C,D) and (G,H) respectively. The paths within the parentheses are the possible next nodes(for the DFS step).

Step Path Node Frontier Next Node
1 A A B(C,D), F(G,H) F
Suggested Path Total Cost
AB(C) 32
AB(D) 33
AF(G) 25
AF(H) 29

This is the second step, we choose AF as our path so far; so we are at node F and want to decide where to go next:

Step Path Node Frontier Next Node
2 AF F G(I), H(I) G
Suggested Path Total Cost
AFG(I) 26
AFH(I) 32

This is the third step, we choose AFG as our path so far; so we are at node G and want to decide where to go next:

Note: I is the only point connected to G; so we can choose it without further calculations; but we will calculate the cost anyway.

Step Path Node Frontier Next Node
3 AFG G I(J, E) I
Suggested Path Total cost
AFGI(J) 29
AFGI(E) 34

This is the fourth step, we choose AFGI as our path so far; so we are at node I and want to decide where to go next:

Step Path Node Frontier Next Node
4 AFGI I J, E J
Suggested Path Total Cost
AFGIJ 29
AFGIE 34

To conclude, the most cost-effective path to reach from start state “A” to final state “J” is AFGIJ with a total cost of 29.

Name Value
Effective Path A → F → G → I → J
Total Cost 29

References

  • Poole, D. L., & Mackworth, A. K. (2017). Artificial Intelligence: Foundations of computational agents. Cambridge University Press. https://artint.info/2e/html/ArtInt2e.html.Chapter 3 – Searching for Solutions
  • Taipala, D. (2014, September 22). CS4408 Artificial Intelligence unit 3 lecture 1 + 2 [Video]. YouTube.