The merge-and-shrink framework has been introduced as a general approach for defining abstractions of large state spaces arising in domain-independent planning and related areas. The distinguishing characteristic of the merge-and-shrink approach is that it operates directly on the factored representation of state spaces, repeatedly modifying this representation through transformations such as shrinking (abstracting a factor of the representation), merging (combining two factors), label reduction (abstracting the way in which different factors interact), and pruning (removing states or transitions of a factor). We provide a novel view of the merge-and-shrink framework as a “toolbox” or “algebra” of transformations on factored transition systems, with the construction of abstractions as only one possible application. For each transformation, we study desirable properties such as conservativeness (overapproximating the original transition system), inducedness (absence of spurious states and transitions), and refinability (reconstruction of paths in the original transition system from the transformed one). We provide the first complete characterizations of the conditions under which these desirable properties can be achieved. We also provide the first full formal account of factored mappings, the mechanism used within the merge-and-shrink framework to establish the relationship between states in the original and transformed factored transition system. Unlike earlier attempts to develop a theory for merge-and-shrink, our approach is fully compositional: the properties of a sequence of transformations can be entirely understood by the properties of the individual transformations involved. This aspect is key to the use of merge-and-shrink as a general toolbox for transforming factored transition systems. New transformations can easily be added to our theory, with compositionality taking care of the seamless integration with the existing components. Similarly, new properties of transformations can be integrated into the theory by showing their compositionality and studying under which conditions they are satisfied by the building blocks of merge-and-shrink.

Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence in which one needs to find a set of collision-free paths for a group of mobile agents (robots) operating in the shared workspace. Due to its importance, the problem is well-studied and multiple optimal and approximate algorithms are known. However, many of them abstract away from the kinematic constraints and assume that the agents can accelerate/decelerate instantaneously. This complicates the application of the algorithms on the real robots. In this paper, we present a method that mitigates this issue to a certain extent. The suggested solver is essentially, a prioritized planner based on the well-known Safe Interval Path Planning (SIPP) algorithm. Within SIPP we explicitly reason about the speed and the acceleration thus the constructed plans directly take kinematic constraints of agents into account. We suggest a range of heuristic functions for that setting and conduct a thorough empirical evaluation of the suggested algorithm.

The Snakes AI Competition was held by the Innopolis University and was part of the IEEE Conference on Games2020 and 2021 editions. It aimed to create a sandbox for learning and implementing artificial intelligence algorithms in agents in a ludic manner. Competitors of several countries participated in both editions of the competition, which was streamed to create asynergy between organizers and the community. The high-quality submissions and the enthusiasm around the developed framework create an exciting scenario for future extensions.

We construct a Virtual Kinematic Chain (VKC) that readily consolidates the kinematics of the mobile base, the arm, and the object to be manipulated in mobile manipulations. Accordingly, a mobile manipulation task is represented by altering the state of the constructed VKC, which can be converted to a motion planning problem, formulated, and solved by trajectory optimization. This new VKC perspective of mobile manipulation allows a service robot to (i) produce well-coordinated motions, suitable for complex household environments, and (ii) perform intricate multi-step tasks while interacting with multiple objects without an explicit definition of intermediate goals. In simulated experiments, we validate these advantages by comparing the VKC-based approach with baselines that solely optimize individual components. The results manifest that VKC-based joint modeling and planning promote task success rates and produce more efficient trajectories.

Among daily tasks of database administrators (DBAs), the analysis of query workloads to identify schema issues and improving performances is crucial. Although DBAs can easily pinpoint queries repeatedly causing performance issues, it remains challenging to automatically identify subsets of queries that share some properties only (a pattern) and simultaneously foster some target measures, such as execution time. Patterns are defined on combinations of query clauses, environment variables, database alerts and metrics and help answer questions like what makes SQL queries slow? What makes I/O communications high? Automatically discovering these patterns in a huge search space and providing them as hypotheses for helping to localize issues and root-causes is important in the context of explainable AI. To tackle it, we introduce an original approach rooted on Subgroup Discovery. We show how to instantiate and develop this generic data-mining framework to identify potential causes of SQL workloads issues. We believe that such data-mining technique is not trivial to apply for DBAs. As such, we also provide a visualization tool for interactive knowledge discovery. We analyse a one week workload from hundreds of databases from our company, make both the dataset and source code available, and experimentally show that insightful hypotheses can be discovered.

We propose a novel concise function representation for graphical models, a central theoretical framework that provides the basis for many reasoning tasks. We then show how we exploit our concise representation based on deterministic finite state automata within Bucket Elimination (BE), a general approach based on the concept of variable elimination that accommodates many inference and optimisation tasks such as most probable explanation and constrained optimisation. We denote our version of BE as FABE. By using our concise representation within FABE, we dramatically improve the performance of BE in terms of runtime and memory requirements. Results on standard benchmarks obtained using an established experimental methodology show that FABE often outperforms the best available approach (RBFAOO), leading to significant runtime improvements (up to 2 orders of magnitude in our tests).

Incremental graph search algorithms, such as D* Lite, reuse previous search efforts to speed up subsequent similar path planning tasks. These algorithms have demonstrated their efficiency in comparison with search from scratch, and have been leveraged in many applications such as navigation in unknown terrain. On the other hand, path planning typically involves optimizing multiple conflicting objectives simultaneously, such as travel risk, arrival time, etc. Multi-objective path planning is challenging as the number of "Pareto-optimal" solutions can grow exponentially with respect to the size of the graph, which makes it computationally burdensome to plan from scratch each time when similar planning tasks needs to be solved. This article presents a new multi-objective incremental search algorithm called Multi-Objective Path-Based D* Lite (MOPBD*) which reuses previous search efforts to speed up subsequent planning tasks while optimizing multiple objectives. Numerical results show that MOPBD* is more efficient than search from scratch and runs an order of magnitude faster than existing incremental method for multi-objective path planning.

Becoming a data scientist is considered a prestigious trait. Back in 2012, Harvard Business Review called'data scientist' the sexiest job of the 21st century, and the growing trend of roles in the industry seems to be confirming that statement. To confirm this sexiness is still ongoing, the info from Glassdoor shows being a data scientist is the second-best job in America in 2021. To get such a prestigious job, you have to go through rigorous job interviews. Data science questions asked can be very broad and complex. This is expected, considering the role of a data scientist usually incorporates so many areas.

AI is transforming how we live, work, and play. By enabling new technologies like self-driving cars and recommendation systems or improving old ones like medical diagnostics and search engines, the demand for expertise in AI and machine learning is growing rapidly. This course will enable you to take the first step toward solving important real-world problems and future-proofing your career. CS50's Introduction to Artificial Intelligence with Python explores the concepts and algorithms at the foundation of modern artificial intelligence, diving into the ideas that give rise to technologies like game-playing engines, handwriting recognition, and machine translation. Through hands-on projects, students gain exposure to the theory behind graph search algorithms, classification, optimization, reinforcement learning, and other topics in artificial intelligence and machine learning as they incorporate them into their own Python programs.

In this paper, we study zeroth-order algorithms for nonconvex-concave minimax problems, which have attracted widely attention in machine learning, signal processing and many other fields in recent years. We propose a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems, and its iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$, and the number of function value estimation is bounded by $\mathcal{O}(d_{x}\varepsilon^{-4}+d_{y}\varepsilon^{-6})$ per iteration. Moreover, we propose a zeroth-order block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving block-wise nonsmooth nonconvex-concave minimax optimization problems, and the iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$ and the number of function value estimation per iteration is bounded by $\mathcal{O}(K d_{x}\varepsilon^{-4}+d_{y}\varepsilon^{-6})$. To the best of our knowledge, this is the first time that zeroth-order algorithms with iteration complexity gurantee are developed for solving both general smooth and block-wise nonsmooth nonconvex-concave minimax problems. Numerical results on data poisoning attack problem validate the efficiency of the proposed algorithms.