Lab 3 (Part II): Search Algorithms (Curve Fitting Onramp)

PART II - Uniform-Cost Search (UCS) Algorithm

Objective

To create Python script to execute Uniform Cost Search (UCS) algorithm.

Problem to be solved

We will revisit Nick’s route-finding problem in Romania, starting in Arad to reach Bucharest, and implement uniform-cost search to solve the problem.

Continue work from Part I

Uniform Cost Search (UCS) changes the sorting of the frontier by ordering it with its path cost up to the leaf node and expanding the leaf node with the lowest cost.

1. Upcate the code from Part I to be able to sort the frontier following the path cost up to the leaf node.

2. If a latter-found node has the same state as a previous node and the previous node has been expanded, what should be done?

3. What happens when a latter-found node has the same state as a previous node and have a shorter path cost? How do we implement this in our code?

4. Note also, the goal test should be applied during expansion, not generation.

Execute the program and investigate if the program is working correctly.

---

1. The updated Node Class definition

class Node:
  def __init__(self, state=None, parent=None, cost=0):
    self.state = state
    self.parent = parent
    self.children = []
    self.cost = cost    

  def addChildren(self, children):
    self.children.extend(children)

Discussion: take a note of how the cost is now part of the node definition

2. The updated ExpandAndReturnChildren function

def expandAndReturnChildren(state_space, node):
  children = []
  for [m,n,c] in state_space:
    # if a match is found, add the other as a child & accumulate costs
    if m == node.state:
      children.append(Node(n, node.state, node.cost+c)) 
    elif n == node.state:
      children.append(Node(m, node.state, node.cost+c))
  return children

Discussion: What is the difference between cost and c ?

3. The AppendAndSort (Frontier) function (new)

def appendAndSort(frontier, node):
  duplicated = False
  removed = False
  for i, f in enumerate(frontier):
    if f.state == node.state:
      duplicated = True
      if f.cost > node.cost:
        del frontier[i]
        removed = True
        break    
  if (not duplicated) or removed:
    insert_index = len(frontier)
    for i, f in enumerate(frontier):
      if f.cost > node.cost:
        insert_index = i
        break
    frontier.insert(insert_index, node)
  return frontier

Discussion: similarly to how we did it in BFS, run through the loops and evaluate this function

4. The UCS Algorithm (incomplete)

# The UCS Algorithm 
def ucs(state_space, initial_state, goal_state):

  # Step 1 - Initiate variables & conditions

  # Step 2 - Search Loops 
  while not found_goal:

    # 2.1 goal test 

    # 2.2 Manage the Frontier & Explored Lists 

    # 2.3 Progress Update


  # Step 3 Solution & Cost   

  return solution, path_cost

Discussion: Complete & run this based on the work we did in BFS & definitions above

5. All together now

Your complete Program show now look like this

class Node:
  ...

def expandAndReturnChildren(...):
  ...

def appendAndSort(...):
  ...

def ucs(...):
  ...

if __name__ == '__main__':
  state_space = [
  ...
  ]

  initial_state = 'Arad'
  goal_state = 'Bucharest'

  print('Solution: ' + str(ucs(state_space, initial_state, goal_state)))

---

Bonus Opportunity: Curve Fitting Onramp Certificate

To complement your learning in this lab and explore data modeling techniques, you are encouraged to complete the Curve Fitting Onramp course by MathWorks.

• Estimated Time: ~2 hours
• Platform: Online (browser-based)
• Outcome: Digital Certificate of Completion from MathWorks

Action Steps: 1. Access the course here: Curve Fitting Onramp – MathWorks Academy 2. Go through all the lessons and complete the interactive activities. 3. Download your Certificate of Completion. 4. Upload your certificate along with your Lab X submission on LMS.

Bonus Recognition: - Students who complete and submit this certificate will be acknowledged later in the semester. - This is optional and will not impact your Lab X grade.

---