Task planning with temporally extended goals (TEGs) is a critical challenge in AI and robotics, enabling agents to achieve complex sequences of objectives over time rather than addressing isolated, immediate tasks. Linear Temporal Logic on finite traces (LTLf ) provides a robust formalism for encoding these temporal goals. Traditional LTLf task planning approaches often transform the temporal planning problem into a classical planning problem with reachability goals, which are then solved using off-the-shelf planners. However, these methods often lack informed heuristics to provide a guided search for temporal goals. We introduce TIDE (Trace-Informed Depth-first Exploration), a novel approach that addresses this limitation by decomposing a temporal problem into a sequence of smaller, manageable reach-avoid sub-problems, each solvable using an off-the-shelf planner. TIDE identifies and prioritizes promising automaton traces within the domain graph, using cost-driven heuristics to guide exploration. Its adaptive backtracking mechanism systematically recovers from failed plans by recalculating costs and penalizing infeasible transitions, ensuring completeness and efficiency. Experimental results demonstrate that TIDE achieves promising performance and is a valuable addition to the portfolio of planning methods for temporally extended goals.
@article{Suprun26tide,bibtex_show=true,author={Suprun, Yuliia and Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},author+an={2=KE},title={{TIDE}: A Trace-Informed Depth-First Exploration for Planning with Temporally Extended Goals},journal={arXiv:2601.12141},year={2026},keywords={preprint}}
Journal
Falsification of Autonomous Systems in Rich Environments
Khen
Elimelech, Morteza
Lahijanian, Lydia E.
Kavraki, and Moshe Y.
Vardi
ACM Transactions on Cyber-Physical Systems (TCPS), May 2026
@article{Elimelech26tcps,bibtex_show=true,author={Elimelech, Khen and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},author+an={1=KE},title={Falsification of Autonomous Systems in Rich Environments},journal={{ACM} Transactions on Cyber-Physical Systems ({TCPS})},year={2026},issue_date={July 2026},publisher={Association for Computing Machinery},address={New York, NY, USA},volume={10},number={3},issn={2378-962X},url={https://doi.org/10.1145/3801740},doi={10.1145/3801740},month=may,articleno={35},numpages={32}}
Conference
Explaining Failures of Cyber-Physical Systems with Actual Causality
Khen
Elimelech*, Tom
Yaacov*, David A.
Kelly, Hana
Chockler, and Moshe Y.
Vardi
In IEEE International Conference on Robotics and Automation (ICRA), Vienna, Austria, Jun 2026
Modern autonomous Cyber-Physical Systems (CPSs), such as self-driving cars, face increasingly complex demands, and yet are expected to act reliably. The black-box nature often characterizing such systems, especially those relying on neural components, makes it impossible to fully verify the system behavior prior to deployment. Unfortunately, unexpected failures—cases when the system does not comply with its specification—are inevitable and may have catastrophic implications. To improve trust in the system and facilitate future mitigation after a failure occurs, it is important to try to derive an explanation for the unexpected system behavior. This paper introduces the novel concept of leveraging the framework of actual causality for CPS failure explanation. Up until now, this framework was only used to derive explanations in the context of simple systems, such as image classifiers. This paper addresses the theoretical gaps and provides the guidance needed to allow for correct explanation derivation in the CPS domain. Beyond the theoretical contribution, the paper presents two novel, practical, system-agnostic explanation derivation algorithms, allowing to prioritize either explanation optimality or derivation efficiency. The approach is demonstrated and evaluated in the context of a neural-network-controlled autonomous car, designed to avoid collisions.
@inproceedings{Elimelech26icra,bibtex_show=true,author={Elimelech, Khen and Yaacov, Tom and Kelly, David A. and Chockler, Hana and Vardi, Moshe Y.},author+an={1=KE+jointfirst;2=jointfirst},title={Explaining Failures of Cyber-Physical Systems with Actual Causality},booktitle={{IEEE} International Conference on Robotics and Automation ({ICRA})},year={2026},month=jun,location={Vienna, Austria}}
2024
Conference
Accelerating Long-Horizon Planning with Affordance-Directed Dynamic Grounding of Abstract Strategies
Khen
Elimelech, Zachary
Kingston, Wil
Thomason, Moshe Y.
Vardi, and Lydia E.
Kavraki
In IEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan, May 2024
Long-horizon task planning is important for robot autonomy, especially as a subroutine for frameworks such as Integrated Task and Motion Planning. However, task planning is computationally challenging and struggles to scale to realistic problem settings. We propose to accelerate task planning over an agent’s lifetime by integrating abstract strategies: a generalizable planning experience encoding introduced in earlier work. In this work, we contribute a practical approach to planning with strategies by introducing a novel formalism of planning in a strategy-augmented domain. We also introduce and formulate the notion of a strategy’s affordance, which indicates its predicted benefit to the solution, and use it to guide the planning and strategy grounding processes. Together, our observations yield an affordance-directed, lazy-search planning algorithm, which can seamlessly compose strategies and actions to solve long-horizon planning problems. We evaluate our planner in an object rearrangement domain, where we demonstrate performance benefits relative to a state-of-the-art task planner.
@inproceedings{Elimelech24icra,bibtex_show=true,author={Elimelech, Khen and Kingston, Zachary and Thomason, Wil and Vardi, Moshe Y. and Kavraki, Lydia E.},author+an={1=KE},title={Accelerating Long-Horizon Planning with Affordance-Directed Dynamic Grounding of Abstract Strategies},booktitle={{IEEE} International Conference on Robotics and Automation ({ICRA})},year={2024},month=may,location={Yokohama, Japan}}
Workshop
LiteRacer: a lightweight autonomous vehicle simulator for benchmarking and development of formal verification techniques
Khen
Elimelech, Morteza
Lahijanian, Lydia E.
Kavraki, and Moshe Y.
Vardi
In Workshop on Software Challenges in Formal Methods for Robotics (FMR), in conjunction with IEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan, May 2024
@inproceedings{Elimelech24icra_ws,bibtex_show=true,author={Elimelech, Khen and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},author+an={1=KE},title={LiteRacer: a lightweight autonomous vehicle simulator for benchmarking and development of formal verification techniques},booktitle={Workshop on Software Challenges in Formal Methods for Robotics (FMR), in conjunction with {IEEE} International Conference on Robotics and Automation ({ICRA})},year={2024},month=may,location={Yokohama, Japan},keywords={workshop}}
Workshop
Encoding Reusable Multi-Robot Planning Strategies as Abstract Hypergraphs
Khen
Elimelech, James
Motes, Marco
Morales, Nancy M.
Amato, Moshe Y.
Vardi, and Lydia E.
Kavraki
In 40th Anniversary of the IEEE International Conference on Robotics and Automation (ICRA@40), Rotterdam, Netherlands, Sep 2024
Multi-Robot Task Planning (MR-TP) is the search for a discrete-action plan a team of robots should take to complete a task. The complexity of such problems scales exponentially with the number of robots and task complexity, making them challenging for online solution. To accelerate MR-TP over a system’s lifetime, this work looks at combining two recent advances: (i) Decomposable State Space Hypergraph (DaSH), a novel hypergraph-based framework to efficiently model and solve MR-TP problems; and (ii) learning-by-abstraction, a technique that enables automatic extraction of generalizable planning strategies from individual planning experiences for later reuse. Specifically, we wish to extend this strategy-learning technique, originally designed for single-robot planning, to benefit multi-robot planning using hypergraph-based MR-TP.
@inproceedings{Elimelech24icra40,bibtex_show=true,author={Elimelech, Khen and Motes, James and Morales, Marco and Amato, Nancy M. and Vardi, Moshe Y. and Kavraki, Lydia E.},author+an={1=KE+jointfirst;2=jointfirst},title={Encoding Reusable Multi-Robot Planning Strategies as Abstract Hypergraphs},booktitle={40th Anniversary of the IEEE International Conference on Robotics and Automation (ICRA@40)},year={2024},month=sep,location={Rotterdam, Netherlands},keywords={workshop}}
2023
Conference
Extracting generalizable skills from a single plan execution using abstraction-critical state detection
Khen
Elimelech, Lydia E.
Kavraki, and Moshe Y.
Vardi
In IEEE International Conference on Robotics and Automation (ICRA), London, UK, May 2023
Robotic task planning is computationally challenging. To reduce planning cost and support life-long operation, we must leverage prior planning experience. To this end, we address the problem of extracting reusable and generalizable abstract skills from successful plan executions. In previous work, we introduced a supporting framework, allowing us, theoretically, to extract an abstract skill from a single execution and later automatically adapt it and reuse it in new domains. We also proved that, given a library of such skills, we can significantly reduce the planning effort for new problems. Nevertheless, until now, abstract-skill extraction could only be performed manually. In this paper, we finally close the automation loop and explain how abstract skills can be practically and automatically extracted. We start by analyzing the desired qualities of an abstract skill and formulate skill extraction as an optimization problem. We then develop two extraction algorithms, based on the novel concept of abstraction-critical state detection. As we show experimentally, the approach is independent of any planning domain.
@inproceedings{Elimelech23icra,bibtex_show=true,author={Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},author+an={1=KE},title={Extracting generalizable skills from a single plan execution using abstraction-critical state detection},booktitle={{IEEE} International Conference on Robotics and Automation ({ICRA})},year={2023},month=may,location={London, UK}}
2022
Journal
Simplified decision making in the belief space using belief sparsification
Khen
Elimelech and Vadim
Indelman
International Journal of Robotics Research (IJRR), May 2022
In this work, we introduce a new and efficient solution approach for the problem of decision making under uncertainty, which can be formulated as decision making in a belief space, over a possibly high-dimensional state space. Typically, to solve a decision problem, one should identify the optimal action from a set of candidates, according to some objective. We claim that one can often generate and solve an analogous yet simplified decision problem, which can be solved more efficiently. A wise simplification method can lead to the same action selection, or one for which the maximal loss in optimality can be guaranteed. Furthermore, such simplification is separated from the state inference and does not compromise its accuracy, as the selected action would finally be applied on the original state. First, we present the concept for general decision problems and provide a theoretical framework for a coherent formulation of the approach. We then practically apply these ideas to decision problems in the belief space, which can be simplified by considering a sparse approximation of their initial belief. The scalable belief sparsification algorithm we provide is able to yield solutions which are guaranteed to be consistent with the original problem. We demonstrate the benefits of the approach in the solution of a realistic active-SLAM problem and manage to significantly reduce computation time, with no loss in the quality of solution. This work is both fundamental and practical and holds numerous possible extensions.
@article{Elimelech22ijrr,bibtex_show=true,author={Elimelech, Khen and Indelman, Vadim},author+an={1=KE},title={Simplified decision making in the belief space using belief sparsification},journal={International Journal of Robotics Research ({IJRR})},volume={41},number={5},pages={470-496},doi={10.1177/02783649221076381},year={2022}}
Conference
Automatic cross-domain task plan transfer by caching abstract skills
Khen
Elimelech, Lydia E.
Kavraki, and Moshe Y.
Vardi
In Workshop on the Algorithmic Foundations of Robotics (WAFR), College Park, MD, USA, Jun 2022
Solving realistic robotic task planning problems is computationally demanding. To better exploit the planning effort, and reduce the future planning cost, it is important to increase the reusability of successful plans. To this end, we suggest a systematic and automatable approach for plan transfer, by rethinking the plan caching procedure. Specifically, instead of caching successful plans in their original domain, we suggest transferring them upon discovery to a dynamically-defined abstract domain, and cache them as "abstract skills" there. This technique allows us to maintain a unified, standardized, and compact skill database, to avoid skill redundancy, and to support lifelong operation. Cached skills can later be reconstructed into new domains on demand, and be applied to new tasks, with no human intervention. This is made possible thanks to the novel concept of "abstraction keys". An abstraction key, when coupled with a skill, provides all the necessary information to cache it, reconstruct it, and transfer it across all domains in which it is applicable – even domains we have yet to encounter. We practically demonstrate the approach by providing two examples of such keys, and explain how they can be used in a manipulation planning domain.
@inproceedings{Elimelech22wafr,bibtex_show=true,author={Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},author+an={1=KE},title={Automatic cross-domain task plan transfer by caching abstract skills},booktitle={Workshop on the Algorithmic Foundations of Robotics ({WAFR})},year={2022},month=jun,location={College Park, MD, USA}}
Conference
Efficient task planning using abstract skills and dynamic road map matching
Khen
Elimelech, Lydia E.
Kavraki, and Moshe Y.
Vardi
In International Symposium on Robotics Research (ISRR), Geneva, Switzerland, Sep 2022
Task planning is the problem of finding a discrete sequence of actions to achieve a goal. Unfortunately, task planning in robotic domains is computationally challenging. To address this, in our prior work, we explained how knowledge from a successful task solution can be cached for later use, as an “abstract skill." Such a skill is represented as a trace of states (“road map") in an abstract space and can be matched with new tasks on-demand. This paper explains how one can use a library of abstract skills, derived from past planning experience, to reduce the computational cost of solving new task planning problems. As we explain, matching a skill to a task allows us to decompose it into independent sub-tasks, which can be quickly solved in parallel. This can be done automatically and dynamically during planning. We begin by formulating this problem of “planning with skills" as a constraint satisfaction problem. We then provide a hierarchical solution algorithm, which integrates with any standard task planner. Finally, we experimentally demonstrate the computational benefits of the approach for reach-avoid tasks.
@inproceedings{Elimelech22isrr,bibtex_show=true,author={Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},author+an={1=KE},title={Efficient task planning using abstract skills and dynamic road map matching},booktitle={International Symposium on Robotics Research ({ISRR})},year={2022},month=sep,location={Geneva, Switzerland}}
2021
Journal
Efficient Modification of the Upper Triangular Square Root Matrix on Variable Reordering
Khen
Elimelech and Vadim
Indelman
IEEE Robotics and Automation Letters (RA-L), Apr 2021
In probabilistic state inference, we seek to estimate the state of an (autonomous) agent from noisy observations. It can be shown that, under certain assumptions, finding the estimate is equivalent to solving a linear least squares problem. Solving such a problem is done by calculating the upper triangular matrix R from the coefficient matrix A, using the QR or Cholesky factorizations; this matrix is commonly referred to as the "square root matrix". In sequential estimation problems, we are often interested in periodic optimization of the state variable order, e.g., to reduce fill-in, or to apply a predictive variable ordering tactic; however, changing the variable order implies expensive re-factorization of the system. Thus, we address the problem of modifying an existing square root matrix R, to convey reordering of the variables. To this end, we identify several conclusions regarding the effect of column permutation on the factorization, to allow efficient modification of R, without accessing A at all, or with minimal re-factorization. The proposed parallelizable algorithm achieves a significant improvement in performance over the state-of-the-art incremental Smoothing And Mapping (iSAM2) algorithm, which utilizes incremental factorization to update R.
@article{Elimelech21ral,bibtex_show=true,author={Elimelech, Khen and Indelman, Vadim},author+an={1=KE},title={Efficient Modification of the Upper Triangular Square Root Matrix on Variable Reordering},journal={{IEEE} Robotics and Automation Letters ({RA-L})},volume={6},number={2},pages={675-682},doi={10.1109/LRA.2020.3048663},issn={2377-3766},year={2021},month=apr,note={also selected for presentation at ICRA 2021}}
Thesis
Efficient Decision Making under Uncertainty in High-Dimensional State Spaces
Khen
Elimelech
Technion – Israel Institute of Technology, Jun 2021
@phdthesis{Elimelech21thesis,bibtex_show=true,author={Elimelech, Khen},author+an={1=KE},title={Efficient Decision Making under Uncertainty in High-Dimensional State Spaces},school={Technion -- Israel Institute of Technology},month=jun,year={2021},}
Preprint
Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic
In this work, we examine the problem of online decision making under uncertainty, which we formulate as planning in the belief space. Maintaining beliefs (i.e., distributions) over high-dimensional states (e.g., entire trajectories) was not only shown to significantly improve accuracy, but also allows planning with information-theoretic objectives, as required for the tasks of active SLAM and information gathering. Nonetheless, planning under this "smoothing" paradigm holds a high computational complexity, which makes it challenging for online solution. Thus, we suggest the following idea: before planning, perform a standalone state variable reordering procedure on the initial belief, and "push forwards" all the predicted loop closing variables. Since the initial variable order determines which subset of them would be affected by incoming updates, such reordering allows us to minimize the total number of affected variables, and reduce the computational complexity of candidate evaluation during planning. We call this approach PIVOT: Predictive Incremental Variable Ordering Tactic. Applying this tactic can also improve the state inference efficiency; if we maintain the PIVOT order after the planning session, then we should similarly reduce the cost of loop closures, when they actually occur. To demonstrate its effectiveness, we applied PIVOT in a realistic active SLAM simulation, where we managed to significantly reduce the computation time of both the planning and inference sessions. The approach is applicable to general distributions, and induces no loss in accuracy.
@article{Elimelech21pivot_preprint,bibtex_show=true,author={Elimelech, Khen and Indelman, Vadim},author+an={1=KE},title={Efficient Belief Space Planning in High-Dimensional State Spaces using {PIVOT}: {P}redictive {I}ncremental {V}ariable {O}rdering {T}actic},journal={arXiv:2112.14428},year={2021},month=dec,keywords={preprint}}
2019
Conference
Introducing PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning
Khen
Elimelech and Vadim
Indelman
In International Symposium on Robotics Research (ISRR), Hanoi, Vietnam, Oct 2019
Belief Space Planning (BSP) is a fundamental technique in artificial intelligence and robotics, which is widely used in the solution of problems such as online autonomous navigation and manipulation. Unfortunately, BSP is computationally demanding, especially when dealing with high-dimensional state spaces. We thus introduce PIVOT: Predictive Incremental Variable Ordering Tactic, a novel approach to improve planning efficiency. Although variable ordering has been extensively used for the state inference problem, variable ordering specifically for planning has hardly been considered. Interestingly, this tactic can also lead to improved loop-closing efficiency during state inference. We use the approach in an active-SLAM scenario, and demonstrate a significant improvement in efficiency. This approach follows our previous work regarding efficient BSP via belief sparsification.
@inproceedings{Elimelech19isrr,bibtex_show=true,author={Elimelech, Khen and Indelman, Vadim},author+an={1=KE},title={Introducing {PIVOT}: {P}redictive {I}ncremental {V}ariable {O}rdering {T}actic for Efficient Belief Space Planning},booktitle={International Symposium on Robotics Research ({ISRR})},year={2019},month=oct,location={Hanoi, Vietnam},}
2017
Conference
Consistent Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces
Khen
Elimelech and Vadim
Indelman
In IEEE International Conference on Robotics and Automation (ICRA), Singapore, May 2017
In this paper we introduce a novel approach for efficient decision making under uncertainty and belief space planning, in high dimensional state spaces. While recently developed methods focus on sparsifying the inference process, the sparsification here is done in the context of efficient decision making, with no impact on the state inference. By identifying state variables which are uninvolved in the decision, we generate a sparse version of the state’s information matrix, to be used in the examination of candidate actions. This sparse approximation is action-consistent, i.e. has no influence on the action selection. Overall we manage to maintain the same quality of solution, while reducing the computational complexity of the problem. The approach is put to the test in a SLAM simulation, where a significant improvement in runtime is achieved. Nevertheless, the method is generic, and not tied to a specific type of problem.
@inproceedings{Elimelech17icra,bibtex_show=true,author={Elimelech, Khen and Indelman, Vadim},author+an={1=KE},title={Consistent Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces},booktitle={{IEEE} International Conference on Robotics and Automation ({ICRA})},pages={3786-3791},doi={10.1109/ICRA.2017.7989437},year={2017},month=may,location={Singapore}}
Conference
Scalable Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces
Khen
Elimelech and Vadim
Indelman
In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, Canada, Sep 2017
In this paper we introduce a novel sparsification method for efficient decision making under uncertainty and belief space planning in high dimensional state spaces. By using a sparse version of the state’s information matrix, we are able to improve the high computational cost of examination of all candidate actions. We also present an in-depth analysis for the general case of approximated decision making, and use it in order to set bounds over the induced error in potential revenue. The scalability of the method allows balancing between the degree of sparsification and the tolerance for this error, in order to maximize its benefits. The approach differs from recent methods by focusing on improving the decision making process directly, and not as a byproduct of a sparsification of the state inference. Eventually, we demonstrate the superiority of the approach in a SLAM simulation, where we manage to maintain the accuracy of the solution, while demonstrating a significant improvement in run time.
@inproceedings{Elimelech17iros,bibtex_show=true,author={Elimelech, Khen and Indelman, Vadim},author+an={1=KE},title={Scalable Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces},booktitle={{IEEE/RSJ} International Conference on Intelligent Robots and Systems ({IROS})},pages={5668-5673},doi={10.1109/IROS.2017.8206456},year={2017},month=sep,location={Vancouver, Canada}}
Conference
Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations
Khen
Elimelech and Vadim
Indelman
In International Symposium on Robotics Research (ISRR), Puerto Varas, Chile, Dec 2017
In this paper we develop a novel paradigm to efficiently solve decision making and planning problems, and demonstrate it for the challenging case of planning under uncertainty. While conventional methods tend to optimize properties of specific problems, and sacrifice performance in order to reduce their complexity, our approach has no coupling to a specific problem, and relies solely on the structure of the general decision making problem, in order to directly reduce its computational cost, with no influence over the quality of solution, nor the maintained state. Using bounded approximations of the state, we can easily eliminate unfit actions, while sparing the need to evaluate the exact revenues (or rewards) of all the candidate actions. The original problem can then be solved considering a minimal subset of candidates. Since the approach is especially relevant when the action domain is large, and revenues are expensive to evaluate, we later extend the discussion specifically for decision making under uncertainty and belief space planning, and present dedicated and practical tools, in order to apply the method to a sensor deployment problem. This paper continues our previous work towards efficient decision making.
@inproceedings{Elimelech17isrr,bibtex_show=true,author={Elimelech, Khen and Indelman, Vadim},author+an={1=KE},title={Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations},booktitle={International Symposium on Robotics Research ({ISRR})},year={2017},month=dec,location={Puerto Varas, Chile},keywords={duplicate}}