Research

Unidirectional algorithms such as A* work forward from the start. Bidirectional heuristic search (BiHS) grows two frontiers until they meet. It can reduce search effort, but only if the algorithm knows which nodes it may safely skip. Our work characterizes the nodes that must be expanded by any admissible bidirectional algorithm and converts those characterizations into practical algorithms: front-to-end search with consistent heuristics, memory-restricted and parallel external-memory variants, unified frameworks for the bounded-suboptimal case, and extensions beyond minimization to problems such as the longest path.

Two current threads separate the two jobs every bounded-suboptimal algorithm performs: finding a solution and proving its quality. This separation allows each job to run in whichever direction suits it. We also ask whether recent shortest-path algorithms that beat the comparison-sorting barrier can be made goal-directed, giving A* the same asymptotic advantage. Supported by an Israel Science Foundation grant with Ariel Felner and Eyal Shimony.

Domain-independent heuristics such as pattern databases trade accuracy against time and memory, and that trade-off worsens as problems grow. Reinforcement learning provides another way to estimate cost-to-go without a hand-designed abstraction, but learned estimates generally do not retain the same guarantees. Their errors can direct search effort toward unproductive paths.

We study what goes wrong and how to repair it. One line concerns the bias built into Bellman-style training: the min backup used for cost-to-go systematically underestimates, which is the mirror image of the well-known overestimation from the max operator in RL. This bias can be more damaging in search because A*-style algorithms depend on the absolute magnitude of the heuristic rather than only on which action looks best. Downward bias weakens pruning and widens the search. Related work guides search with learned Q-functions and replaces single-step updates with limited-horizon lookahead. Supported by an NSF-BSF grant with Forest Agostinelli.

Classical planners require a model that specifies actions, preconditions, and effects. With Roni Stern's group we learn this model from observations, including numeric effects that cannot be represented as propositional state changes, and study how few observations suffice, how to learn online while acting, and how to combine learned symbolic models with reinforcement learning so that each covers the other's weakness. Minecraft has been a useful testbed: long horizons, crafting hierarchies, and no clean model to start from.

An agent that plans in the real world spends real time doing it, and the opportunities it plans for can expire meanwhile. That makes the allocation of planning effort a decision problem in its own right: which partial plan deserves the next unit of computation, when is a plan good enough to commit to, and when should execution begin even though planning is unfinished. We formalized this as allocating effort when actions expire, solved the known-deadline case, and have since extended the framework to interleaved and concurrent planning and execution and to the trade-off between plan cost and timeliness.

Current work pushes in two directions: situated planning where goals are optional and carry rewards, so the planner must weigh which goal set to pursue against the chance of still finding a plan in time; and deadline-aware allocation of computation in task and motion planning, where several symbolic skeletons compete for refinement time and both refinement and execution durations are uncertain.

Real routing problems rarely optimize one quantity for one agent. Multi-objective search returns a Pareto front rather than a single path, and the dominance checks against that front come to dominate runtime as the number of objectives grows. We study both the nodes that must be expanded in the multi-objective setting and the data structures used for dominance checks. Current work compares geometric indexing with the total-order trees used by existing frameworks. On the multi-agent side we work on pathfinding under different cost measures, such as minimizing fuel rather than time, on meeting problems where agents must converge on a location, and on multi-directional search where more than two frontiers interact.

A learning agent should not have to repeat a catastrophe in order to avoid it. We work on shields that accumulate safety rules from observed catastrophic effects, on constrained policies where exploration is relaxed during training but strict at deployment, and on reward structures so imbalanced that safety dominates the return, where successor features and curriculum learning help.

Current work is largely multi-agent. One thread replaces reactive constraint satisfaction with model-based foresight: a world model that predicts per-agent cost as well as reward, so most policy updates can be taken against imagined rollouts and a violation need not be experienced to be avoided. Another asks for fairness as a specification rather than a penalty weight: the user names a tolerated level of inequality between agents' outcomes and the algorithm meets it while keeping team return. Supported by grants from the Israel Ministry of Science and Technology, including work with Ayal Taitler.

When no good heuristic exists, Monte-Carlo tree search grows a tree by sampling; my earlier work used the value of information to decide what to sample next. Current work adapts MCTS to autonomous driving: learning state-dependent discretizations of continuous action spaces, predicting next states from the planned trajectories of other agents, and folding human domain knowledge into the search.

Nearby, we work on navigation when the world is only partly observable until you get there. This includes contingent planning over roadmaps whose edges may be blocked, where the plan is a policy over observation outcomes rather than a path, and it can be worth taking a longer route to learn earlier whether a shortcut is open. And with Ayal Taitler, on refining kinematic plans into trajectories a physical system can actually execute.

Language models are useful at the edges of planning: turning a natural-language request into a formal problem, driving planning tools through a conversational interface, and generating candidate structures a planner can then verify. We build and evaluate that plumbing, and we treat generation itself as a search problem when the answer has to satisfy hard constraints.

A second thread concerns what these systems retain after deletion. Removing a document from a retrieval corpus does not necessarily remove information derived from it in fine-tuned retrievers, answer caches, hierarchical index summaries, or long-horizon agent memory. We study deletion as a property of system state rather than corpus membership and develop purging procedures that target the components affected by a deletion request.