Add support for computing an early abort for Astar based on cost #565

Activity

1. samueltardieu commented on Jul 27, 2024

   

   samueltardieu

   on Jul 27, 2024

   Member

   More actions

   I would think that you would want to limit the number of steps rather than the cost. You can already do that by incrementing a variable in the success function and returning true if it reaches a given value. You would then have to check the return of astar to see if this is a true, or you could also set an additional boolean in the success function to reflect the fact that you have aborted the search.

   Another way, as you suggest, would be to pass a state to the success function (with the cost, number of steps, etc.), and let it return either Success, Failure, or Abort. It you have a signature to suggest, that might be useful for what you want to do.
2. RaminKav commented on Jul 27, 2024

   

   RaminKav

   on Jul 27, 2024

   Author

   More actions

   Ah yes, steps would be ideal, good point. Using a counter in the success function worked great, I had tried incrementing in the successors and heuristic callbacks and was running into BC issues, didnt realize i could increment inside the success function too, that makes a lot more sense!

   I think as i thought about it more, i might still need to do some extra work before calling astar to detect if the target is in a separate "island" using a flood-fill algorithem.

   For the signature, did you mean something like FS: FnMut(&N, usize, &C) -> bool, for success ? This would pass in the index (for number of steps) and cost.
3. samueltardieu commented on Jul 29, 2024

   

   samueltardieu

   on Jul 29, 2024

   Last edited by samueltardieu

   Member

   More actions

   Either that, or something like

   pub struct AstarProgress<'C> {
     number_of_steps: usize,
     current_cost: C,
     current_depth: usize,  // Depth since the start of the A* search
   }
   
   pub enum AstarResult {
     Success,
     Continue,
     Abort,
   }

   with FS: FnMut(&N, &AstarProgress) -> AstarResult.

   It would be easy to maintain the current API while offering a new one with the full capabilities without duplicating the code. It would also make sense to replicate this scheme for other exploration methods. Also, AstarProgress could be easily extended in the future if needed.
4. samueltardieu

   added

   feature_request

   on Aug 31, 2024
5. saberoueslati commented on Sep 17, 2026

   

   saberoueslati

   on Sep 17, 2026

   More actions

   I will try working on this