3 ms·

I like this..I recently used A* to implement laying out connectors between nodes in a graph. I really like the abstraction of a heuristic function. I was able t

I like this..I recently used A* to implement laying out connectors between nodes in a graph. I really like the abstraction of a heuristic function. I was able to add in all sorts of things to make the implementation work the way i want (penalise turns, crossing over lines etc.). This would automatically create "last resort" style solutions and minimise ugliness in the diagram.

eigenvalue 2y ago
Yes, doing it that way sort of goes beyond the standard A* and becomes more of a "build your own custom pathfinder toolbox" where you can insert any additional considerations you have in your specific problem domain. Sort of like how you can add different factors to a loss function in machine learning (like trying to minimize non-zero parameter count for LASSO in addition to minimizing mean squared error).
dietr1ch 2y ago
The heuristic is the wrong place to adjust solutions, just change the costs on the original problem and adjust the heuristic if necessary. I guess that for your intention, using an inconsistent heuristic that over-estimated costs and resulted in sub-optimal solutions was fine because you wanted sub-optimal solutions in your penalty-free problem, but this was better modeled by a modified problem that either penalized or forbid certain solutions in the original problem.
- noufalibrahim 2y ago
  That's a good point. I didn't think of like that. I think the "don't allow" cases might be modelled in the heuristic but my initial graph was just all open.
  - dietr1ch 2y ago
    I'm not sure what you mean by the initial graph being just all open, but I'm still convinced that modelling things only in the heuristic is wrong. Here's why it fails eventually, Hacking only the heuristic side will seem to work as intended on short paths, but as the f-value (g+h) naturally starts being dominated by g as the solutions become longer, you'll see that the hints at what not to do embedded in the heuristic will start to seemingly become neglected by A*
    - noufalibrahim 2y ago
      When I said "all open", I meant that none of the constraints were included in the graph I started with. All paths between the two endpoints are equally valid. I wanted then, to find paths that didn't overlap with other connectors, that didn't go too close to other objects and didn't turn too much. These, I modeled by adjusting the heuristics so that such paths are penalised. I see your point. The penalties right now are "big" but only when compared to the values of g at the beginning. As it moves forward, even the big penalties will be swamped by the g and hence, the heuristics will be ignored. I'm not sure about how else to model this though.

eigenvalue 2y ago

Yes, doing it that way sort of goes beyond the standard A* and becomes more of a "build your own custom pathfinder toolbox" where you can insert any additional considerations you have in your specific problem domain. Sort of like how you can add different factors to a loss function in machine learning (like trying to minimize non-zero parameter count for LASSO in addition to minimizing mean squared error).

dietr1ch 2y ago

The heuristic is the wrong place to adjust solutions, just change the costs on the original problem and adjust the heuristic if necessary. I guess that for your intention, using an inconsistent heuristic that over-estimated costs and resulted in sub-optimal solutions was fine because you wanted sub-optimal solutions in your penalty-free problem, but this was better modeled by a modified problem that either penalized or forbid certain solutions in the original problem.

noufalibrahim 2y ago
That's a good point. I didn't think of like that. I think the "don't allow" cases might be modelled in the heuristic but my initial graph was just all open.
- dietr1ch 2y ago
  I'm not sure what you mean by the initial graph being just all open, but I'm still convinced that modelling things only in the heuristic is wrong. Here's why it fails eventually, Hacking only the heuristic side will seem to work as intended on short paths, but as the f-value (g+h) naturally starts being dominated by g as the solutions become longer, you'll see that the hints at what not to do embedded in the heuristic will start to seemingly become neglected by A*
  - noufalibrahim 2y ago
    When I said "all open", I meant that none of the constraints were included in the graph I started with. All paths between the two endpoints are equally valid. I wanted then, to find paths that didn't overlap with other connectors, that didn't go too close to other objects and didn't turn too much. These, I modeled by adjusting the heuristics so that such paths are penalised. I see your point. The penalties right now are "big" but only when compared to the values of g at the beginning. As it moves forward, even the big penalties will be swamped by the g and hence, the heuristics will be ignored. I'm not sure about how else to model this though.