A common way to represent dynamic 2D open spaces in robotics and video games for any-angle path planning is through the use of a grid with blocked and unblocked cells. The Basic Theta* algorithm is an existing algorithm that produces near-optimal solutions with a running time close to A* on 8-directional grids. However, a disadvantage is that it often finds non-taut paths that make unnecessary turns. In this paper, we demonstrate that by restricting the search space of Theta* to taut paths, the algorithm will, in most cases, find much shorter paths than the original. We describe two novel variants of the Theta* algorithm, which are simple to implement and use, yet produce a remarkable improvement over Theta* in terms of path length, with a very small running time trade-off. Another side benefit is that almost all paths found will be taut, which makes more convincing paths.

Planning in hybrid systems is important for dealing with real-world applications. PDDL+ supports this representation of domains with mixed discrete and continuous dynamics, and supports events and processes modelling exogenous change. Motivated by numerous SAT-based planning approaches, we propose an approach to PDDL+ planning through SMT, describing an SMT encoding that captures all the features of the PDDL+ problem as published by Fox and Long. The encoding can be applied on domains with nonlinear continuous change. We apply this encoding in a simple planning algorithm, demonstrating excellent results on a set of benchmark problems.

Even in today’s world of increasingly faster storage technologies, magnetic tapes continue to play an essential role in the market. Yet, they are often overlooked in the literature, despite the many changes made to the underlying tape architecture since they were conceived. In this article, we introduce the LINEAR TAPE SCHEDULING PROBLEM (LTSP), which aims to identify scheduling strategies for read and write operations in single-tracked magnetic tapes that minimize the overall response times for read requests. Structurally, LTSP has many similarities with versions of the Travelling Repairman Problem and of the Dial-a-Ride Problem restricted to the real line. We investigate several properties of LTSP and show how they can be explored in the design of algorithms for the online version of the problem. Computational experiments show that the resulting strategies deliver very satisfactory scheduling plans, which in most cases are clearly superior (potentially differing by one order of magnitude) to those produced by a strategy currently used in the industry.

Interaction with users is a key capability of planning systems that are applied in real-world settings. Such a system has to be able to react appropriately to requests issued by its users. Most of these systems are based on a generated plan that is continually criticised by him, resulting in a mixed-initiative planning system. We present several practically relevant requests to change a plan in the setting of hierarchical task network planning and investigate their computational complexity. On the one hand, these results provide guidelines when constructing algorithms to execute the respective requests, but also provide translations to other well-known planning queries like plan existence or verification. These can be employed to extend an existing planner such that it can form the foundation of a mixed-initiative planning system simply by adding a translation layer on top.

Hierarchical Task Network (HTN) planning is a formalism that can express constraints which cannot easily be expressed by classical (non-hierarchical) planning approaches. It enables reasoning about procedural structures and domain-specific search control knowledge. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because it is not clear how to estimate the goal distance for a partially-ordered task network. When using SHOP2-style progression, a task network of yet unprocessed tasks is maintained during search. In the general case it can grow arbitrarily large. However, many — if not most — existing HTN domains have a certain structure (called tail-recursive) where the network's size is bounded. We show how this bound can be calculated and exploited to automatically translate tail-recursive HTN problems into non-hierarchical STRIPS representations, which allows using both hierarchical structures and classical planning heuristics. In principle, the approach can also be applied to non-tail-recursive HTNs by incrementally increasing the bound. We give three translations with different advantages and present the results of an empirical evaluation with several HTN domains that are translated to PDDL and solved by two current classical planning systems. Our results show that we can automatically find practical bounds for solving partially-ordered HTN problems. We also show that classical planners perform similarly with our automatic translations versus a previous hand-bounded HTN translation which is restricted to totally-ordered problems.

This article, co-authored by Harvey Lewis, research director at Deloitte UK, unveils the possibilities presented by artificial intelligence. In the 2015 film, "Ex Machina", the character Nathan Bateman, an archetypal eccentric billionaire, suggests that "one day the AIs are going to look back on us the same way we look at fossil skeletons on the plains of Africa. An upright ape living in dust with crude language and tools, all set for extinction." Given the surge of interest in artificial intelligence (AI) in recent years, fueled by big data and ever more sophisticated algorithms and hardware, it should come as no surprise that famous entrepreneurs and even eminent scientists in the real world are asking whether computers could one day threaten the survival of humankind. Governments and businesses around the world are continuing to invest billions of pounds in the technology.

It's one thing to keep robots from crashing into fixed obstacles like walls or furniture, but preventing collisions with other moving things is a much tougher challenge. Targeting teams of robots working together, MIT on Thursday announced a new algorithm that helps robots avoid moving objects. Planning algorithms for robot teams can be centralized, in which a single computer makes decisions for the whole team, or decentralized, in which each robot makes its own decisions. The latter approach is much better in terms of incorporating local observations, but it's also much trickier, since each robot must essentially guess what the others are going to do. MIT's new algorithm takes a decentralized approach and factors in not just stationary obstacles but also moving ones.

George Osborne has said contingency planning is taking place to anticipate the likely impact on the UK's financial stability of a vote to leave the EU. The chancellor told MPs there would be a "number of impacts" on the financial system that would have to be addressed. Economists have warned of market volatility and a sharp fall in sterling should there be a Leave vote. The chancellor said it would be up to the Bank of England to consider appropriate monetary responses. Mr Osborne, a key figure in the Remain campaign, has previously refused to be drawn on whether the Treasury and other public bodies were, in any way, preparing for the possibility of a Leave vote in the referendum on 23 June.

The proposal behind this paper is the introduction of a new agent denominated Go-Ahead: this is an automatic Go player that uses a new technique in order to improve the accuracy of the pre estimated values of the moves that are candidates to be introduced into the classical Monte Carlo tree search (MCTS) algorithm which is used by many of the current top agents for Go. Go-Ahead is built upon the framework of one of these agents: the well known open source automatic player Fuego, in which these pre estimated values are obtained by means of a heuristic called prior knowledge. Go-Ahead copes with the task of refining the calculations of these values through a new technique that performs a balanced combination between the prior knowledge heuristic and some relevant information retrieved from the numerous play out simulation phases that are repeatedly executed throughout the Monte Carlo search. With such a strategy, Go-Ahead provides the contribution of enhancing the MCTS process of choosing appropriate moves. Further, this new approach attenuates the supervision level inherent to this process due to the following fact: it allows for the lessening of the impact of the prior knowledge heuris- tics through strengthening the impact of play out information. The results obtained in tournaments against Fuego confirm the benefits and the contributions provided by this approach.

Improved collaboration techniques for tasks executed collectively by multiple agents can lead to increased amount of information available to the agents, increased efficiency of resource utilization, reduced interference among the agents, and faster task completion. An example of a multiagent task that benefits from collaboration is Collective Transport with Obstacle Avoidance: the task of multiple agents jointly moving an object while navigating around obstacles. We propose a new approach to sharing and aggregation of information among the transporting agents that entails (1) considering all available information instead of only their own most pressing concerns through establishing objectively valued system needs and (2) being persuadable instead of stubborn, through assessing how these needs compare to the needs established by their peers. Our system extends and improves upon the work in (Ferrante et al. 2013), leading to better informed agents making efficient decisions that cause less inter-agent interference and lead to faster and more reliable completion of the collective task.