• Home
• Blog
• Artificial Intelligence Question

# Artificial Intelligence Question

1. Given an environment with polygonal obstacles, a maximum budget C (i.e., path length), and {S, G}, your goal would be to find the shortest path between S and G such that the path cost is less than C using Algorithm 1 in [Stern 2014]. [50 points]
• You should test your program with the environment shown in Fig. 3.31 first.
• C should be input the program — constraint in the problem.
• Show the path found. If there is no such path, inform the user.
• Next, create a new environment that is drastically different from the environment in 3.31. This environment should have at least 5 polygonal obstacles in it.
• Test your program in this environment like the previous one.
• Show the output for each input C.
• Please list in your submission PDF which C values worked and which did not work — not specific numbers, but ranges, for example.
• You will lose points without this information.
• Note that your program should show the user the final path found by your algorithm for a specific input value of C in both environments.
• You can use your Assignment 1 code as a base for this assignment.
• Create the SWITCH-CASE that will switch between the environments.
• Create a while loop to take inputs [environment number and C value] from the user until he/she decides to stop.
• You will lose points without this structure.
• Attach screenshots of your program’s outputs with various values of C (should be properly labeled).
• Reminder: there are two main differences between A* and this algorithm.
• Instead of the f-value, it uses their own-defined (u-value) — can be found before the algorithm.
• There is a constraint added in Algo 1 that decides which nodes should not be expanded as it has a higher cost than budget C.

[Stern 2014] Stern, R., Felner, A., van den Berg, J., Puzis, R., Shah, R., & Goldberg, K. (2014). Potential-based bounded-cost search and Anytime Non-Parametric A*. Artificial Intelligence, 214, 1-25.