A major challenge in decision making domains with large state spaces is to effectively select actions which maximize utility. In recent years, approaches such as reinforcement learning (RL) and search algorithms have been successful to tackle this issue, despite their differences. RL defines a learning framework that an agent explores and interacts with. Search algorithms provide a formalism to search for a solution. However, it is often difficult to evaluate the performances of such approaches in a practical way. Motivated by this problem, we focus on one game domain, i.e., Connect-4, and develop a novel evolutionary framework to evaluate three classes of algorithms: RL, Minimax and Monte Carlo tree search (MCTS). The contribution of this paper is threefold: i) we implement advanced versions of these algorithms and provide a systematic comparison with their standard counterpart, ii) we develop a novel evaluation framework, which we call the Evolutionary Tournament, and iii) we conduct an extensive evaluation of the relative performance of each algorithm to compare our findings. We evaluate different metrics and show that MCTS achieves the best results in terms of win percentage, whereas Minimax and Q-Learning are ranked in second and third place, respectively, although the latter is shown to be the fastest to make a decision.

Neural Architecture Search (NAS) has been widely adopted to design neural networks for various computer vision tasks. One of its most promising subdomains is differentiable NAS (DNAS), where the optimal architecture is found in a differentiable manner. However, gradient-based methods suffer from the discretization error, which can severely damage the process of obtaining the final architecture. In our work, we first study the risk of discretization error and show how it affects an unregularized supernet. Then, we present that penalizing high entropy, a common technique of architecture regularization, can hinder the supernet's performance. Therefore, to robustify the DNAS framework, we introduce a novel single-stage searching protocol, which is not reliant on decoding a continuous architecture. Our results demonstrate that this approach outperforms other DNAS methods by achieving 75.3% in the searching stage on the Cityscapes validation dataset and attains performance 1.1% higher than the optimal network of DCNAS on the non-dense search space comprising short connections. The entire training process takes only 5.5 GPU days due to the weight reuse, and yields a computationally efficient architecture. Additionally, we propose a new dataset split procedure, which substantially improves results and prevents architecture degeneration in DARTS.

We give a model-based agent that builds a Python program representing its knowledge of the world based on its interactions with the environment. The world model tries to explain its interactions, while also being optimistic about what reward it can achieve. We define this optimism as a logical constraint between a program and a planner. We study our agent on gridworlds, and on task planning, finding our approach is more sample-efficient compared to deep RL, more compute-efficient compared to ReAct-style agents, and that it can transfer its knowledge across environments by editing its code.

Retrosynthesis is a fundamental but challenging task in organic chemistry, with broad applications in fields such as drug design and synthesis. Given a target molecule, the goal of retrosynthesis is to find out a series of reactions which could be assembled into a synthetic route which starts from purchasable molecules and ends at the target molecule. The uncertainty of reactions used in retrosynthetic planning, which is caused by hallucinations of backward models, has recently been noticed. In this paper we propose a succinct probabilistic model to describe such uncertainty. Based on the model, we propose a new retrosynthesis planning algorithm called retro-prob to maximize the successful synthesis probability of target molecules, which acquires high efficiency by utilizing the chain rule of derivatives. Experiments on the Paroutes benchmark show that retro-prob outperforms previous algorithms, retro* and retro-fallback, both in speed and in the quality of synthesis plans.

Lane detection is a fundamental task in autonomous driving. While the problem is typically formulated as the detection of continuous boundaries, we study the problem of detecting lane boundaries that are sparsely marked by 2D points with many false positives. This problem arises in the Formula Student Driverless (FSD) competition and is challenging due to its inherent ambiguity. Previous methods are inefficient and unable to find long-horizon solutions. We propose a deterministic algorithm called CLC that uses backtracking graph search with a learned likelihood function to overcome these limitations. We impose geometric constraints on the lane candidates to guarantee a geometrically sound lane. Our exhaustive search leads to finding the global optimum in 45% of instances, and the algorithm is overall robust to up to 50% false positives. Our algorithm runs in less than 15 ms on a single CPU core, meeting the low latency requirements of autonomous racing. We extensively evaluate our method on real data and realistic racetrack layouts, and show that it outperforms the state-of-the-art by detecting long lanes over 100 m with few (0.6%) critical failures. This allows our autonomous racecar to drive close to its physical limits on a previously unknown racetrack without being limited by perception. We release our dataset with realistic Formula Student racetracks to enable further research.

This paper considers the distributed convex-concave minimax optimization under the second-order similarity. We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method, which takes the advantage of the finite-sum structure in the objective by involving the mini-batch client sampling and variance reduction. We prove SVOGS can achieve the $\varepsilon$-duality gap within communication rounds of ${\mathcal O}(\delta D^2/\varepsilon)$, communication complexity of ${\mathcal O}(n+\sqrt{n}\delta D^2/\varepsilon)$, and local gradient calls of $\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)D^2/\varepsilon\log(1/\varepsilon))$, where $n$ is the number of nodes, $\delta$ is the degree of the second-order similarity, $L$ is the smoothness parameter and $D$ is the diameter of the constraint set. We can verify that all of above complexity (nearly) matches the corresponding lower bounds. For the specific $\mu$-strongly-convex-$\mu$-strongly-convex case, our algorithm has the upper bounds on communication rounds, communication complexity, and local gradient calls of $\mathcal O(\delta/\mu\log(1/\varepsilon))$, ${\mathcal O}((n+\sqrt{n}\delta/\mu)\log(1/\varepsilon))$, and $\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)/\mu)\log(1/\varepsilon))$ respectively, which are also nearly tight. Furthermore, we conduct the numerical experiments to show the empirical advantages of proposed method.

Network interdiction problems are combinatorial optimization problems involving two players: one aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives. Such problems typically emerge in an attacker-defender context, encompassing areas such as military operations, disease spread analysis, and communication network management. The primary bottleneck in network interdiction arises from the high time complexity of using conventional exact solvers and the challenges associated with devising efficient heuristic solvers. GNNs, recognized as a cutting-edge methodology, have shown significant effectiveness in addressing single-level CO problems on graphs, such as the traveling salesman problem, graph matching, and graph edit distance. Nevertheless, network interdiction presents a bi-level optimization challenge, which current GNNs find difficult to manage. To address this gap, we represent network interdiction problems as Mixed-Integer Linear Programming (MILP) instances, then apply a multipartite GNN with sufficient representational capacity to learn these formulations. This approach ensures that our neural network is more compatible with the mathematical algorithms designed to solve network interdiction problems, resulting in improved generalization. Through two distinct tasks, we demonstrate that our proposed method outperforms theoretical baseline models and provides advantages over traditional exact solvers.

It's a puzzle that can keep most people entertained for hours. But the Rubik's Cube is light work for one robot, which has officially broken the Guinness World Record for the fastest robot to solve a rotating puzzle cube. The bot can complete the puzzle in just 0.305 seconds - so it's safe to say that if you blink, you'll miss it! That's around 10 times faster than the quickest human, who is able to solve the puzzle in an impressive 3.13 seconds. It's a puzzle that can keep most people entertained for hours. But the Rubik's Cube is light work for one robot, which has officially broken the Guinness World Record for the fastest robot to solve a rotating puzzle cube The'fastest robot to solve a rotating puzzle cube' record has been popular for years.

As the trend of moving away from high-precision maps gradually emerges in the autonomous driving industry,traditional planning algorithms are gradually exposing some problems. To address the high real-time, high precision, and high trajectory quality requirements posed by the automatic parking task under real-time perceived local maps,this paper proposes an improved automatic parking planning algorithm based on the A* algorithm, and uses Model Predictive Control (MPC) as the control module for automatic parking.The algorithm enhances the planning real-time performance by optimizing heuristic functions, binary heap optimization, and bidirectional search; it calculates the passability of narrow areas by dynamically loading obstacles and introduces the vehicle's own volume during planning; it improves trajectory quality by using neighborhood expansion and Bezier curve optimization methods to meet the high trajectory quality requirements of the parking task. After obtaining the output results of the planning algorithm, a loss function is designed according to the characteristics of the automatic parking task under local maps, and the MPC algorithm is used to output control commands to drive the car along the planned trajectory. This paper uses the perception results of real driving environments converted into maps as planning inputs to conduct simulation tests and ablation experiments on the algorithm. Experimental results show that the improved algorithm proposed in this paper can effectively meet the special requirements of automatic parking under local maps and complete the automatic parking planning and control tasks.

Automated Valet Parking (AVP) is a crucial component of advanced autonomous driving systems, focusing on the endpoint task within the "human-vehicle interaction" process to tackle the challenges of the "last mile".The perception module of the automated parking algorithm has evolved from local perception using ultrasonic radar and global scenario precise map matching for localization to a high-level map-free Birds Eye View (BEV) perception solution.The BEV scene places higher demands on the real-time performance and safety of automated parking planning tasks. This paper proposes an improved automated parking algorithm based on the A* algorithm, integrating vehicle kinematic models, heuristic function optimization, bidirectional search, and Bezier curve optimization to enhance the computational speed and real-time capabilities of the planning algorithm.Numerical optimization methods are employed to generate the final parking trajectory, ensuring the safety of the parking path. The proposed approach is experimentally validated in the commonly used industrial CARLA-ROS joint simulation environment. Compared to traditional algorithms, this approach demonstrates reduced computation time with more challenging collision-risk test cases and improved performance in comfort metrics.