Search

We investigate a novel anytime algorithm for wireless networked control with random dropouts. The controller computes sequences of tentative future control commands using time-varying (Markovian) computation resources. The sensor-controller and controller-actuator channel states are spatial- and time-correlated and are modeled as a multi-state Markov process. We develop a novel cycle-cost-based approach to obtain stability conditions on the nonlinear plant, controller, network and computation resources.

This article addresses the almost surely exponential (ASE) stabilization problem of continuous-time jump systems realized by a stochastic scheduled controller. In this study, a stochastic scheduled controller based on the anytime algorithm is proposed. It is able to cope with the situation where no controller is added to subsystems during some time slices. Sufficient conditions for the existence of such a controller are established by applying novel techniques to its stochastic transfer matrix, and they are all presented with solvable forms. Particularly, both dwell times of the jump signal and distribution properties of stochastic scheduling are considered and proved to have played positive roles in obtaining better performance and applications. Two special situations about no jump systems with constant and varied dwell times are further studied, respectively. A practical example is offered so as to verify the effectiveness and superiority of the methods proposed in this study.

Chjara, breeder in Carg{\`e}se, has n wild pigs. She would like to sort her herd by weight to better meet the demands of her buyers. Each beast has a distinct weight, alas unknown to Chjara. All she has at her disposal is a Roberval scale, which allows her to compare two pigs only at the cost of an acrobatic manoeuvre. The balance, quite old, can break at any time. Chjara therefore wants to sort his herd in a minimum of weighings, but also to have a good estimate of the result after each weighing.To help Chjara, we pose the problem of finding a good anytime sorting algorithm, in the sense of Kendall's tau distance between provisional result and perfectly sorted list, and we bring the following contributions:- We introduce Corsort, a family of anytime sorting algorithms based on estimators.- By simulation, we show that a well-configured Corsort has a near-optimal termination time, and provides better intermediate estimates than the best sorting algorithms we are aware of., Comment: in French language, AlgoTel 2023 - 25{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications, May 2023, Cargese, France

We present an algorithm that enumerates all the minimal triangulations of a graph in incremental polynomial time. Consequently, we get an algorithm for enumerating all the proper tree decompositions, in incremental polynomial time, where “proper” means that the tree decomposition cannot be improved by removing or splitting a bag. The algorithm can incorporate any method for (ordinary, single result) triangulation or tree decomposition, and can serve as an anytime algorithm to improve such a method. We describe an extensive experimental study of an implementation on real data from different fields. Our experiments show that the algorithm improves upon central quality measures over the underlying tree decompositions, and is able to produce a large number of high-quality decompositions.

It is extremely useful to exploit labeled datasets not only to learn models and perform predictive analytics but also to improve our understanding of a domain and its available targeted classes. The subgroup discovery task has been considered for more than two decades. It concerns the discovery of patterns covering sets of objects having interesting properties, e.g., they characterize or discriminate a given target class. Though many subgroup discovery algorithms have been proposed for both transactional and numerical data, discovering subgroups within labeled sequential data has been much less studied. First, we propose an anytime algorithm SeqScout that discovers interesting subgroups w.r.t. a chosen quality measure. This is a sampling algorithm that mines discriminant sequential patterns using a multi-armed bandit model. For a given budget, it finds a collection of local optima in the search space of descriptions and thus, subgroups. It requires a light configuration and is independent from the quality measure used for pattern scoring. We also introduce a second anytime algorithm MCTSExtent that pushes further the idea of a better trade-off between exploration and exploitation of a sampling strategy over the search space. To the best of our knowledge, this is the first time that the Monte Carlo Tree Search framework is exploited in a sequential data mining setting. We have conducted a thorough and comprehensive evaluation of our algorithms on several datasets to illustrate their added value, and we discuss their qualitative and quantitative results.

Distributed Constraint Optimization Problems (DCOPs) are a widely studied constraint handling framework. The objective of a DCOP algorithm is to optimize a global objective function that can be described as the aggregation of several distributed constraint cost functions. In a DCOP, each of these functions is defined by a set of discrete variables. However, in many applications, such as target tracking or sleep scheduling in sensor networks, continuous valued variables are more suited than the discrete ones. Considering this, Functional DCOPs (F-DCOPs) have been proposed that can explicitly model a problem containing continuous variables. Nevertheless, state-of-the-art F-DCOPs approaches experience onerous memory or computation overhead. To address this issue, we propose a new F-DCOP algorithm, namely Particle Swarm based F-DCOP (PFD), which is inspired by a meta-heuristic, Particle Swarm Optimization (PSO). Although it has been successfully applied to many continuous optimization problems, the potential of PSO has not been utilized in F-DCOPs. To be exact, PFD devises a distributed method of solution construction while significantly reducing the computation and memory requirements. Moreover, we theoretically prove that PFD is an anytime algorithm. Finally, our empirical results indicate that PFD outperforms the state-of-the-art approaches in terms of solution quality and computation overhead.

In this paper, we study the problem of selecting a subset from a ground set to maximize a monotone objective function f such that a monotone cost function c is bounded by an upper limit. State-of-the-art algorithms include the generalized greedy algorithm and POMC. The former is an efficient fixed time algorithm, but the performance is limited by the greedy nature. The latter is an anytime algorithm that can find better subsets using more time, but without any polynomial-time approximation guarantee. In this paper, we propose a new anytime algorithm EAMC, which employs a simple evolutionary algorithm to optimize a surrogate objective integrating f and c. We prove that EAMC achieves the best known approximation guarantee in polynomial expected running time. Experimental results on the applications of maximum coverage, influence maximization and sensor placement show the excellent performance of EAMC.

The paper is devoted to the problem of action selection by an intelligent agent in real-time systems. This is one of the key tasks in the field of multi-agent systems in respect of the existing time constraints and incomplete perception of the surrounding world by agents. As an example, the virtual football environment, which is a highly dynamic system with a rapidly changing environment, is selected for illustration. The article analyzes and builds models of basic actions from virtual football. As a basis for these models, an approach is proposed based on the step-by-step implementation of the task under consideration with a constant assessment of the usefulness of possible options for action. The proposed algorithm also meets the requirements for anytime algorithms, which allows agent to achieve a result which quality is proportional to the time spent on calculations, which is extremely important in such a rapidly changing environment as virtual football. Experimental testing confirmed the algorithm's performance as an anytime algorithm, namely the ability to execute the algorithm faster due to the quality of the result.

This paper explores the dynamic multi-agent task allocation problem in an open and dynamic environment. Some existing works on task allocation have not been able to cater for the extra needs of scalability and robustness in large scale complex systems. Furthermore, some algorithms highly rely on the agents' organisation structure. We proposes a novel algorithm based on the notions of potential contributions, values and utilities of the individual agents and the system. A game structure is constructed to model the task allocation problem, based on which a novel algorithm POT is then proposed to search for a Nash equilibrium solution that maximises the system's potential utility. We carry out comprehensive empirical studies to demonstrate that POT achieves a higher system utility compared with the state-of-the-art GreedyNE algorithm.

Computed tomography is an important technique for non-destructive analysis of an object's internal structure, relevant for scientific studies, medical applications, and industry. Pressing challenges emerging in the field of tomographic imaging include speeding up reconstruction, reducing the time required to obtain the X-ray projections, and reducing the radiation dose imparted to the object. In this paper, we introduce a model of a monitored reconstruction process, in which the acquiring of projections is interspersed with image reconstruction. This model allows to examine the tomographic reconstruction process as an anytime algorithm and consider a problem of finding the optimal stopping point, corresponding to the required number of X-ray projections for the currently scanned object. We outline the theoretical framework for the monitored reconstruction, propose ways of constructing stopping rules for various reconstruction quality metrics and provide their experimental evaluation. Due to stopping at different times for different objects, the proposed approach allows to achieve a higher mean reconstruction quality for a given mean number of X-ray projections. Conversely, fewer projections on average are used to achieve the same mean reconstruction quality.

Human-induced faults play a large role in systems reliability. In cloud platforms, system administrators may inadvertently make catastrophic mistakes, like deleting a virtual disk with important data. Providing rollback for cloud operations can reduce the severity and impact of such mistakes, by allowing to revert to a known, good state. However, in the context of cloud management this is non-trivial, since cloud consumers only have limited visibility and indirect control. In this paper, we present a scalable approach to rollback operations that change the state of a system on proprietary cloud platforms. In our previous work, we provided a system that augments cloud APIs and provides rollback operation using an AI planner. In this paper, we build upon our previous work, but parallelize the rollback plan generation based on characteristics unique to rollback scenario. Furthermore, we introduce a distributed anytime algorithm that gradually improves plan quality over time, until either an optimal plan is found or a timeout is reached. Through experimental evaluation we show that our approach scales better than a naive approach, and effectively avoids the exponential behavior of AI planning. Further, we explore the trade-offs between the quality of rollback plans and plan generation time.

Triple-structured open data creates value in many ways. However, the reuse of datasets is still challenging. Users feel difficult to assess the usefulness of a large dataset containing thousands or millions of triples. To satisfy the needs, existing abstractive methods produce a concise high-level abstraction of data. Complementary to that, we adopt the extractive strategy and aim to select the optimum small subset of data from a dataset as a snippet to compactly illustrate the content of the dataset. This has been formulated as a combinatorial optimization problem in our previous work. In this article, we design a new algorithm for the problem, which is an order of magnitude faster than the previous one but has the same approximation ratio. We also develop an anytime algorithm that can generate empirically better solutions using additional time. To suit datasets that are partially accessible via online query services (e.g., SPARQL endpoints for RDF data), we adapt our algorithms to trade off quality of snippet for feasibility and efficiency in the Web environment. We carry out extensive experiments based on real RDF datasets and SPARQL endpoints for evaluating quality and running time. The results demonstrate the effectiveness and practicality of our proposed algorithms.

Real-time conflict takes place on Clausewitz landscapes most notably marked by fog-of-war and frictional limits, uncertainties, and misperceptions. Imposition of such factors on an opponent is, in fact, a standard tactic of confrontation, from courts of law to commerce, from political campaigns to the battlefield. Time-constrained optimization models of institutional effectiveness, based on ‘anytime algorithm’ methods, suggest that the burden of doctrinal groupthink may become synergistic with fog-of-war and friction to greatly compromise the ability of an institution to respond to shadow price demands imposed by a contending agent or environment. A different, and more direct, approach via a ‘simple’ stochastic model, provides similar insight.

Aircraft routing problem is a crucial component for flight automation. Despite recent successes, challenges still remain when the environment is dynamic and uncertain. In this paper, we tackle the following two challenges. First, when the environment is uncertain, it is much safer if the route planner can guarantee a specified level of safety. Second, when the environment is dynamic, the planner needs to adapt to the changes in the environment quickly. To address these challenges, we present three contributions. First, we propose formulating the aircraft routing problem under a dynamic and uncertain environment as a chance constrained stochastic shortest path (CC-SSP) problem. Second, we introduce an anytime algorithm for the CC-SSP problem, which is effective in a dynamic environment with limited planning time. To be more specific, we present two versions of the algorithm and compare their performances. Third, we show that the algorithm can be generalized to solve a larger class of problems called chance constrained partially observable Markov decision process (CC-POMDP).

Although existing cellular network base stations are typically immobile, the recent development of small form factor base stations and self driving cars has enabled the possibility of deploying a team of continuously moving base stations that can reorganize the network infrastructure to adapt to changing network traffic usage patterns. Given such a system of mobile base stations (MBSes) that can freely move on the road, how should their path be planned in an effort to optimize the experience of the users? This paper addresses this question by modeling the problem as a Markov Decision Process where the actions correspond to the MBSes deciding which direction to go at traffic intersections; states corresponds to the position of MBSes; and rewards correspond to minimization of packet loss in the network. A Monte Carlo Tree Search (MCTS)-based anytime algorithm that produces path plans for multiple base stations while optimizing expected packet loss is proposed. Simulated experiments in the city of Verdun, QC, Canada with varying user equipment (UE) densities and random initial conditions show that the proposed approach consistently outperforms myopic planners, and is able to achieve near-optimal performance.

Computing tight over-approximation of reach sets of a controlled uncertain dynamical system is a common practice in verification of safety-critical cyber-physical systems (CPS). While several algorithms are available for this purpose, they tend to be computationally demanding in CPS applications since here, the computational resources such as processor availability tend to be scarce, time-varying and difficult to model. A natural idea then is to design "computation-aware" algorithms that can dynamically adapt with respect to the processor availability in a provably safe manner. Even though this idea should be applicable in broader context, here we focus on ellipsoidal over-approximations. We demonstrate that the algorithms for ellipsoidal over-approximation of reach sets of uncertain linear systems, are well-suited for anytime implementation in the sense the quality of the over-approximation can be dynamically traded off depending on the computational time available, all the while guaranteeing safety. We give a numerical example to illustrate the idea, and point out possible future directions.

Anytime algorithms allow a practitioner to trade-off runtime for solution quality. This is of particular interest in multi-objective combinatorial optimization since it can be infeasible to identify all efficient solutions in a reasonable amount of time. We present a theoretical model that, under some mild assumptions, characterizes the “optimal” trade-off between runtime and solution quality, measured in terms of relative hypervolume, of anytime algorithms for bi-objective optimization. In particular, we assume that efficient solutions are collected sequentially such that the collected solution at each iteration maximizes the hypervolume indicator, and that the non-dominated set can be well approximated by a quadrant of a superellipse. We validate our model against an “optimal” model that has complete knowledge of the non-dominated set. The empirical results suggest that our theoretical model approximates the behavior of this optimal model quite well. We also analyze the anytime behavior of an $$\varepsilon $$ -constraint algorithm, and show that our model can be used to guide the algorithm and improve its anytime behavior.

As knowledge graphs are getting increasingly adopted, the question of how to maintain the validity and accuracy of our knowledge becomes ever more relevant. We introduce context-aware constraints as a means to help preserve knowledge integrity. Context-aware constraints offer a more fine-grained control of the domain onto which we impose restrictions. We also introduce a bottom-up anytime algorithm to discover contextaware constraint directly from heterogeneous knowledge graphs-graphs made up from entities and literals of various (data) types which are linked using various relations. Our method is embarrassingly parallel and can exploit prior knowledge in the form of schemas to reduce computation time. We demonstrate our method on three different datasets and evaluate its effectiveness by letting experts on knowledge validation and management assess candidate constraints in a real-world knowledge validation use case. Our results show that overall, context-aware constraints are to an extent useful for knowledge validation tasks, and that the majority of the generated constraints are well balanced with respect to complexity.

Neural networks are powerful tools for automated decision-making, with applications ranging from image recogni-tion to hiring decisions and safety-critical autonomous driving. However, due to their black-box nature and large scale, reasoning about their behavior is challenging. Statistical analysis is oftenused to infer probabilistic properties of a network, such as its robustness to noise and inaccurate inputs or the fairness of its decisions. While scalable, statistical methods can only provide probabilistic guarantees on the quality of their results and may underestimate the impact of low probability inputs leading to undesired behavior of the network.In this paper, we investigate the use of symbolic analysis and constraint solution space quantification to precisely quantify probabilistic properties in neural networks. We collect symbolic constraints corresponding to the network’s response to concrete inputs, while efficiently rejecting inputs whose responses have been seen before. We further propose a quantification procedure for the collected constraints, producing arbitrarily tight, sound interval bounds on the estimated probabilities. The proposed approach is an anytime algorithm, increasing in precision with more paths explored. We implemented our approach in SpaceScanner and demonstrate its potential in analyzing fairness, robustness, and sensitivity properties of neural networks.

With the growing interest in big data, speed-up techniques for clustering are required. The density-based spatial clustering of applications with noise (DBSCAN) has been well known in database domains. Since the DBSCAN algorithm was first proposed, several speed-up methods have been introduced. In the previous work, cell-based DBSCAN as a fast DBSCAN algorithm that divides the whole dataset into smaller cells and connects them to form clusters was proposed. In this study we propose a novel clustering algorithm called anytime algorithm for cell-based DBSCAN. The proposed algorithm connects some randomly selected cells and calculates the clustering result at high speed. Next, it repeats this process, which improves the accuracy of clustering, thereby yielding the precise results. Experimental results demonstrated that the proposed algorithm can calculate the clustering results with high accuracy at high speed.

International audience; Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.

This article investigates the problem of information-based sampling design and path planning for a mobile sensing network to predict scalar fields of monitored environments. A hierarchical framework with a built-in Gaussian Markov random field model is proposed to provide adaptive sampling for efficient field reconstruction. In the proposed framework, a nonmyopic planner is operated at a sink to navigate the mobile sensing agents in the field to the sites that are most informative. Meanwhile, a myopic planner is carried out on board each agent. A tradeoff between computationally intensive global optimization and efficient local greedy search is incorporated into the system. The mobile sensing agents can be scheduled online through an anytime algorithm to visit and observe the high-information sites. Experiments on both synthetic and real-world datasets are used to demonstrate the feasibility and efficiency of the proposed planner in model exploitation and adaptive sampling for environmental field mapping.

Anytime algorithms offer a trade-off between solution quality and computation time that has proven to be useful in autonomous systems for a wide range of real-time planning problems. In order to optimize this trade-off, an autonomous system has to solve a challenging meta-level control problem: it must decide when to interrupt the anytime algorithm and act on the current solution. Prevailing meta-level control techniques, however, make a number of unrealistic assumptions that reduce their effectiveness and usefulness in the real world. Eliminating these assumptions, we first introduce a model-free approach to meta-level control based on reinforcement learning and prove its optimality. We then offer a general meta-level control technique that can use different reinforcement learning methods. Finally, we show that our approach is effective across several common benchmark domains and a mobile robot domain.