Till Örebro universitet

Modern lightweight dual-arm robots bring the physical capabilities to quickly take over tasks at typical industrial workplaces designed for workers. Low setup times - including the instructing/specifying of new tasks - are crucial to stay competitive. We propose a constraint programming approach to simultaneous task allocation and motion scheduling for such industrial manipulation and assembly tasks. Our approach covers the robot as well as connected machines. The key concept are Ordered Visiting Constraints, a descriptive and extensible model to specify such tasks with their spatiotemporal requirements and combinatorial or ordering constraints. Our solver integrates such task models and robot motion models into constraint optimization problems and solves them efficiently using various heuristics to produce makespan-optimized robot programs. For large manipulation tasks with 200 objects, our solver implemented using Google's Operations Research tools requires less than a minute to compute usable plans. The proposed task model is robot-independent and can easily be deployed to other robotic platforms. This portability is validated through several simulation-based experiments.

“Bioshotcrete” is a new technology being developed by a team of robotic experts, architects, engineers, and drones’ specialists, aiming at using drones in the construction industry to spray natural materials over a temporary light formwork until a self-standing shell is completed. This technique consists in projecting paste-like matter composed of clay mixes following precise and customized deposition sequences over a temporary formwork, incorporating computational techniques in the design and fabrication stages, therefore proposing a more sustainable version of shotcrete. In particular, this paper features experiments using drones for spraying wet and dry ranges of clay mixes over a reusable inflatable formwork with the purpose to build monolithic earthen shells. The featured case studies propose specific protocols to control different deposition sequences, describing the proper formulation of clay mixes, the design and production of customized spraying devices, and fitting options in the drone allowing to vary pressure and other drone spraying parameters. The development of Bioshotcrete using robotic fabrication strategies could help expand and transform existing construction methods and processes to be applied at large scale, therefore incorporating innovative digital fabrication protocols towards a more sustainable building construction realm.

Robots operating in a complex human-inhabited environment need to represent and reason about different kinds of knowledge, including ontological, spatial, causal, temporal and resource knowledge. Often, these reasoning tasks are not mutually independent, but need to be integrated with each other. Integrated reasoning is especially important when dealing with knowledge derived from perception, which may be intrinsically incomplete or ambiguous. For instance, the non-observable property that a dish has been used and should therefore be washed can be inferred from the observable properties that it was full before and that it is empty now. In this paper, we present a hybrid reasoning framework which allows to easily integrate different kinds of reasoners. We demonstrate the suitability of our approach by integrating two kinds of reasoners, for ontological reasoning and for temporal reasoning, and using them to recognize temporally and ontologically defined object properties in point cloud data captured using an RGB-D camera.

This paper reports on the aims, the approach, and the results of the European project RACE. The project aim was to enhance the behavior of an autonomous robot by having the robot learn from conceptualized experiences of previous performance, based on initial models of the domain and its own actions in it. This paper introduces the general system architecture; it then sketches some results in detail regarding hybrid reasoning and planning used in RACE, and instances of learning from the experiences of real robot task execution. Enhancement of robot competence is operationalized in terms of performance quality and description length of the robot instructions, and such enhancement is shown to result from the RACE system.

The quest of AI and Robotics researchers to realize fully AI-driven integrated robotic systems has not yet led to such realizations, in spite of great attainments in both research areas. This thesis claims that one of the major hindrances to these realizations is the lack of attention to what we call “the hybrid reasoning problem”. This is the problem of jointly reasoning about heterogeneous and inter-dependent aspects of the world, expressed in different forms and at different levels of abstraction.

In this thesis, we propose an approach to hybrid reasoning (or integrated reasoning) for robot applications. Our approach constitutes a systematic way of achieving a domain-specific integration of reasoning capabilities. Its underpinning is to jointly reason about the sub-problems of an overall hybrid problem in the combined search space of mutual decisions. Each sub-problem represents one viewpoint, or type of requirement, that is meaningful in the particular application. We propose a Constraint Satisfaction Problem (CSP) formulation of the hybrid reasoning problem. This CSP, called meta-CSP, captures the dependencies between sub-problems. It constitutes a high-level representation of the (hybrid) requirements that define a particular application. We formalize the meta-CSP in a way that is independent of the viewpoints that are relevant in the application, as is the algorithm used for solving the meta-CSP.

In order to verify the applicability of the meta-CSP approach in real-world robot applications, we instantiate it in several different domains, namely, a waiter robot, an automated industrial fleet management application, and a drill pattern planning problem in open-pit mining. These realizations highlight the important features of the approach, namely, modularity, generality, online reasoning and solution adjustment, and the ability to account for domain-specific metric and symbolic knowledge.

"Women are just not interested'' is a convenient justification for the absence of women in computer science. This paper questions this simplification; it admits that women have not shown considerable interest toward computer science by referring to the relevant statistics and common observations by experts in the field. Second, it analyses several diverse factors that may have led to this lack of interest. This paper also points out the importance of women's involvement in this field, and discusses some possible solutions.

Fleet automation often involves solving several strongly correlated sub-problems, including task allocation, motion planning, and coordination. Solutions need to account for very specific, domaindependent constraints. In addition, several aspects of the overall fleet management problem become known only online. We propose a method for solving the fleet-management problem grounded on a heuristically-guided search in the space of mutually feasible solutions to sub-problems. We focus on a mining application which requires online contingency handling and accommodating many domainspecific constraints. As contingencies occur, efficient reasoning is performed to adjust the plan online for the entire fleet.

More and more industrial applications require fleets of autonomous ground vehicles. Today's solutions to the management of these fleets still largely rely on fixed set-ups of the system, manually specified ad-hoc rules. Our aim is to replace current practice with autonomous fleets and fleet management systems that are easily adaptable to new set-ups and environments, can accommodate human-intelligible rules, and guarantee feasible and meaningful behavior of the fleet. We propose to cast the problem of autonomous fleet management to a meta-CSP that integrates task allocation, coordination and motion planning. We discuss design choices of the approach, and how it caters to the need for hybrid reasoning in terms of symbolic, metric, temporal and spatial constraints. We also comment on a preliminary realization of the system.

We present a novel modelling and planning approach for multi-robot systems under uncertain travel times. The approach uses generalised stochastic Petri nets (GSPNs) to model desired team behaviour, and allows to specify safety constraints and rewards. The GSPN is interpreted as a Markov decision process (MDP) for which we can generate policies that optimise the requirements. This representation is more compact than the equivalent multi-agent MDP, allowing us to scale better. Furthermore, it naturally allows for asynchronous execution of the generated policies across the robots, yielding smoother team behaviour. We also describe how the integration of the GSPN with a lower-level team controller allows for accurate expectations on team performance. We evaluate our approach on an industrial scenario, showing that it outperforms hand-crafted policies used in current practice.

We introduce a variant of the multi-vehicle routing problem which accounts for nonholonomic constraints and dense, dynamic obstacles, called MVRP-DDO. The problem is strongly motivated by an industrial mining application. This paper illustrates how MVRP-DDO relates to other extensions of the vehicle routing problem. We provide an application-independent formulation of MVRP-DDO, as well as a concrete instantiation in a surface mining application. We propose a multi-abstraction search approach to compute an executable plan for the drilling operations of several machines in a very constrained environment. The approach is evaluated in terms of makespan and computation time, both of which are hard industrial requirements.

An important contribution of AI to Robotics is the model-centred approach, whereby competent robot behaviour stems from automated reasoning in models of the world which can be changed to suit different environments, physical capabilities and tasks. However models need to capture diverse (and often application-dependent) aspects of the robot's environment and capabilities. They must also have good computational properties, as robots need to reason while they act in response to perceived context. In this article, we investigate the use of a meta-CSP-based technique to interleave reasoning in diverse knowledge types. We reify the approach through a robotic waiter case study, for which a particular selection of spatial, temporal, resource and action KR formalisms is made. Using this case study, we discuss general principles pertaining to the selection of appropriate KR formalisms and jointly reasoning about them. The resulting integration is evaluated both formally and experimentally on real and simulated robotic platforms.

In order to close the sense-plan-act loop, a robotrequires several capabilities: it must match perceived contextwith general knowledge about the environment, instantiateplans into the metric space of the real world, and detectand react to contingencies. All of these capabilities includesome form of spatial reasoning — however, at different levelsof abstraction. Perception generates metric spatial knowledge,while general knowledge about the environment is often quali-tative in nature. Similarly, plans may call for the achievementof qualitative spatial relations, but actions must be preciselyinstantiated in metric space. This paper focuses on integratingqualitative and metric spatial reasoning for closing the looparound perception and actuation. We propose a knowledgerepresentation and reasoning technique, grounded on well-established spatial calculi, for combining qualitative and metricknowledge and obtaining solutions expressed in actionablemetric terms.

In this paper we present ongoing work on integrating qualitative andmetric spatial reasoning into planning for robots. We propose a knowledge repre-sentation and reasoning technique, grounded on well-established constraint-basedspatial calculi, for combining qualitative and metric knowledge and obtainingplans expressed in actionable metric terms.

AI-based solutions for robot planning have so farfocused on very high-level abstractions of robot capabilitiesand of the environment in which they operate. However, tobe useful in a robotic context, the model provided to an AIplanner should afford both symbolic and metric constructs;its expressiveness should not hinder computational efficiency;and it should include causal, spatial, temporal and resourceaspects of the domain. We propose a planner grounded onwell-founded constraint-based calculi that adhere to theserequirements. A proof of completeness is provided, and theflexibility and portability of the approach is validated throughseveral experiments on real and simulated robot platforms.

Timelines allow to represent temporally-rich informa-tion about plans as well as the current execution statusof plans. Recent work has addressed the related issueof inferring timelines representing contextual informa-tion — often useful for informing planning and/or planexecution monitoring processes. The present article ad-dresses the particular issue of inferring context fromgiven models of how observations relate to context,and representing this context on timelines. We strive toabandon assumptions currently made on context recog-nition, namely that hypotheses are either confirmed ordisproved. We propose a technique which allows to ac-cept the inferred context on a timeline with a degree ofpossibility. The approach is based on fuzzy constraintreasoning, and captures two sources of uncertainty: un-certainty in the model that is used to infer context, anduncertainty in the observations. We also formulate theproblem of searching for the most likely timeline as aConstraint Optimization Problem.

Combined Task and Motion Planning (TAMP) is an area where no one-fits-all solution can exist. Many aspects of the domain, as well as operational requirements, have an effect on how algorithms and representations are designed. Frequently, trade-offs have to be madet o build a system that is effective. We propose five research questions that we believe need to be answered to solve real-world problems that involve combined TAMP. We show which decisions and trade-offs should be made with respect to these research questions, and illustrate these on examples of existing application domains. By doing so, this article aims to provide a guideline for designing combined TAMP solutions that are adequate and effective in the target scenario.

Deploying fleets of autonomous robots in real-world applications requires addressing three problems: motion planning, coordination, and control. Application-specific features of the environment and robots often narrow down the possible motion planning and control methods that can be used. This paper proposes a lightweight coordination method that implements a high-level controller for a fleet of potentially heterogeneous robots. Very few assumptions are made on robot controllers, which are required only to be able to accept set point updates and to report their current state. The approach can be used with any motion planning method for computing kinematically-feasible paths. Coordination uses heuristics to update priorities while robots are in motion, and a simple model of robot dynamics to guarantee dynamic feasibility. The approach avoids a priori discretization of the environment or of robot paths, allowing robots to “follow each other” through critical sections. We validate the method formally and experimentally with different motion planners and robot controllers, in simulation and with real robots.

This paper is concerned with automating fleets of autonomous robots. This involves solving a multitude of problems, including goal assignment, motion planning, and coordination, while maximizing some performance criterion. While methods for solving these sub-problems have been studied, they address only a facet of the overall problem, and make strong assumptions on the use-case, on the environment, or on the robots in the fleet. In this paper, we formulate the overall fleet management problem in terms of Optimal Control. We describe a scheme for solving this problem in the particular case of fleets of non-holonomic robots navigating in an environment with obstacles. The method is based on a two-phase approach, whereby the first phase solves for fleet-wide boolean decision variables via Mixed Integer Quadratic Programming, and the second phase solves for real-valued variables to obtain an optimized set of trajectories for the fleet. Examples showcasing the features of the method are illustrated, and the method is validated experimentally.

This paper deals with the problem of allocating goals to multiple robots with complex dynamics while computing obstacle-free motions to reach those goals. The spectrum of existing methods ranges from complete and optimal approaches with poor scalability, to highly scalable methods which make unrealistic assumptions on the robots and/or environment. We overcome these limitations by using an efficient graph-based method for decomposing the problem into sub-problems. In particular, we reduce the problem to a Minimum-Cost Max-Flow problem whose solution is used by a multi-robot motion planner that does not impose restrictive assumptions on robot kinodynamics or on the environment. We show empirically that our approach scales to tens of robots in environments composed of hundreds of polygons.

This paper addresses the problem of automating fleets of robots with non-holonomic dynamics. Previously studied methods either specialize in facets of this problem, that is, one or a combination of multi-robot goal allocation, motion planning, and coordination, and typically acrifice optimality and completeness for scalability. We propose an approach that constructs an abstract multi-robot roadmap in a reduced configuration space, where we account for environment connectivity and interference cost between robots occupying the same polygons. Querying the road-map results in a robot-goal assignment and abstract multi-robot trajectory. This is then exploited to de-compose the original problem into smaller problems, each of which is solved with a multi-robot motion planner that accounts for kinodynamic constraints. We validate the approach experimentally to demonstrate the advantage of considering task assignment and motion planning holistically, and explore some methods for balancing solution quality and computational efficiency.

Planning with diverse knowledge, i.e., hybrid planning, is essential for robotic applications. However, powerful heuristics are needed to reason efficiently in the resulting large search spaces. HTN planning provides a means to reduce the search space; furthermore, meta-CSP search has shown promise in hybrid domains, both wrt. search and online plan adaptation. In this paper we combine the two approaches by implementing HTN-style task decomposition as a meta-constraint in a meta-CSP search, resulting in an HTN planner able to handle very rich domain knowledge. The planner produces partial-order plans and if several goal tasks are given, subtasks can be shared, leading to shorter plans. We demonstrate the straightforward integration of different kinds of knowledge for causal, temporal and resource knowledge as well as knowledge provided by an external path planner. The resulting online planner, CHIMP, is integrated in a plan-based robot control system and is demonstrated to physically guide a PR2 robot.

Plan-based robot control has to consider a multitude of aspects of tasks at once, such as task dependency, time, space, and resource usage. Hybrid planning is a strategy for treating them jointly. However, by incorporating all these aspects into a hybrid planner, its search space is huge by construction. This paper introduces the planner CHIMP, which is based on meta-CSP planning to represent the hybrid plan space and uses hierarchical planning as the strategy for cutting efficiently through this space. The paper makes two contributions: First, it describes how HTN planning is integrated into meta-CSP reasoning leading to a planner that can reason about different forms of knowledge and that is fast enough to be used on a robot. Second, it demonstrates CHIMP’s task merging capabilities, i.e., the unification of different tasks from different plan parts, resulting in plans that are more efficient to execute. It also allows to merge new tasks online into a plan that is being executed. This is demonstrated on a PR2 robot.