Planning & Scheduling: Overviews


A Review on Learning Planning Action Models for Socio-Communicative HRI

arXiv.org Artificial Intelligence

For social robots to be brought more into widespread use in the fields of companionship, care taking and domestic help, they must be capable of demonstrating social intelligence. In order to be acceptable, they must exhibit socio-communicative skills. Classic approaches to program HRI from observed human-human interactions fails to capture the subtlety of multimodal interactions as well as the key structural differences between robots and humans. The former arises due to a difficulty in quantifying and coding multimodal behaviours, while the latter due to a difference of the degrees of liberty between a robot and a human. However, the notion of reverse engineering from multimodal HRI traces to learn the underlying behavioral blueprint of the robot given multimodal traces seems an option worth exploring. With this spirit, the entire HRI can be seen as a sequence of exchanges of speech acts between the robot and human, each act treated as an action, bearing in mind that the entire sequence is goal-driven. Thus, this entire interaction can be treated as a sequence of actions propelling the interaction from its initial to goal state, also known as a plan in the domain of AI planning. In the same domain, this action sequence that stems from plan execution can be represented as a trace. AI techniques, such as machine learning, can be used to learn behavioral models (also known as symbolic action models in AI), intended to be reusable for AI planning, from the aforementioned multimodal traces. This article reviews recent machine learning techniques for learning planning action models which can be applied to the field of HRI with the intent of rendering robots as socio-communicative.


A Framework for Robot Programming in Cobotic Environments: First user experiments

arXiv.org Artificial Intelligence

The increasing presence of robots in industries has not gone unnoticed. Large industrial players have incorporated them into their production lines, but smaller companies hesitate due to high initial costs and the lack of programming expertise. In this work we introduce a framework that combines two disciplines, Programming by Demonstration and Automated Planning, to allow users without any programming knowledge to program a robot. The user teaches the robot atomic actions together with their semantic meaning and represents them in terms of preconditions and effects. Using these atomic actions the robot can generate action sequences autonomously to reach any goal given by the user. We evaluated the usability of our framework in terms of user experiments with a Baxter Research Robot and showed that it is well-adapted to users without any programming experience.


Towards Providing Explanations for AI Planner Decisions

arXiv.org Artificial Intelligence

In order to engender trust in AI, humans must understand what an AI system is trying to achieve, and why. To overcome this problem, the underlying AI process must produce justifications and explanations that are both transparent and comprehensible to the user. AI Planning is well placed to be able to address this challenge. In this paper we present a methodology to provide initial explanations for the decisions made by the planner. Explanations are created by allowing the user to suggest alternative actions in plans and then compare the resulting plans with the one found by the planner. The methodology is implemented in the new XAI-Plan framework.


Decentralized Cooperative Planning for Automated Vehicles with Continuous Monte Carlo Tree Search

arXiv.org Artificial Intelligence

Urban traffic scenarios often require a high degree of cooperation between traffic participants to ensure safety and efficiency. Observing the behavior of others, humans infer whether or not others are cooperating. This work aims to extend the capabilities of automated vehicles, enabling them to cooperate implicitly in heterogeneous environments. Continuous actions allow for arbitrary trajectories and hence are applicable to a much wider class of problems than existing cooperative approaches with discrete action spaces. Based on cooperative modeling of other agents, Monte Carlo Tree Search (MCTS) in conjunction with Decoupled-UCT evaluates the action-values of each agent in a cooperative and decentralized way, respecting the interdependence of actions among traffic participants. The extension to continuous action spaces is addressed by incorporating novel MCTS-specific enhancements for efficient search space exploration. The proposed algorithm is evaluated under different scenarios, showing that the algorithm is able to achieve effective cooperative planning and generate solutions egocentric planning fails to identify.


The reactive multiple operating room surgical case sequencing problem

arXiv.org Artificial Intelligence

In this paper we consider the surgical case sequencing problem (SCSP) under stochastic conditions. In addition to implementing a robust surgical schedule, we investigate the use of a number of reactive strategies that can be used to maintain schedule feasibility. We present a mixed integer nonlinear programming (MINLP) model for the reactive multiple operating room (OR) SCSP that may be suitable for direct implementation on small problem instances. A machine scheduling perspective is considered and the model is equivalent to a resource-constrained parallel-machine scheduling problem with identical machines, machine eligibility restrictions, and machine and job release dates. The explicit objective of the model is to reduce OR idle time, although other common objectives (including time to surgery and overtime) are discussed. The work here is based on a case study of a large Australian public hospital with long surgical waiting lists and high non-elective demand. Results of computational experiments show that the reactive strategies presented in this paper can be used to reduce idle time without putting excessive pressure on surgeons.


The real-time reactive surgical case sequencing problem

arXiv.org Artificial Intelligence

In this paper, the multiple operating room (OR) surgical case sequencing problem (SCSP) is addressed. The objective is to maximise total OR utilisation during standard opening hours. The work here is based on a case study of a large Australian public hospital with long surgical waiting lists and high levels of non-elective demand. Due to the complexity of the SCSP and the size of the instances considered herein, heuristic techniques are required to solve the problem. Constructive heuristics are presented based on both a modified block scheduling policy and an open scheduling policy. A number of real-time reactive strategies are presented that can be used to maintain schedule feasibility in the case of disruptions. Results of computational experiments show that the approach presented in this paper can be used to maintain schedule feasibility in real-time, whilst increasing OT utilisation and throughput, and reducing the waiting time of non-elective patients. The framework presented here is applicable to the real-life scheduling of OT departments, and recommendations have been provided regarding implementation of the approach.


Compact Policies for Fully-Observable Non-Deterministic Planning as SAT

arXiv.org Artificial Intelligence

Fully observable non-deterministic (FOND) planning is becoming increasingly important as an approach for computing proper policies in probabilistic planning, extended temporal plans in LTL planning, and general plans in generalized planning. In this work, we introduce a SAT encoding for FOND planning that is compact and can produce compact strong cyclic policies. Simple variations of the encodings are also introduced for strong planning and for what we call, dual FOND planning, where some non-deterministic actions are assumed to be fair (e.g., probabilistic) and others unfair (e.g., adversarial). The resulting FOND planners are compared empirically with existing planners over existing and new benchmarks. The notion of "probabilistic interesting problems" is also revisited to yield a more comprehensive picture of the strengths and limitations of current FOND planners and the proposed SAT approach.


Compact Policies for Fully Observable Non-Deterministic Planning as SAT

AAAI Conferences

Fully observable non-deterministic (FOND) planning is becoming increasingly important as an approach for computing proper policies in probabilistic planning, extended temporal plans in LTL planning, and general plans in generalized planning. In this work, we introduce a SAT encoding for FOND planning that is compact and can produce compact strong cyclic policies. Simple variations of the encodings are also introduced for strong planning and for what we call, dual FOND planning, where some non-deterministic actions are assumed to be fair (e.g., probabilistic) and others unfair (e.g., adversarial). The resulting FOND planners are compared empirically with existing planners over existing and new benchmarks. The notion of ``probabilistic interesting problems'' is also revisited to yield a more comprehensive picture of the strengths and limitations of current FOND planners and the proposed SAT approach.


A Hybrid Genetic Algorithm for Parallel Machine Scheduling at Semiconductor Back-End Production

AAAI Conferences

This paper addresses batch scheduling at a back-end semiconductor plant of Nexperia. This complex manufacturing environment is characterized by a large product and batch size variety, numerous parallel machines with large capacity differences, sequence and machine dependent setup times and machine eligibility constraints. A hybrid genetic algorithm is proposed to improve the scheduling process, the main features of which are a local search enhanced crossover mechanism, two additional fast local search procedures and a user-controlled multi-objective fitness function. Testing with real-life production data shows that this multi-objective approach can strike the desired balance between production time, setup time and tardiness, yielding high-quality practically feasible production schedules.


Monte-Carlo Planning for Agile Legged Locomotion

AAAI Conferences

Recent progress in legged locomotion research has produced robots that can perform agile blind-walking with robustness comparable to a blindfolded human. However, this walking approach has not yet been integrated with planners for high-level activities. In this paper, we take a step towards high-level task planning for these robots by studying a planar simulated biped that captures their essential dynamics. We investigate variants of Monte-Carlo Tree Search (MCTS) for selecting an appropriate blind-walking controller at each decision cycle. In particular, we consider UCT with an intelligently selected rollout policy, which is shown to be capable of guiding the biped through treacherous terrain. In addition, we develop a new MCTS variant, called Monte-Carlo Discrepancy Search (MCDS), which is shown to make more effective use of limited planning time than UCT for this domain. We demonstrate the effectiveness of these planners in both deterministic and stochastic environments across a range of algorithm parameters. In addition, we present results for using these planners to control a full-order 3D simulation of Cassie, an agile bipedal robot, through complex terrain.