Consider the problem of finding the shortest path (e.g., using A* algorithm) between two points on a plane that has convex polygonal obstacles as shown in Figure 3.31. This is an idealization of the problem that a robot has to solve to navigate in a crowded environment.

• Define the necessary functions to implement the search problem, including an ACTIONS function that takes a vertex as input and returns a set of vectors, each of which maps the current vertex to one of the vertices that can be reached in a straight line. (Do not forget the neighbors on the same polygon.)
  • Use the straight-line distance for the heuristic function.
• Write a program (language no bar) to solve the shortest pathfinding problem for such an environment.
  • Input: an environment like the one shown in Fig. 3.31 in your textbook, a start, and a goal location.
  • Output: the shortest path that the robot has to follow to reach from the start to the goal (Shown visually on screen).

    Polygon 1: ((220, 616), (220, 666), (251, 670), (272, 647))

    Polygon 2: ((341, 655), (359, 667), (374, 651), (366, 577))

    Polygon 3: ((311, 530), (311, 559), (339, 578), (361, 560), (361, 528), (336, 516))

    Polygon 4: ((105, 628), (151, 670), (180, 629), (156, 577), (113, 587))

    Polygon 5: ((118, 517), (245, 517), (245, 577), (118, 557))

    Polygon 6: ((280, 583), (333, 583), (333, 665), (280, 665))

    Polygon 7: ((252, 594), (290, 562), (264, 538))

    Polygon 8: ((198, 635), (217, 574), (182, 574))

    Start: (120, 650) End: (380, 560)

Please write a code in Java using A* algorithm and please put the full code with the GUI. Thanks

G S. Figure 3.31 A scene with polygonal obstacles. S and G are the start and goal states