The combinatorial problems that constraint programming typically solves belong to the class of NP-hard problems. The AI planning community focuses on even harder problems: for example, classical planning is PSPACE-hard. A natural and well-known constraint programming approach to classical planning solves a succession of fixed plan-length problems, but with limited success. We revisit this approach in light of recent progress on general-purpose branching heuristics. We conduct an empirical comparison of our proposal against state-of-the-art planners.

Cooperation among different vehicles is a promising concept for route planning of Mobility as a Service (MaaS). For instance, vehicle platooning on highways decreases fuel consumption because it reduces the air resistance and several trucks cooperate with each other when planning. Traditional platooning, however, cannot model cooperation among different types of vehicles because it assumes the homogeneity of vehicle types. We study a model that permits heterogeneous cooperation and discuss a route optimization problem under assumption that the heterogeneous cooperation benefits the objective function. We experimentally evaluate the formulation through using synthetic and real graphs based on a modern integer programming solver with various parameter settings, which are not tried in previous studies. We also compare the results by the solves with simple heuristic method developed in this paper and discuss the results to reveal the properties of the optimization problem with heterogeneous vehicle types.

Search methods are useful in hierarchical task network (HTN) planning to make performance less dependent on the domain knowledge provided, and to minimize plan costs. Here we investigate Monte-Carlo tree search (MCTS) as a new algorithmic alternative in HTN planning. We implement combinations of MCTS with heuristic search in PANDA. We furthermore investigate MCTS in JSHOP, to address lifted (non-grounded) planning, leveraging the fact that, in contrast to other search methods, MCTS does not require a grounded task representation. Our new methods yield coverage performance on par with the state of the art, but in addition can effectively minimize plan cost over time.

In this paper, we investigate the combination of synthesis techniques and learning techniques to obtain safe and near optimal schedulers for a preemptible task scheduling problem. We study both model-based learning techniques with PAC guarantees and model-free learning techniques based on shielded deep Q-learning. The new learning algorithms have been implemented to conduct experimental evaluations.

Path and motion planning for autonomous systems has long been an area of research within the robotics and artificial intelligence communities. This has led to the development of a number of frameworks which formulate planning tasks in terms of mathematical optimization problems, which can then be solved by utilizing approaches from optimization theory and optimal control [1, 2]. However, planning in complex domains can be a challenging problem, and requires the agents to spend time and computational resources in order to find solutions, leading to an intrinsic need to balance computational complexity and optimality [3, 4, 5, 6, 7]. Within the path-planning community, this observation has resulted in the development of a number of approaches, which aim to explicitly capture the interplay between complexity and optimality. For example, in [8, 5, 9], the authors utilize wavelets to obtain multi-resolution representations of a two-dimensional environment for path-planning.

Markov decision processes are of major interest in the planning community as well as in the model checking community. But in spite of the similarity in the considered formal models, the development of new techniques and methods happened largely independently in both communities. This work is intended as a beginning to unite the two research branches. We consider goal-reachability analysis as a common basis between both communities. The core of this paper is the translation from Jani, an overarching input language for quantitative model checkers, into the probabilistic planning domain definition language (PPDDL), and vice versa from PPDDL into Jani. These translations allow the creation of an overarching benchmark collection, including existing case studies from the model checking community, as well as benchmarks from the international probabilistic planning competitions (IPPC). We use this benchmark set as a basis for an extensive empirical comparison of various approaches from the model checking community, variants of value iteration, and MDP heuristic search algorithms developed by the AI planning community. On a per benchmark domain basis, techniques from one community can achieve state-ofthe-art performance in benchmarks of the other community. Across all benchmark domains of one community, the performance comparison is however in favor of the solvers and algorithms of that particular community. Reasons are the design of the benchmarks, as well as tool-related limitations. Our translation methods and benchmark collection foster crossfertilization between both communities, pointing out specific opportunities for widening the scope of solvers to different kinds of models, as well as for exchanging and adopting algorithms across communities.

Battery life is yet one of the main limiting factors to a robot's total mission time, and efficient energy management is paramount in a robotic application. In this paper, we integrate energy awareness in the path planning of a mobile robot performing autonomous navigation. Our contributions are: 1) The formalization of a planning domain for mobile robot path planning which accounts for energy consumption and integrates energy actions in the generated plans; 2) A proof of concept of automatic path planning that avoids high energy areas in a known environment. We test our approach in simulation, extending an embedded computer's total battery discharge time by approximately 42.8%, and in a real ground mobile robot, achieving a mean energy draw reduction of 52.02%, both compared to conventional path planning.

We develop an effective computer model to simulate sensing environments that consist of natural trees. The simulated environments are random and contain full geometry of the tree foliage. While this simulated model can be used as a general platform for studying the sensing mechanism of different flying species, our ultimate goal is to build bat-inspired Quad-rotor UAVs— UAVs that can recreate bat’s flying behavior (e.g., obstacle avoidance, path planning) in dense vegetation. To this end, we also introduce a foliage echo simulator that can produce simulated echoes by mimicking bat’s biosonar. In our current model, a few realistic model choices or assumptions are made. First, in order to create natural looking trees, the branching structures of trees are modeled by L-systems, whereas the detailed geometry of branches, sub-branches and leaves is created by randomizing a reference tree in a CAD object file. Additionally, the foliage echo simulator is simplified so that no shading effect is considered. We demonstrate our developed model by simulating real-world scenarios with multiple trees and compute the corresponding impulse responses along a Quad-rotor trajectory.

Advances in intelligent game playing agents have led to successes in perfect information games like Go and imperfect information games like Poker. The Information Set Monte Carlo Tree Search (ISMCTS) family of algorithms outperforms previous algorithms using Monte Carlo methods in imperfect information games. In this paper, Single Observer Information Set Monte Carlo Tree Search (SO-ISMCTS) is applied to Secret Hitler, a popular social deduction board game that combines traditional hidden role mechanics with the randomness of a card deck. This combination leads to a more complex information model than the hidden role and card deck mechanics alone. It is shown in 10108 simulated games that SO-ISMCTS plays as well as simpler rule based agents, and demonstrates the potential of ISMCTS algorithms in complicated information set domains.

The debate between the optimal way of allocating societal surplus (i.e. products and services) has been raging, in one form or another, practically forever; following the collapse of the Soviet Union in 1991, the market became the only legitimate form of organisation -- there was no other alternative. Working within the tradition of Marx, Leontief, Kantorovich, Beer and Cockshott, we propose what we deem an automated planning system that aims to operate on unit level (e.g., factories and citizens), rather than on aggregate demand and sectors. We explain why it is both a viable and desirable alternative to current market conditions and position our solution within current societal structures. Our experiments show that it would be trivial to plan for up to 50K industrial goods and 5K final goods in commodity hardware.