How to make Beam Stack Search optimal and complete

Question

I was reading the paper Beam-Stack Search: Integrating Backtracking with Beam Search by Rong Zhou and Eric A. Hansen and I was attempting to implement it in Java (see PathFinding.java repository in GitHub, the page README gives instruction on running the app). My code is as follows:

package io.github.coderodde.pathfinding.finders;
import static io.github.coderodde.pathfinding.finders.Finder.searchSleep;
import io.github.coderodde.pathfinding.heuristics.HeuristicFunction;
import io.github.coderodde.pathfinding.logic.GridCellNeighbourIterable;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.logic.SearchState;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
/**
 *
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Sep 15, 2025)
 * @since 1.0.0 (Sep 15, 2025)
 */
public final class BeamStackSearchFinder implements Finder {
 @Override
 public List<Cell> findPath(GridModel model, 
 GridCellNeighbourIterable neighbourIterable, 
 PathfindingSettings pathfindingSettings, 
 SearchState searchState, 
 SearchStatistics searchStatistics) {
 
 Deque<BeamStackEntry> beamStack = new ArrayDeque<>();
 beamStack.push(new BeamStackEntry(0.0, Double.POSITIVE_INFINITY));
 
 List<Cell> optimalPath = null;
 DoubleHolder U = new DoubleHolder();
 U.value = Double.POSITIVE_INFINITY;
 
 while (!beamStack.isEmpty()) {
 List<Cell> path;
 System.out.println("hello");
 
 try {
 path = search(model, 
 U,
 beamStack,
 neighbourIterable,
 pathfindingSettings,
 searchState,
 searchStatistics);
 
 } catch (HaltRequestedException ex) {
 return List.of();
 }
 
 if (searchState.haltRequested()) {
 return List.of();
 }
 
 while (searchState.pauseRequested()) {
 searchSleep(pathfindingSettings);
 System.out.println("yes 1");
 if (searchState.haltRequested()) {
 return List.of();
 }
 }
 
 if (path != null) {
 optimalPath = path;
 U.value = getPathCost(path, pathfindingSettings);
 }
 
 while (!beamStack.isEmpty() && beamStack.peek().fmax >= U.value) {
 beamStack.pop();
 } 
 
 if (beamStack.isEmpty()) {
 return optimalPath == null ? List.of() : optimalPath;
 }
 
 BeamStackEntry top = beamStack.peek();
 top.fmin = top.fmax;
 top.fmax = U.value;
 }
 
 throw new IllegalStateException("Should not get here ever");
 }
 
 private static double 
 getPathCost(List<Cell> path,
 PathfindingSettings pathsPathfindingSettings) {
 
 double cost = 0.0;
 
 for (int i = 0; i < path.size() - 1; ++i) {
 Cell c1 = path.get(i);
 Cell c2 = path.get(i + 1);
 cost += pathsPathfindingSettings.getWeight(c1, c2);
 }
 
 return cost;
 }
 
 private static List<Cell> search(GridModel model, 
 DoubleHolder U,
 Deque<BeamStackEntry> beamStack,
 GridCellNeighbourIterable iterable,
 PathfindingSettings pathfindingSettings,
 SearchState searchState,
 SearchStatistics searchStatistics) {
 
 Map<Integer, PriorityQueue<HeapNode>> open = new HashMap<>();
 Map<Integer, Set<Cell>> closed = new HashMap<>();
 Map<Cell, Double> g = new HashMap<>();
 Map<Cell, Cell> p = new HashMap<>();
 
 HeuristicFunction h = pathfindingSettings.getHeuristicFunction();
 Cell source = model.getSourceGridCell();
 Cell target = model.getTargetGridCell();
 
 Cell bestGoal = null;
 int layerIndex = 0;
 
 open.put(0, new PriorityQueue<>());
 open.put(1, new PriorityQueue<>());
 open.get(0).add(new HeapNode(source, 0.0));
 
 closed.put(0, new HashSet<>());
 g.put(source, 0.0);
 p.put(source, null);
 
 searchStatistics.incrementOpened();
 
 while (!open.get(layerIndex).isEmpty() ||
 !open.get(layerIndex + 1).isEmpty()) {
 
 while (!open.get(layerIndex).isEmpty()) {
 
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 
 while (searchState.pauseRequested()) {
 searchSleep(pathfindingSettings);
 System.out.println("yes 2");
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 }
 
 Cell cell = open.get(layerIndex).remove().cell;
 closed.get(layerIndex).add(cell);
 searchStatistics.decrementOpened();
 searchStatistics.incrementVisited();
 
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.VISITED);
 }
 
 if (cell.equals(target)) {
 U.value = g.get(cell);
 bestGoal = cell;
 }
 
 iterable.setStartingCell(cell);
 BeamStackEntry bse = beamStack.peek();
 
 for (Cell child : iterable) {
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 // TODO: Find out why?
 searchState.resetState();
 
 while (searchState.pauseRequested()) {
 System.out.println("yes 3");
 searchSleep(pathfindingSettings);
 
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 } 
 
 double tentativeGscore = g.get(cell) 
 + pathfindingSettings
 .getWeight(cell, 
 child);
 
 if (tentativeGscore < g.getOrDefault(
 child, 
 Double.POSITIVE_INFINITY)) {
 
 double f = tentativeGscore + h.estimate(child, target);
 
 searchSleep(pathfindingSettings);
 
 if (bse.fmin <= f && f < bse.fmax) {
 Queue<HeapNode> nextOpen = open.get(layerIndex + 1);
 
 // Add for the first time or improve the g-cost:
 nextOpen.removeIf(
 heapNode -> heapNode.cell.equals(child));
 
 nextOpen.add(new HeapNode(child, f));
 
 g.put(child, tentativeGscore);
 p.put(child, cell);
 searchStatistics.incrementOpened();
 
 if (!child.getCellType().equals(CellType.SOURCE) &&
 !child.getCellType().equals(CellType.TARGET)) {
 model.setCellType(child, CellType.OPENED);
 }
 }
 }
 }
 
 PriorityQueue<HeapNode> nextOpen = open.get(layerIndex + 1);
 
 if (nextOpen.size() > pathfindingSettings.getBeamWidth()) {
 pruneLayer(model,
 nextOpen,
 pathfindingSettings,
 searchStatistics);
 }
 }
 
 layerIndex++;
 open.put(layerIndex + 1, new PriorityQueue<>());
 closed.put(layerIndex, new HashSet<>());
 beamStack.push(new BeamStackEntry(0, U.value));
 }
 
 for (PriorityQueue<HeapNode> queue : open.values()) {
 for (HeapNode heapNode : queue) {
 Cell cell = heapNode.cell;
 
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.FREE);
 }
 }
 }
 
 for (Set<Cell> closedSet : closed.values()) {
 for (Cell cell : closedSet) {
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.FREE);
 }
 }
 }
 
 if (bestGoal != null) {
 List<Cell> path = new ArrayList<>();
 
 for (Cell cell = bestGoal; 
 cell != null; 
 cell = p.get(cell)) {
 
 path.add(cell);
 }
 
 Collections.reverse(path);
 return path;
 }
 
 return null;
 }
 
 private static void pruneLayer(GridModel model,
 PriorityQueue<HeapNode> open,
 PathfindingSettings pathfindingSettings,
 SearchStatistics searchStatistics) {
 
 List<HeapNode> keepList = new ArrayList<>(open);
 
 for (HeapNode heapNode : keepList) {
 Cell cell = heapNode.cell;
 
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.FREE);
 }
 }
 
 keepList.sort((a, b) -> Double.compare(a.f, b.f));
 keepList = keepList.subList(0, pathfindingSettings.getBeamWidth());
 
 for (HeapNode heapNode : keepList) {
 Cell cell = heapNode.cell;
 
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.OPENED);
 }
 }
 
 List<HeapNode> pruneList = new ArrayList<>();
 double fmin = Double.POSITIVE_INFINITY;
 
 for (HeapNode heapNode : open) {
 if (!keepList.contains(heapNode)) {
 pruneList.add(heapNode);
 fmin = Math.min(fmin, heapNode.f);
 }
 }
 
 for (HeapNode heapNode : pruneList) {
 open.remove(heapNode);
 Cell cell = heapNode.cell;
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.VISITED);
 }
 }
 }
 
 private static final class BeamStackEntry {
 double fmin;
 double fmax;
 
 BeamStackEntry(double fmin, double fmax) {
 this.fmin = fmin;
 this.fmax = fmax;
 }
 }
 
 private static final class DoubleHolder {
 double value;
 }
}

Reproducing bugs

Note that you will have tweak a bit the settings pane: Settings pane of PathFinding.java app.

My current implementation seems to be very sensitive to the beam width: if too small, it either returns a suboptimal path or terminates with no path at all.

Below, the green cell is the source cell, the red one is the target cell, the white cells are the unoccupied cells, the black cells are the walls, the light green cells are the cells in the open list, and the dark gray are the visited cells.

No path at all bug:

I get this one on beam width of 1: No path bug illustration. Above, the green cell is the source cell, and the red cell is the target cell.

What comes to suboptimality, with beam width of 4, I get: Suboptimality bug illustration.

Desired behaviour

The optimal path might look like: Optimal path illustration. The above happens only starting with the beam width of 8.

Some failing unit tests:

package io.github.coderodde.pathfinding.finders;
import io.github.coderodde.pathfinding.heuristics.OctileHeuristicFunction;
import io.github.coderodde.pathfinding.logic.GridCellNeighbourIterable;
import io.github.coderodde.pathfinding.logic.GridNodeExpander;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.logic.SearchState;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;
public class BeamStackSearchFinderTest {
 
 private final PathfindingSettings ps = new PathfindingSettings();
 private final SearchState searchState = new SearchState();
 private final SearchStatistics searchStatistics =
 new SearchStatistics(null, 
 null,
 null,
 null);
 
 public BeamStackSearchFinderTest() {
 ps.setDontCrossCorners(false);
 ps.setAllowDiagonals(true);
 ps.setFinder(new BeamStackSearchFinder());
 ps.setHeuristicFunction(new OctileHeuristicFunction());
 ps.setFrequency(1000);
 }
 
 @Test
 public void hasSolutionPath() {
 System.out.println("hasSolutionPath()");
 
 GridModel model = new GridModel(20, 5);
 model.moveTarget(17, 2);
 model.moveSource(15, 2);
 model.setCellType(16, 2, CellType.WALL);
 ps.setBeamWidth(1);
 
 GridNodeExpander expander = new GridNodeExpander(model, ps);
 
 GridCellNeighbourIterable iterable =
 new GridCellNeighbourIterable(model, 
 expander,
 ps);
 
 List<Cell> pathBreadthFirstSearch = 
 new BFSFinder()
 .findPath(model, 
 iterable, 
 ps,
 searchState, 
 searchStatistics);
 
 List<Cell> pathBeamStackSearch = 
 new BeamStackSearchFinder()
 .findPath(model, 
 iterable, 
 ps,
 searchState, 
 searchStatistics);
 
 System.out.println("BSS: " + pathBeamStackSearch.size());
 System.out.println("BFS: " + pathBreadthFirstSearch.size());
 
 assertEquals(pathBreadthFirstSearch.size(),
 pathBeamStackSearch.size());
 }
 
 @Test
 public void debugNoPath() {
 System.out.println("debugNoPath()");
 
 GridModel model = new GridModel(53, 33);
 model.moveTarget(6, 4);
 model.moveSource(3, 4);
 model.setCellType(4, 2, CellType.WALL);
 model.setCellType(4, 3, CellType.WALL);
 model.setCellType(5, 3, CellType.WALL);
 model.setCellType(5, 4, CellType.WALL);
 model.setCellType(5, 5, CellType.WALL);
 
 ps.setBeamWidth(1);
 
 GridNodeExpander expander = new GridNodeExpander(model, ps);
 
 GridCellNeighbourIterable iterable =
 new GridCellNeighbourIterable(model, 
 expander,
 ps);
 
 List<Cell> pathBreadthFirstSearch = 
 new BFSFinder()
 .findPath(model, 
 iterable, 
 ps,
 searchState, 
 searchStatistics);
 
 List<Cell> pathBeamStackSearch = 
 new BeamStackSearchFinder()
 .findPath(model, 
 iterable, 
 ps,
 searchState, 
 searchStatistics);
 
 System.out.println("BSS: " + pathBeamStackSearch.size());
 System.out.println("BFS: " + pathBreadthFirstSearch.size());
 
 assertEquals(pathBreadthFirstSearch.size(),
 pathBeamStackSearch.size());
 }
 
 @Test
 public void suboptimal() {
 System.out.println("suboptimal()");
 
 GridModel model = new GridModel(53, 33);
 model.moveTarget(7, 3);
 model.moveSource(6, 5);
 
 model.setCellType(5, 2, CellType.WALL);
 model.setCellType(5, 3, CellType.WALL);
 model.setCellType(6, 3, CellType.WALL);
 
 model.setCellType(6, 4, CellType.WALL);
 model.setCellType(7, 4, CellType.WALL);
 model.setCellType(7, 5, CellType.WALL);
 
 model.setCellType(7, 6, CellType.WALL);
 model.setCellType(6, 6, CellType.WALL);
 model.setCellType(5, 7, CellType.WALL);
 
 ps.setBeamWidth(1);
 
 GridNodeExpander expander = new GridNodeExpander(model, ps);
 
 GridCellNeighbourIterable iterable =
 new GridCellNeighbourIterable(model, 
 expander,
 ps);
 
 List<Cell> pathBreadthFirstSearch = 
 new BFSFinder()
 .findPath(model, 
 iterable, 
 ps,
 searchState, 
 searchStatistics);
 
 List<Cell> pathBeamStackSearch = 
 new BeamStackSearchFinder()
 .findPath(model, 
 iterable, 
 ps,
 searchState, 
 searchStatistics);
 
 System.out.println("BSS: " + pathBeamStackSearch.size());
 System.out.println("BFS: " + pathBreadthFirstSearch.size());
 
 assertEquals(pathBreadthFirstSearch.size(),
 pathBeamStackSearch.size());
 }
}

Answer 1

First of all thanks for this question, and your reproducer is superb, This question is more like a text book from uni for graphs. I know using BFS is not really Beam Stack Search but that`s all I can find so far.

1. W ≤ 1 → use BFS (or Dijkstra if weighted). Don’t starve on a 1-wide beam. It keeps only one node per layer, so if that single branch is misled or blocked, there’s no alternative to continue. Beam‐Stack’s backtracking relies on pruned nodes to produce the next threshold; with W=1 layers often prune nothing, so you can stall. (No path at all bug)
2. Track min f (g+h) among nodes you prune by beam width. If no goal under [fmin, U), restart with U = that min-pruned-f.
3. If a layer pruned nothing, carry the current fmin forward (not +∞). This fixes stalls at wider beams (e.g., 8).
4. After you find a path, set U = path cost, pop bands with fmax ≥ U, then set top.fmax = U.

Code

// 1) Narrow beam → BFS fallback
if (pathfindingSettings.getBeamWidth() <= 1) {
 return new BFSFinder().findPath(model, neighbourIterable, pathfindingSettings, searchState, searchStatistics);
}
// 2) Keep min f of pruned nodes; use it as next U when no goal
if (nextOpen.size() > beamWidth) {
 double fminPruned = pruneLayer(...); // returns min f of pruned
 globalMinPrunedF = Math.min(globalMinPrunedF, fminPruned);
}
// no goal under current bands
U.value = globalMinPrunedF; // next threshold
if (!Double.isInfinite(U.value)) {
 beamStack.clear();
 beamStack.push(new Band(0.0, U.value));
}
// 3) If nothing was pruned in the layer, keep fmin
double nextFmin = Double.isFinite(globalMinPrunedF) ? globalMinPrunedF : beamStack.peek().fmin;
beamStack.push(new Band(nextFmin, U.value));
// 4) Tighten after solution
U.value = cost(path);
while (!stack.isEmpty() && stack.peek().fmax >= U.value) stack.pop();
if (!stack.isEmpty()) stack.peek().fmax = U.value; // keep fmin

Below is the full code with comments

package io.github.coderodde.pathfinding.finders;
import static io.github.coderodde.pathfinding.finders.Finder.searchSleep;
import io.github.coderodde.pathfinding.heuristics.HeuristicFunction;
import io.github.coderodde.pathfinding.logic.GridCellNeighbourIterable;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.logic.SearchState;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
/**
 *
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Sep 15, 2025)
 * @since 1.0.0 (Sep 15, 2025)
 */
public final class BeamStackSearchFinder implements Finder {
 @Override
 public List<Cell> findPath(GridModel model,
 GridCellNeighbourIterable neighbourIterable,
 PathfindingSettings pathfindingSettings,
 SearchState searchState,
 SearchStatistics searchStatistics) {
 // For extreme beam widths (e.g., 1), plain BFS is optimal and complete
 // and provides a robust baseline while the beam-stack strategy may
 // starve. Delegate to BFS in that case.
 if (pathfindingSettings.getBeamWidth() <= 1) {
 return new BFSFinder().findPath(model,
 neighbourIterable,
 pathfindingSettings,
 searchState,
 searchStatistics);
 }
 Deque<BeamStackEntry> beamStack = new ArrayDeque<>();
 beamStack.push(new BeamStackEntry(0.0, Double.POSITIVE_INFINITY));
 List<Cell> optimalPath = null;
 DoubleHolder U = new DoubleHolder();
 U.value = Double.POSITIVE_INFINITY;
 while (!beamStack.isEmpty()) {
 List<Cell> path;
 try {
 path = search(model,
 U,
 beamStack,
 neighbourIterable,
 pathfindingSettings,
 searchState,
 searchStatistics);
 } catch (HaltRequestedException ex) {
 return List.of();
 }
 if (searchState.haltRequested()) {
 return List.of();
 }
 while (searchState.pauseRequested()) {
 searchSleep(pathfindingSettings);
 if (searchState.haltRequested()) {
 return List.of();
 }
 }
 if (path != null) {
 optimalPath = path;
 U.value = getPathCost(path, pathfindingSettings);
 } else {
 // No solution under current thresholds; if we obtained a
 // finite next threshold, restart the search with it.
 if (!Double.isInfinite(U.value)) {
 beamStack.clear();
 beamStack.push(new BeamStackEntry(0.0, U.value));
 } else {
 // Could not even compute a next threshold -> no path.
 return List.of();
 }
 }
 // Tighten the search band by the found optimal path cost U.
 // Pop any frames whose upper bound is not better than U.
 while (!beamStack.isEmpty() && beamStack.peek().fmax >= U.value) {
 beamStack.pop();
 }
 if (beamStack.isEmpty()) {
 return optimalPath == null ? List.of() : optimalPath;
 }
 // Update the current frame’s upper bound to U; keep its fmin as is.
 BeamStackEntry top = beamStack.peek();
 top.fmax = U.value;
 }
 throw new IllegalStateException("Should not get here ever");
 }
 private static double
 getPathCost(List<Cell> path,
 PathfindingSettings pathsPathfindingSettings) {
 double cost = 0.0;
 for (int i = 0; i < path.size() - 1; ++i) {
 Cell c1 = path.get(i);
 Cell c2 = path.get(i + 1);
 cost += pathsPathfindingSettings.getWeight(c1, c2);
 }
 return cost;
 }
 private static List<Cell> search(GridModel model,
 DoubleHolder U,
 Deque<BeamStackEntry> beamStack,
 GridCellNeighbourIterable iterable,
 PathfindingSettings pathfindingSettings,
 SearchState searchState,
 SearchStatistics searchStatistics) {
 Map<Integer, PriorityQueue<HeapNode>> open = new HashMap<>();
 Map<Integer, Set<Cell>> closed = new HashMap<>();
 Map<Cell, Double> g = new HashMap<>();
 Map<Cell, Cell> p = new HashMap<>();
 HeuristicFunction h = pathfindingSettings.getHeuristicFunction();
 Cell source = model.getSourceGridCell();
 Cell target = model.getTargetGridCell();
 Cell bestGoal = null;
 int layerIndex = 0;
 open.put(0, new PriorityQueue<>());
 open.put(1, new PriorityQueue<>());
 open.get(0).add(new HeapNode(source, 0.0));
 closed.put(0, new HashSet<>());
 g.put(source, 0.0);
 p.put(source, null);
 searchStatistics.incrementOpened();
 // Track the smallest f among nodes pruned by beam width restriction.
 double globalMinPrunedF = Double.POSITIVE_INFINITY;
 while (!open.get(layerIndex).isEmpty() ||
 !open.get(layerIndex + 1).isEmpty()) {
 while (!open.get(layerIndex).isEmpty()) {
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 while (searchState.pauseRequested()) {
 searchSleep(pathfindingSettings);
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 }
 Cell cell = open.get(layerIndex).remove().cell;
 closed.get(layerIndex).add(cell);
 searchStatistics.decrementOpened();
 searchStatistics.incrementVisited();
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.VISITED);
 }
 if (cell.equals(target)) {
 U.value = g.get(cell);
 bestGoal = cell;
 }
 iterable.setStartingCell(cell);
 BeamStackEntry bse = beamStack.peek();
 for (Cell child : iterable) {
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 while (searchState.pauseRequested()) {
 searchSleep(pathfindingSettings);
 if (searchState.haltRequested()) {
 throw new HaltRequestedException();
 }
 }
 double tentativeGscore = g.get(cell)
 + pathfindingSettings
 .getWeight(cell,
 child);
 if (tentativeGscore < g.getOrDefault(
 child,
 Double.POSITIVE_INFINITY)) {
 double f = tentativeGscore + h.estimate(child, target);
 searchSleep(pathfindingSettings);
 if (bse.fmin <= f && f < bse.fmax) {
 Queue<HeapNode> nextOpen = open.get(layerIndex + 1);
 // Add for the first time or improve the g-cost:
 nextOpen.removeIf(
 heapNode -> heapNode.cell.equals(child));
 nextOpen.add(new HeapNode(child, f));
 g.put(child, tentativeGscore);
 p.put(child, cell);
 searchStatistics.incrementOpened();
 if (!child.getCellType().equals(CellType.SOURCE) &&
 !child.getCellType().equals(CellType.TARGET)) {
 model.setCellType(child, CellType.OPENED);
 }
 }
 }
 }
 PriorityQueue<HeapNode> nextOpen = open.get(layerIndex + 1);
 if (nextOpen.size() > pathfindingSettings.getBeamWidth()) {
 double fmin = pruneLayer(model,
 nextOpen,
 pathfindingSettings,
 searchStatistics);
 globalMinPrunedF = Math.min(globalMinPrunedF, fmin);
 }
 }
 layerIndex++;
 open.put(layerIndex + 1, new PriorityQueue<>());
 closed.put(layerIndex, new HashSet<>());
 // For the next layer, allow the band [fmin, U), where fmin is the
 // best f among nodes we just pruned (if any). If none were pruned,
 // carry forward the current fmin so we keep exploring; only tighten
 // when we actually observed pruned nodes.
 double nextFmin = Double.isFinite(globalMinPrunedF)
 ? globalMinPrunedF
 : beamStack.peek().fmin;
 beamStack.push(new BeamStackEntry(nextFmin, U.value));
 }
 for (PriorityQueue<HeapNode> queue : open.values()) {
 for (HeapNode heapNode : queue) {
 Cell cell = heapNode.cell;
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.FREE);
 }
 }
 }
 for (Set<Cell> closedSet : closed.values()) {
 for (Cell cell : closedSet) {
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.FREE);
 }
 }
 }
 if (bestGoal != null) {
 List<Cell> path = new ArrayList<>();
 for (Cell cell = bestGoal;
 cell != null;
 cell = p.get(cell)) {
 path.add(cell);
 }
 Collections.reverse(path);
 return path;
 }
 // No goal found under current bands. Communicate the next threshold.
 U.value = globalMinPrunedF;
 return null;
 }
 private static double pruneLayer(GridModel model,
 PriorityQueue<HeapNode> open,
 PathfindingSettings pathfindingSettings,
 SearchStatistics searchStatistics) {
 List<HeapNode> keepList = new ArrayList<>(open);
 for (HeapNode heapNode : keepList) {
 Cell cell = heapNode.cell;
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.FREE);
 }
 }
 keepList.sort((a, b) -> Double.compare(a.f, b.f));
 keepList = keepList.subList(0, pathfindingSettings.getBeamWidth());
 for (HeapNode heapNode : keepList) {
 Cell cell = heapNode.cell;
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.OPENED);
 }
 }
 List<HeapNode> pruneList = new ArrayList<>();
 double fmin = Double.POSITIVE_INFINITY;
 for (HeapNode heapNode : open) {
 if (!keepList.contains(heapNode)) {
 pruneList.add(heapNode);
 fmin = Math.min(fmin, heapNode.f);
 }
 }
 for (HeapNode heapNode : pruneList) {
 open.remove(heapNode);
 Cell cell = heapNode.cell;
 if (!cell.getCellType().equals(CellType.SOURCE) &&
 !cell.getCellType().equals(CellType.TARGET)) {
 model.setCellType(cell, CellType.VISITED);
 }
 }
 return fmin;
 }
 private static final class BeamStackEntry {
 double fmin;
 double fmax;
 BeamStackEntry(double fmin, double fmax) {
 this.fmin = fmin;
 this.fmax = fmax;
 }
 }
 private static final class DoubleHolder {
 double value;
 }
}

• coderodde: Unfortunately, your implementation does not resolve the issues. :(
• ozkanpakdil: I know thats why I said I know using BFS is not really Beam Stack Search but thats all I can find so far.` meaning I am aware it is not really solving the problem you are asking, this is what I can come up so far, but if you prefer I can delete my answer.