Khen Elimelech

To download full texts, visit my ResearchGate profile.

Preprints

"Falsification of Autonomous Systems in Rich Environments"

Khen Elimelech, Morteza Lahijanian, Lydia E. Kavraki, and Moshe Y. Vardi

arXiv:2412.17992, December 2024.

@article{Elimelech24falsification_preprint,
  author = {Elimelech, Khen and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  title = {Falsification of Autonomous Systems in Rich Environments},
  journal = {arXiv:2412.17992},
  year = {2024},
  month = dec,
  keywords = {preprint}
}

Validating the behavior of autonomous Cyber-Physical Systems (CPS) and Artificial Intelligence (AI) agents, which rely on automated controllers, is an objective of great importance. In recent years, Neural-Network (NN) controllers have been demonstrating great promise. Unfortunately, such learned controllers are often not certified and can cause the system to suffer from unpredictable or unsafe behavior. To mitigate this issue, a great effort has been dedicated to automated verification of systems. Specifically, works in the category of “black-box testing” rely on repeated system simulations to find a falsifying counterexample of a system run that violates a specification. As running high-fidelity simulations is computationally demanding, the goal of falsification approaches is to minimize the simulation effort (NN inference queries) needed to return a falsifying example. This often proves to be a great challenge, especially when the tested controller is well-trained. This work contributes a novel falsification approach for autonomous systems under formal specification operating in uncertain environments. We are especially interested in CPS operating in rich, semantically-defined, open environments, which yield high-dimensional, simulation-dependent sensor observations. Our approach introduces a novel reformulation of the falsification problem as the problem of planning a trajectory for a “meta-system,” which wraps and encapsulates the examined system; we call this approach: meta-planning. This formulation can be solved with standard sampling-based motion-planning techniques (like RRT) and can gradually integrate domain knowledge to improve the search. We support the suggested approach with an experimental study on falsification of an obstacle-avoiding autonomous car with a NN controller, where meta-planning demonstrates superior performance over alternative approaches.

"Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic"

Khen Elimelech, and Vadim Indelman

arXiv:2112.14428, December 2021.

@article{Elimelech21ipivot_preprint,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  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}
}

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.

Journal Articles

"Simplified decision making in the belief space using belief sparsification"

Khen Elimelech, and Vadim Indelman

International Journal of Robotics Research (IJRR), vol. 41, num. 5, pp. 470-496, 2022.

@article{Elimelech22ijrr,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  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},
  note = {initially submitted Dec. 2018.}
}

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.

"Efficient Modification of the Upper Triangular Square Root Matrix on Variable Reordering"

Khen Elimelech, and Vadim Indelman

IEEE Robotics and Automation Letters (RA-L), vol. 6, num. 2, pp. 675-682, April 2021.

@article{Elimelech21ral,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  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}
}

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.

In Conference Proceedings

"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), May 2024.

@inproceedings{Elimelech24icra,
  author = {Elimelech, Khen and Kingston, Zachary and Thomason, Wil and Vardi, Moshe Y. and Kavraki, Lydia E.},
  main_auth = {1},
  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}
}

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.

"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), May 2023.

@inproceedings{Elimelech23icra,
  author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  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}
}

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.

"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), September 2022.

@inproceedings{Elimelech22isrr,
  author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  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}
}

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.

"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), June 2022.

@inproceedings{Elimelech22wafr,
  author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  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}
}

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.

"Introducing PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning"

Khen Elimelech, and Vadim Indelman

In International Symposium on Robotics Research (ISRR), October 2019.

@inproceedings{Elimelech19isrr,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  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},
  keywords = {duplicate}
}

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.

"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), December 2017.

@inproceedings{Elimelech17isrr,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  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}
}

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.

"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), pp. 5668-5673, September 2017.

@inproceedings{Elimelech17iros,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  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}
}

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.

"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), pp. 3786-3791, May 2017.

@inproceedings{Elimelech17icra,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  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}
}

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.

In Professional Workshops

"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), September 2024.

@inproceedings{Elimelech24icra40,
  author = {Elimelech, Khen and Motes, James and Morales, Marco and Amato, Nancy M. and Vardi, Moshe Y. and Kavraki, Lydia E.},
  main_auth = {1,2},
  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}
}

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.

"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) Workshop, in conjunction with IEEE International Conference on Robotics and Automation (ICRA), May 2024.

@inproceedings{Elimelech24icra_ws,
  author = {Elimelech, Khen and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  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) Workshop, in conjunction with {IEEE} International Conference on Robotics and Automation ({ICRA})},
  year = {2024},
  month = may,
  location = {Yokohama, Japan},
  url = {https://github.com/khen/LiteRacer},
  keywords = {workshop}
}

"Extracting generalizable skills from a single plan execution using abstraction-critical state detection"

Khen Elimelech, Lydia E. Kavraki, and Moshe Y. Vardi

In Workshop on Mobile Manipulation and Embodied Intelligence (MOMA): Challenges and Opportunities, in conjunction with IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), October 2022.

@inproceedings{Elimelech22iros_ws,
  author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  title = {Extracting generalizable skills from a single plan execution using abstraction-critical state detection},
  booktitle = {Workshop on Mobile Manipulation and Embodied Intelligence (MOMA): Challenges and Opportunities, in conjunction with {IEEE/RSJ} International Conference on Intelligent Robots and Systems ({IROS})},
  year = {2022},
  month = oct,
  location = {Kyoto, Japan},
  keywords = {workshop, duplicate}
}

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 recently published 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 provide an overview of this transfer framework and finally close the automation loop by explaining how abstract skills can be automatically extracted. Practically, we formulate skill extraction as an optimization problem and develop two extraction algorithms, based on the novel concept of abstraction-critical state detection. As we show experimentally, the approach is applicable in both geometric and symbolic (e.g., robotic manipulation) planning domains.

"Automatic cross-domain task plan transfer by caching abstract skills"

Khen Elimelech, Lydia E. Kavraki, and Moshe Y. Vardi

In Workshop on Generalization in Planning (GenPlan), in conjunction with International Joint Conference on Artificial Intelligence (IJCAI), July 2022.

@inproceedings{Elimelech22ijcai_ws,
  author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  title = {Automatic cross-domain task plan transfer by caching abstract skills},
  booktitle = {Workshop on Generalization in Planning (GenPlan), in conjunction with International Joint Conference on Artificial Intelligence ({IJCAI})},
  year = {2022},
  month = jul,
  location = {Vienna, Austria},
  keywords = {workshop, duplicate}
}

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.

"Efficient Belief Space Planning using Sparse Approximations"

Khen Elimelech, and Vadim Indelman

In Pioneers Workshop, in conjunction with Robotics: Science and Systems (R:SS), June 2019.

@inproceedings{Elimelech19pioneers_ws,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  title = {Efficient Belief Space Planning using Sparse Approximations},
  booktitle = {Pioneers Workshop, in conjunction with Robotics: Science and Systems ({R:SS})},
  year = {2019},
  month = jun,
  location = {Freiburg, Germany},
  keywords = {workshop}
}

"PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning"

Khen Elimelech, and Vadim Indelman

In Workshop on Toward Online Optimal Control of Dynamic Robots, in conjunction with IEEE International Conference on Robotics and Automation (ICRA), May 2019.

@inproceedings{Elimelech19icra_ws,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  title = {{PIVOT}: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning},
  booktitle = {Workshop on Toward Online Optimal Control of Dynamic Robots, in conjunction with {IEEE} International Conference on Robotics and Automation ({ICRA})},
  year = {2019},
  month = may,
  location = {Montreal, Canada},
  keywords = {workshop}
}

"A Sparsification Method for Efficient Decision Making under Uncertainty in High Dimensional State Spaces"

Khen Elimelech, and Vadim Indelman

In Israel Annual Conference on Aerospace Sciences (IACAS), March 2017.

@inproceedings{Elimelech17iacas,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  title = {A Sparsification Method for Efficient Decision Making under Uncertainty in High Dimensional State Spaces},
  booktitle = {{I}srael Annual Conference on Aerospace Sciences ({IACAS})},
  year = {2017},
  month = mar,
  location = {Tel Aviv, Israel},
  keywords = {workshop}
}

In Collections (Book Chapters)

"Automatic Cross-domain Task Plan Transfer by Caching Abstract Skills"

Khen Elimelech, Lydia E. Kavraki, and Moshe Y. Vardi

In Algorithmic Foundations of Robotics XV, Springer Proceedings in Advanced Robotics (SPAR), vol. 25, pp. 470-487, Springer International Publishing, 2023.

@incollection{Elimelech23wafr_chapter,
  author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  editor = {LaValle, Steven M. and O'Kane, Jason M. and Otte, Michael and Sadigh, Dorsa and Tokekar, Pratap},
  title = {Automatic Cross-domain Task Plan Transfer by Caching Abstract Skills},
  booktitle = {Algorithmic Foundations of Robotics XV},
  pages = {470-487},
  series = {Springer Proceedings in Advanced Robotics (SPAR)},
  volume = {25},
  publisher = {Springer International Publishing},
  address = {Cham, Switzerland},
  doi = {10.1007/978-3-031-21090-7_28},
  isbn = {978-3-031-21090-7},
  year = {2023}
}

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.

"Efficient task planning using abstract skills and dynamic road map matching"

Khen Elimelech, Lydia E. Kavraki, and Moshe Y. Vardi

In Robotics Research, Springer Proceedings in Advanced Robotics (SPAR), vol. 27, pp. 487–503, Springer International Publishing, 2023.

@incollection{Elimelech23isrr_chapter,
  author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.},
  main_auth = {1},
  editor = {Billard, Aude and Asfour, Tamim and Khatib, Oussama},
  title = {Efficient task planning using abstract skills and dynamic road map matching},
  booktitle = {Robotics Research},
  pages = {487–503},
  series = {Springer Proceedings in Advanced Robotics (SPAR)},
  volume = {27},
  publisher = {Springer International Publishing},
  address = {Cham, Switzerland},
  doi = {10.1007/978-3-031-25555-7_33},
  isbn = {978-3-031-25554-7},
  year = {2023}
}

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.

"Introducing PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning"

Khen Elimelech, and Vadim Indelman

In Robotics Research, Springer Proceedings in Advanced Robotics (SPAR), vol. 20, pp. 85-101, Springer International Publishing, 2022.

@incollection{Elimelech22isrr_chapter,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  editor = {Asfour, Tamim and Yoshida, Eiichi and Park, Jaeheung and Christensen, Henrik and Khatib, Oussama},
  title = {Introducing {PIVOT}: {P}redictive {I}ncremental {V}ariable {O}rdering {T}actic for Efficient Belief Space Planning},
  booktitle = {Robotics Research},
  pages = {85-101},
  series = {Springer Proceedings in Advanced Robotics (SPAR)},
  volume = {20},
  publisher = {Springer International Publishing},
  address = {Cham, Switzerland},
  doi = {10.1007/978-3-030-95459-8_6},
  isbn = {978-3-030-95459-8},
  year = {2022}
}

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.

"Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations"

Khen Elimelech, and Vadim Indelman

In Robotics Research, Springer Proceedings in Advanced Robotics (SPAR), vol. 10, pp. 843-858, Springer International Publishing, 2020.

@incollection{Elimelech20isrr_chapter,
  author = {Elimelech, Khen and Indelman, Vadim},
  main_auth = {1},
  editor = {Amato, Nancy M. and Hager, Greg and Thomas, Shawna and Torres-Torriti, Miguel},
  title = {Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations},
  booktitle = {Robotics Research},
  pages = {843-858},
  series = {Springer Proceedings in Advanced Robotics (SPAR)},
  volume = {10},
  publisher = {Springer International Publishing},
  address = {Cham, Switzerland},
  doi = {10.1007/978-3-030-28619-4_58},
  isbn = {978-3-030-28619-4},
  year = {2020}
}

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 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 exactly evaluate the objective function for 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 the objective function is 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.

Theses

"Efficient Decision Making under Uncertainty in High-Dimensional State Spaces"

Khen Elimelech

Technion – Israel Institute of Technology, June 2021.

@phdthesis{Elimelech21thesis,
  author = {Elimelech, Khen},
  main_auth = {1},
  title = {Efficient Decision Making under Uncertainty in High-Dimensional State Spaces},
  school = {Technion -- Israel Institute of Technology},
  month = jun,
  year = {2021}
}