Thread:Talk:GoTo/Optimum Goto Driver/reply

From RoboWiki
(Difference between revisions)
Jump to: navigation, search
m (Reply to Optimum Goto Driver)
 
m (words)
 
Line 1: Line 1:
 
A few weeks ago, I began working towards an algorithm for optimal goto movement like you mention, using a calculus-based approach. My first idea was to find the heading/velocity combination that would minimize the distance between the robot and its target destination on the next turn - a simple optimization problem. This doesn't work, however, due to the fact that in [[Game Physics#Robocode processing loop|Robocode's processing loop]], heading changes before velocity. Because of this, the impact that velocity has on the max turn rate on the ''next'' turn, then, must be taken into account. I am currently revising my formulas to do so. (The new goal is still to minimize the distance between the robot and the target destination, but effectively looking forward 2 turns in the future, instead of just one.)
 
A few weeks ago, I began working towards an algorithm for optimal goto movement like you mention, using a calculus-based approach. My first idea was to find the heading/velocity combination that would minimize the distance between the robot and its target destination on the next turn - a simple optimization problem. This doesn't work, however, due to the fact that in [[Game Physics#Robocode processing loop|Robocode's processing loop]], heading changes before velocity. Because of this, the impact that velocity has on the max turn rate on the ''next'' turn, then, must be taken into account. I am currently revising my formulas to do so. (The new goal is still to minimize the distance between the robot and the target destination, but effectively looking forward 2 turns in the future, instead of just one.)
  
Note #1: I am not certain that this method actually minimizes travel time, but "minimizing distance to destination" seems like it should do so implicitly, as long as all factors affecting possible movement options are accounted for in whatever formula is used to do so. The other way to do this that I see would be to devise some algorithm to effectively mathematically generate possible paths to a point, and then minimize travel time. That seems quite... nontrivial, though.
+
Note #1: I am not certain that this method actually minimizes travel time, but "minimizing distance to destination" seems like it should do so implicitly, as long as all factors affecting possible movement options are accounted for in whatever formula is used. The other way to do this that I see would be to devise some algorithm to effectively mathematically generate possible paths to a point, and then minimize travel time. That seems quite... nontrivial, though.
  
Note #2: My limited testing with the method mentioned above matches your findings above. Max velocity seems to optimal for all but the tightest turns (as one would expect). One thing I have not taken into account in my calculations is reversing. Thusfar, for simplicity's sake, I have effectively considered destination points in only one quadrant and velocities between 0 and 8. As I see it, limiting to one quadrant is a nonissue, as the algorithm should not be affected by π/2 rotations. Negative starting velocities, however, will indeed impact the correct solution, so that is definitely something I plan to look into in the future.
+
Note #2: My limited testing with the method mentioned above matches your findings above. Max velocity seems to optimal for all but the tightest turns (as one would expect). One thing I have not taken into account in my calculations is reversing. Thus far, for simplicity's sake, I have effectively considered destination points in only one quadrant and velocities between 0 and 8. As I see it, limiting to one quadrant is a nonissue, as the algorithm should not be affected by π/2 rotations. Negative starting velocities, however, will indeed impact the correct solution, so that is definitely something I plan to look into in the future.
  
 
Overall, I believe that a calculus-based approach to path generation shows much promise, and could potentially offer a truly optimal solution if done well enough. I rambled a bit here, so feel free to @ me something I have written is unclear. I'll update if/when I make progress with the approach I am currently trying.
 
Overall, I believe that a calculus-based approach to path generation shows much promise, and could potentially offer a truly optimal solution if done well enough. I rambled a bit here, so feel free to @ me something I have written is unclear. I'll update if/when I make progress with the approach I am currently trying.

Latest revision as of 23:11, 16 August 2019

A few weeks ago, I began working towards an algorithm for optimal goto movement like you mention, using a calculus-based approach. My first idea was to find the heading/velocity combination that would minimize the distance between the robot and its target destination on the next turn - a simple optimization problem. This doesn't work, however, due to the fact that in Robocode's processing loop, heading changes before velocity. Because of this, the impact that velocity has on the max turn rate on the next turn, then, must be taken into account. I am currently revising my formulas to do so. (The new goal is still to minimize the distance between the robot and the target destination, but effectively looking forward 2 turns in the future, instead of just one.)

Note #1: I am not certain that this method actually minimizes travel time, but "minimizing distance to destination" seems like it should do so implicitly, as long as all factors affecting possible movement options are accounted for in whatever formula is used. The other way to do this that I see would be to devise some algorithm to effectively mathematically generate possible paths to a point, and then minimize travel time. That seems quite... nontrivial, though.

Note #2: My limited testing with the method mentioned above matches your findings above. Max velocity seems to optimal for all but the tightest turns (as one would expect). One thing I have not taken into account in my calculations is reversing. Thus far, for simplicity's sake, I have effectively considered destination points in only one quadrant and velocities between 0 and 8. As I see it, limiting to one quadrant is a nonissue, as the algorithm should not be affected by π/2 rotations. Negative starting velocities, however, will indeed impact the correct solution, so that is definitely something I plan to look into in the future.

Overall, I believe that a calculus-based approach to path generation shows much promise, and could potentially offer a truly optimal solution if done well enough. I rambled a bit here, so feel free to @ me something I have written is unclear. I'll update if/when I make progress with the approach I am currently trying.

Personal tools