A Formal Hybrid Planning Framework for Robotic Manipulation
Esra Erdem, Sabancı University, Istanbul, Turkey
Abstract: Robotic manipulation aims automatic generation of robot motion sequences for manipulation of movable objects among obstacles, to achieve a desired goal configuration. Some of these objects can only move when picked up by robots, and the order of pick-and-place operations for manipulation may matter to obtain a feasible kinematic solution. Therefore, geometric reasoning and motion planning alone are not sufficient to solve these manipulation problems; and planning of actions such as the pick-and-place operations need to be integrated with the motion planning problem. We present a modular framework that combines these two sorts of reasoning, using expressive formalisms and efficient solvers of answer set programming. We illustrate applications of this framework to complex robotic manipulation tasks that require concurrent execution of actions, with both dynamic simulations and physical implementations, using multiple Kuka youBots.
Bio: Esra Erdem is an associate professor in Computer Science and Engineering at Sabanci University. She received her Ph.D. in computer sciences at the University of Texas at Austin (2002), and visited University of Toronto and Vienna University of Technology for postdoctoral research (2002-2006). Her research is in the area of artificial intelligence, in particular, the mathematical foundations of knowledge representation and reasoning, and their applications to cognitive robotics and computational biology.
Abstract: There is a long tradition associating language and other serial cognitive behavior with an underlying motor planning mechanism (Piaget 1936, Lashley 1951, Miller et al. 1960, passim). The evidence is evolutionary, neurophysiological, and developmental. It suggests that language is much more closely related to embodied cognition than current linguistic theories of grammar suggest.
I'll argue that practically every aspect of language reflects this connection transparently. Building on planning formalisms developed in Robotics and AI, with some attention to applicable machine learning techniques, two basic operation corresponding to seriation and affordance will be shown to provide the basis for both plan-composition in animals, and long-range dependency in human language, of the kind found in constructions like relative clauses and coordination.
A connection this direct raises a further obvious question: If language is so closely related to animal planning, why don't any other animals have language? I'll further argue that the specific requirements of human collaborative planning, involving actions like helping and promising that depend on an understanding of other minds that has been found to be lacking in other animals, provides a distinctively semantic precursor for recursive aspects distinguishing human language from animal communication. I'll show that the automaton that is minimally necessary to conduct search for collaborative plans, which is of only slightly greater generality than the push-down automaton, is exactly the automaton that also appears to characterize the parsing problem for natural languages.
Bio: Mark Steedman is a Professor of Cognitive Science in Informatics at the University of Edinburgh, working in computational linguistics, artificial intelligence, the communicative use of prosody, tense and aspect, and wide-coverage parsing using Combinatory Categorial Grammar (CCG). Prof. Steedman is a Fellow of the Association for the Advancement of Artificial Intelligence (AAAI), the Royal Society of Edinburgh (FRSE), and the British Academy (FBA). He is a member of the Academy of Europe and a former President of the Association for Computational Linguistics (ACL).
Challenges in Temporal Planning for Aggregate Load Management of Household Electricity Demand
Josef Bajada, Maria Fox, and Derek Long
Abstract: Demand response is seen as one of the key mechanisms to manage electricity load in future smart grids. In this paper we present a model which captures the demand-side characteristics of the future power network. These include energy generated from renewable intermittent sources, such as solar panels and wind turbines, flexible demand, that can be controlled through remote actuation capabilities, and availability of electricity storage facilities, such as battery banks and electric vehicles. Automated Planning technology can offer significant benefits in terms of deciding which assets to activate, in which order, and at what time. Limitations of current planning technology to support this domain are subsequently analysed in order to formulate the challenges to be addressed in further research.
Abstract Augmented Lazy Theta*: Applying Graph Abstractions to Trajectory Planning with Speed-Limit Constraints
Peter Gregory and Lukas Chrpa
Abstract: Trajectory planning is a generalisation of path planning in which velocity is also taken into consideration. Considering velocity, in the context of a real-world system such as a robotic vehicle, means considering physical constraints such as the speed limit constraints when steering the vehicle. One of the recent algorithms for solving this type of planning problem is Augmented Lazy Theta*.
In this work we introduce the trajectory planner Abstract Augmented Lazy Theta*. This planner uses a combination of abstraction and relaxation to reduce the search space of Augmented Lazy Theta*. We demonstrate that Abstract Aug- mented Lazy Theta* significantly improves the time performance of Augmented Lazy Theta* whilst retaining the same overall solution quality. Additionally, we show that Abstract Augmented Lazy Theta* performs competitively with another state-of-the-art trajectory planning algorithm, the RRT* algorithm, by demonstrating significantly better overall performance, in terms of both time and quality.
Optimal Motion Planning for Markov Decision Processes with Co-Safe Linear Temporal Logic Specifications
Bruno Lacerda, David Parker, and Nick Hawes
Abstract: We present preliminary work on the application of probabilistic model checking to motion planning for robot systems, using specifications in co-safe linear temporal logic. We describe our approach, implemented with the probabilistic model checker PRISM, illustrate it with a simple simulated example and discuss further extensions and improvements.
Automated Planning for Multi-Objective Machine Tool Calibration: Optimising Makespan and Measurement Uncertainty
Simon Parkinson, Andrew Crampton, Andrew Longstaff, and Peter Gregory
Abstract: The evolution in precision manufacturing has resulted in the requirement to produce and maintain more accurate machine tools. This new requirement coupled with desire to reduce machine tool downtime places emphasis on the calibration procedure during which the machine's capabilities are assessed. Machine tool downtime is significant for manufacturers because the machine will be unavailable for manufacturing use, therefore wasting the manufacturer's time and potentially increasing lead-times for clients. In addition to machine tool downtime, the uncertainty of measurement, due to the schedule of the calibration plan, has significant implications on tolerance conformance, resulting in an increased possibility of false acceptance and rejection of machined parts.
The work presented in this paper is focussed on expanding a developed temporal optimisation model to reduce the uncer- tainty of measurement. Encoding the knowledge in regular PDDL requires the discretization of non-linear, continuous temperature change and implementing the square root function. The implementation shows that not only can domain- independent automated planning reduce machine downtime by 10.6% and the uncertainty of measurement by 59%, it is also possible to optimise both metrics reaching a compromise that is on average 9% worse that the best-known solution for each individual metric.
Abstract: Numeric Timed Initial Fluents are a new feature in PDDL that extends the concept of Timed Initial Literals to numeric fluents. They are particularly useful to model independent functions that change through time and influence the actions to be applied. Although they are very useful to model real world problems, they are not systematically defined in the family of PDDL languages and they are not implemented in any generic PDDL planner, except for POPF and UPMurphi.
In this paper we present different search strategies to improve the search performance of POPF when numeric Timed Initial Fluents are present. We propose two different changes, the first is based on improvements of the heuristic evaluation while the second considers al- ternative search algorithms based on a mixture of Enforced Hill Climbing and Best First Search.
On-the-fly Route Planning for Mono-UAV Surveillance Missions
Michaël Soulignac, François Gaillard, Cédric Dinont, and Gabriel Marchalot
Abstract: This paper addresses the problem of identifying dynamically discovered targets while maintaining the area coverage. This problem is particularly challenging for mono-UAV surveillance missions, because a compromise must be made between detection and identification. That is why we propose POP, an on-the-fly route planning algorithm based on the projection of the targets on a predefined flight pattern. Three enhancements allow the customization of the behavior of POP depending on the context. Simulation results show that POP is able to plan very rapidly routes leading to high detection and identification rates for reasonable sensor ranges and target speeds.
Abstract: In order for an agent or a team of agents to achieve a goal, there is a sequence of state transitions that need to be performed. This sequence of state transitions constitutes a plan. On some occasions multiple ways of achieving the goal may exist. In competitive settings or sabotage scenarios, one may want to prevent or delay an agent or team of agents from achieving a goal; currently, there is little work addressing this issue in the context of agent teams. We argue that plans can be disrupted by preventing particular state transitions from being performed. We propose four algorithms to identify which state transitions should be thwarted such that the achievement of the goal is prevented (total disruption) or delayed (partial disruption). In order to evaluate the performance of our algo- rithms we define disruption (partial and total) and also provide metrics for its measurement. We do acknowledge that the disruptor may not always have an accurate representation of the disruptee's plans. Thus, we perform an experimental analysis to examine the performance of the algorithms when some of the state transitions available to the disruptee are unknown to the disruptor.
Abstract: Many current applications of planning depend on finding high quality solutions. In many cases finding the optimal solution is impractical, but a good estimation of it is required. The quality is evaluated in terms of user defined metric function. This function represent users preferences. We discuss the current state of the art for finding good quality solutions and present a new way of generating high quality plans in response to the change of the metrics using a modified version of relaxed planning graph.
Abstract: The ability of temporal planners to find concurrent plans can potentially be exploited in multiagent planning with concurrent actions. However, in recent years temporal planning has not been very prevalent in the multiagent planning literature. This paper introduces a simple multiagent planning domain (with concurrent interacting actions) and shows how it can be efficiently translated to temporal planning. The performance of a temporal planner (POPF2) is then evaluated and shown to be a useful benchmark for future multiagent approaches.
Abstract: We describe how the initial state representation developed for a socially aware interactive robot is being extended to handle uncertainty. It incorporates the full range of information provided by the input sensors, including multiple possible hypotheses, each with an associated confidence value.
Abstract: Building agents which can learn to act autonomously in the world is an important challenge for artificial intelligence. While autonomous agents often have to operate in noisy, uncertain worlds, current methods to learn action models from agents' experiences typically assume fully deterministic worlds. This paper presents a noise-tolerant approach to learning probabilistic planning operators from experience. Preliminary experiments demonstrate that the approach learns accurate models even if agents' observations are noisy.
Abstract: A robot coexisting with humans must not only be able to perform physical tasks, but must also be able to interact with humans in a socially appropriate manner. We describe an application of planning to task-based social interaction using a robot that must interact with multiple human agents in a simple bartending domain. Extensions to previous work include a new domain supporting planning for group interactions, and reasoning about uncertainty due to automatic speech recognition.
Abstract: This paper considers the problem of egocentric planning in multi-agent, partially observable, communication-denied domains with varying task specifications and unknown teammate characteristics. We present reward-adaptive planning, a novel algorithm combining online Monte-Carlo planning and Inverse Reinforcement Learning for simultaneous reward learning and action selection. Our method efficiently adapts to changing goals and team compositions, without recourse to domain-dependent models, and using only limited computation time. We present preliminary results from a benchmark multi-agent domain, where reward-adaptive planning is shown to outperform a state-of-the-art decentralised planner and an otherwise identical non-adaptive implementation.
Ruth Aylett, Heriot-Watt University, Edinburgh, UK
Andrew Coles, King's College London, UK
Matthew Crosby, University of Edinburgh, UK
Mary Ellen Foster, Heriot-Watt University, Edinburgh, UK
Christopher Geib, Drexel University, Philadelphia, USA
Peter Gregory, Teesside University, Middlesbrough, UK
Derek Long, King's College London, UK
Kira Mourão, University of Edinburgh, UK
Ron Petrick, University of Edinburgh, UK
Ron Petrick, University of Edinburgh, UK
Mary Ellen Foster, Heriot-Watt University, Edinburgh, UK
The organisers would like to thank the Scottish Informatics and Computer Science Alliance (SICSA) and the JAMES project for supporting UK PlanSIG 2013.