Answers.Body: <p>To solve the polygonal obstacle problem using hill climbing, you could creatively explore potential paths by adjusting waypoints slightly, rotating, or translating the entire path to avoid obstacles. By shifting sections of the path or tweaking its direction, you can uncover new solutions that might bring you closer to an optimal route. With every move, aim to keep the path valid and gradually improve its performance, whether through reducing path length or avoiding new obstacles. This incremental approach can help guide you toward a better solution.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-12T13:31:07.163Z
Answers.Text: Could you help me understand your answer a bit more? For instance, suppose I enter the initial path to be [A,B,F,T,G,Y,X]. If I was to alter that path, in any way, it will most likely invalidate it.
Answers.UserDisplayName: HMPtwo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-14T10:52:05.000Z
Answers.Text: Could you tell me how you would adjust the path to generate valid neighbours?
Answers.UserDisplayName: HMPtwo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-11T12:23:09.700Z
Answers.LastActivityDate: 2024-11-11T12:23:09.700Z
Answers.UserDisplayName: Trushaba B. Jadeja
Body: <p>I will first explain the problem. We start at an initial node S in the 2D plane and our goal is to reach a goal node G. In order to get to the end node we have to get past polygonal obstacles. Here is an image:  <a href="https://i.sstatic.net/wK1AHLY8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wK1AHLY8.png" alt="polygonal path" /></a></p>
  <p>A solution path is a list of vertices starting at S and ending at G that form a path from S to G.</p>
  <p>We can start by giving the hill-climbing algorithm a user-generated path through the polygonal obstacles. What I am struggling to understand is how we generate neighbours? Because a neighbour also has to be a path that starts at S and ends at G. We have to perturb the path in some way to generate a neighbour.</p>
  <p>Any ideas? I have googled this but nothing useful comes up.</p>
  <p>An answer has been given, but I would like to understand how to implement such a method. In my head it is going to be really difficult to change the path in such a way that it remains valid.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-09T22:00:56.837Z
Comments.Text: How can you argue your hill climbing local search heuristic algo is the right approach here since it's not clear this is a convex problem? Why not try A*/Dijkstra/RL?
Comments.UserDisplayName: cinch
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-10T18:10:30.377Z
Comments.Text: I have already solved the problem using A* and Dijkstra. IT is part of an exercise to solve it using hill climbing. What is RL?
Comments.UserDisplayName: HMPtwo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-10T22:33:34.567Z
Comments.Text: Hill climbing is a local search algo which applies in convex case only without local optima, however, based on the many obstacles of your case, it may very well likely stuck in a local optimum even your evaluation function successfully filter out all intersected neighbor paths, curved or straight, after rasterization, say.
Comments.UserDisplayName: cinch
Tags: <hill-climbing>
Title: Using hill climbing to solve the polygonal obstacle problem
UserDisplayName: HMPtwo
ThreadText: # Using hill climbing to solve the polygonal obstacle problem
  
  (Asked by: username_0 on 2024-11-04)
  
  I will first explain the problem. We start at an initial node S in the 2D plane and our goal is to reach a goal node G. In order to get to the end node we have to get past polygonal obstacles. Here is an image: [![polygonal path](https://i.sstatic.net/wK1AHLY8.png)](https://i.sstatic.net/wK1AHLY8.png)
  
  A solution path is a list of vertices starting at S and ending at G that form a path from S to G.
  
  We can start by giving the hill-climbing algorithm a user-generated path through the polygonal obstacles. What I am struggling to understand is how we generate neighbours? Because a neighbour also has to be a path that starts at S and ends at G. We have to perturb the path in some way to generate a neighbour.
  
  Any ideas? I have googled this but nothing useful comes up.
  
  An answer has been given, but I would like to understand how to implement such a method. In my head it is going to be really difficult to change the path in such a way that it remains valid.
  
  **Tags:** hill-climbing
  
  > **Comments:**
  > **username_1**: How can you argue your hill climbing local search heuristic algo is the right approach here since it's not clear this is a convex problem? Why not try A*/Dijkstra/RL?  
  > **username_0**: I have already solved the problem using A* and Dijkstra. IT is part of an exercise to solve it using hill climbing. What is RL?  
  > **username_1**: Hill climbing is a local search algo which applies in convex case only without local optima, however, based on the many obstacles of your case, it may very well likely stuck in a local optimum even your evaluation function successfully filter out all intersected neighbor paths, curved or straight, after rasterization, say.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-11-11. Score: 0
  
  To solve the polygonal obstacle problem using hill climbing, you could creatively explore potential paths by adjusting waypoints slightly, rotating, or translating the entire path to avoid obstacles. By shifting sections of the path or tweaking its direction, you can uncover new solutions that might bring you closer to an optimal route. With every move, aim to keep the path valid and gradually improve its performance, whether through reducing path length or avoiding new obstacles. This incremental approach can help guide you toward a better solution.
  
  > **Comments:**
  > **username_0**: Could you help me understand your answer a bit more? For instance, suppose I enter the initial path to be [A,B,F,T,G,Y,X]. If I was to alter that path, in any way, it will most likely invalidate it.  
  > **username_0**: Could you tell me how you would adjust the path to generate valid neighbours?  
  
  ---
  
  