Eyal Weiss

Eyal Weiss, Michael Margaliot

Many complex systems in biology, physics, and engineering include a large number of state-variables, and measuring the full state of the system is often impossible. Typically, a set of sensors is used to measure part of the state-variables. A system is called observable if these measurements allow to reconstruct the entire state of the system. When the system is not observable, an important and practical problem is how to add a \emph{minimal} number of sensors so that the system becomes observable. This minimal observability problem is practically useful and theoretically interesting, as it pinpoints the most informative nodes in the system. We consider the minimal observability problem for an important special class of Boolean networks, called conjunctive Boolean networks (CBNs). Using a graph-theoretic approach, we provide a necessary and sufficient condition for observability of a CBN with $n$ state-variables, and an efficient~$O(n^2)$-time algorithm for solving the minimal observability problem. We demonstrate the usefulness of these results by studying the properties of a class of random CBNs.

Eyal Weiss, Michael Margaliot

The dynamics of linear positive systems map the positive orthant to itself. In other words, it maps a set of vectors with zero sign variations to itself. This raises the following question: what linear systems map the set of vectors with $k$ sign variations to itself? We address this question using tools from the theory of cooperative dynamical systems and the theory of totally positive matrices. This yields a generalization of positive linear systems called $k$-positive linear systems, that reduces to positive systems for $k=1$. We describe applications of this new type of systems to the analysis of nonlinear dynamical systems. In particular, we show that such systems admit certain explicit invariant sets, and for the case $k=2$ establish the Poincaré-Bendixson property for any bounded trajectory.

Eyal Weiss, Michael Margaliot, Guy Even

Given a conjunctive Boolean network (CBN) with $n$ state-variables, we consider the problem of finding a minimal set of state-variables to directly affect with an input so that the resulting conjunctive Boolean control network (CBCN) is controllable. We give a necessary and sufficient condition for controllability of a CBCN; an $O(n^2)$-time algorithm for testing controllability; and prove that nonetheless the minimal controllability problem for CBNs is NP-hard.

Eyal Weiss, Gal A. Kaminka

The definition and representation of planning problems is at the heart of AI planning research. A key part is the representation of action models. Decades of advances improving declarative action model representations resulted in numerous theoretical advances, and capable, working, domain-independent planners. However, despite the maturity of the field, AI planning technology is still rarely used outside the research community, suggesting that current representations fail to capture real-world requirements, such as utilizing complex mathematical functions and models learned from data. We argue that this is because the modeling process is assumed to have taken place and completed prior to the planning process, i.e., offline modeling for offline planning. There are several challenges inherent to this approach, including: limited expressiveness of declarative modeling languages; early commitment to modeling choices and computation, that preclude using the most appropriate resolution for each action model -- which can only be known during planning; and difficulty in reliably using non-declarative, learned, models. We therefore suggest to change the AI planning process, such that is carries out online modeling in offline planning, i.e., the use of action models that are computed or even generated as part of the planning process, as they are accessed. This generalizes the existing approach (offline modeling). The proposed definition admits novel planning processes, and we suggest one concrete implementation, demonstrating the approach. We sketch initial results that were obtained as part of a first attempt to follow this approach by planning with action cost estimators. We conclude by discussing open challenges.

Eyal Weiss, Michael Margaliot

Smillie (1984) proved an interesting result on the stability of nonlinear, time-invariant, strongly cooperative, and tridiagonal dynamical systems. This result has found many applications in models from various fields including biology, ecology, and chemistry. Smith (1991) has extended Smillie's result and proved entrainment in the case where the vector field is time-varying and periodic. We use the theory of linear totally nonnegative differential systems developed by Schwarz (1970) to give a generalization of these two results. This is based on weakening the requirement for strong cooperativity to cooperativity, and adding an additional observability-type condition.

Eyal Weiss, Ariel Felner, Gal A. Kaminka

The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.

Eyal Weiss, Gal A. Kaminka

Information about action costs is critical for real-world AI planning applications. Rather than rely solely on declarative action models, recent approaches also use black-box external action cost estimators, often learned from data, that are applied during the planning phase. These, however, can be computationally expensive, and produce uncertain values. In this paper we suggest a generalization of deterministic planning with action costs that allows selecting between multiple estimators for action cost, to balance computation time against bounded estimation uncertainty. This enables a much richer -- and correspondingly more realistic -- problem representation. Importantly, it allows planners to bound plan accuracy, thereby increasing reliability, while reducing unnecessary computational burden, which is critical for scaling to large problems. We introduce a search algorithm, generalizing $A^*$, that solves such planning problems, and additional algorithmic extensions. In addition to theoretical guarantees, extensive experiments show considerable savings in runtime compared to alternatives.

Eyal Weiss

Recent work distinguishes two heterophily regimes: adversarial, where cross-class edges dilute class signal and harm classification, and informative, where the heterophilous structure itself carries useful signal. We ask: when does per-edge message routing help, and when is a uniform spectral channel sufficient? To operationalize this question we introduce Cost-Sensitive Neighborhood Aggregation (CSNA), a GNN layer that computes pairwise distance in a learned projection and uses it to soft-route each message through concordant and discordant channels with independent transformations. Under a contextual stochastic block model we show that cost-sensitive weighting preserves class-discriminative signal where mean aggregation provably attenuates it, provided $w_+/w_- > q/p$. On six benchmarks with uniform tuning, CSNA is competitive with state-of-the-art methods on adversarial-heterophily datasets (Texas, Wisconsin, Cornell, Actor) but underperforms on informative-heterophily datasets (Chameleon, Squirrel) -- precisely the regime where per-edge routing has no useful decomposition to exploit. The pattern is itself the finding: the cost function's ability to separate edge types serves as a diagnostic for the heterophily regime, revealing when fine-grained routing adds value over uniform channels and when it does not. Code is available at https://github.com/eyal-weiss/CSNA-public .

Eyal Weiss, Ariel Felner, Gal A. Kaminka

The shortest path problem in graphs is fundamental to AI. Nearly all variants of the problem and relevant algorithms that solve them ignore edge-weight computation time and its common relation to weight uncertainty. This implies that taking these factors into consideration can potentially lead to a performance boost in relevant applications. Recently, a generalized framework for weighted directed graphs was suggested, where edge-weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. We build on this framework to introduce the problem of finding the tightest admissible shortest path (TASP); a path with the tightest suboptimality bound on the optimal cost. This is a generalization of the shortest path problem to bounded uncertainty, where edge-weight uncertainty can be traded for computational cost. We present a complete algorithm for solving TASP, with guarantees on solution quality. Empirical evaluation supports the effectiveness of this approach.

Hadar Peer, Eyal Weiss, Ron Alterovitz et al.

Multi-objective search (MOS) has become essential in robotics, as real-world robotic systems need to simultaneously balance multiple, often conflicting objectives. Recent works explore complex interactions between objectives, leading to problem formulations that do not allow the usage of out-of-the-box state-of-the-art MOS algorithms. In this paper, we suggest a generalized problem formulation that optimizes solution objectives via aggregation functions of hidden (search) objectives. We show that our formulation supports the application of standard MOS algorithms, necessitating only to properly extend several core operations to reflect the specific aggregation functions employed. We demonstrate our approach in several diverse robotics planning problems, spanning motion-planning for navigation, manipulation and planning fr medical systems under obstacle uncertainty as well as inspection planning, and route planning with different road types. We solve the problems using state-of-the-art MOS algorithms after properly extending their core operations, and provide empirical evidence that they outperform by orders of magnitude the vanilla versions of the algorithms applied to the same problems but without objective aggregation.

Roger Alimi, Amir Ivry, Elad Fisher et al.

Modern magnetic sensor arrays conventionally utilize state of the art low power magnetometers such as parallel and orthogonal fluxgates. Low power fluxgates tend to have large Barkhausen jumps that appear as a dc jump in the fluxgate output. This phenomenon deteriorates the signal fidelity and effectively increases the internal sensor noise. Even if sensors that are more prone to dc jumps can be screened during production, the conventional noise measurement does not always catch the dc jump because of its sparsity. Moreover, dc jumps persist in almost all the sensor cores although at a slower but still intolerable rate. Even if dc jumps can be easily detected in a shielded environment, when deployed in presence of natural noise and clutter, it can be hard to positively detect them. This work fills this gap and presents algorithms that distinguish dc jumps embedded in natural magnetic field data. To improve robustness to noise, we developed two machine learning algorithms that employ temporal and statistical physical-based features of a pre-acquired and well-known experimental data set. The first algorithm employs a support vector machine classifier, while the second is based on a neural network architecture. We compare these new approaches to a more classical kernel-based method. To that purpose, the receiver operating characteristic curve is generated, which allows diagnosis ability of the different classifiers by comparing their performances across various operation points. The accuracy of the machine learning-based algorithms over the classic method is highly emphasized. In addition, high generalization and robustness of the neural network can be concluded, based on the rapid convergence of the corresponding receiver operating characteristic curves.