Contingent Planning via an Action-Selection Mechanism

Planning under partial observability is the general case of automatic planning, where only part of the domain information is available at run-time. This formulation of planning is the one that reflects more the real non-deterministic behaviour of a dynamic domain; however, it is also the most complex and demanding planning task.
There are many problems involving sensing actions and incomplete information whose solutions have exponential size. To deal with this problem, we develop a domain-indipendent contingent planner that is heuristics driven and that selects the next-to-apply action in a closed-loop fashion. In that way, it is useless to produce a whole contingent plan to solve a problem: a sequence of actions, interleaving planning/action selection and execution, is enough to reach the goal. This action selection mechanism, to be effective, has to choose the actions in a fast and goal-directed way. It is what we do by using an informed heuristics that uses classical planning to propose a fast solution to a given problem.

 
 

Safe Assumption-Based Planning

A large number of relevant planning problems require the ability to deal with partially observable, non-deterministic domain models. Using assumptions (i.e. expected or nominal domain behaviours) to restrict the search is a well-known approach to alleviate the high complexity of planning problems, focusing the search on expected domain behaviours.
Assumptions may not hold at run-time; for this reason, assumption-based plans are usually executed within a reactive framework, where an external monitor of the execution observes the responses of the domain to the actions, and triggers replanning when such observations are not compatible with the expected behaviour. However this could not be enought, because unnecessary replanning may take place when, due to incomplete knowledge on the domain status at execution time, the monitor cannot distinguish between an acceptable domain behaviour and an unacceptable one.

To effectively deal with complex planning problems for partial observable and non-deterministic domains, we define safe assumption-based solution plans as those solution plans built under assumption that guarantee that any successful execution is observationally distinguishable from any unsuccessful execution.
Safe plans inhibit unnecessary replanning episodes caused by an incomplete knowledge on the domain status at execution time. The notion of safety is lifted to deal with assumptions expressed in Linear Temporal Logic (LTL).

 
 

Bounded Reasoning

Memory bounds may limit the ability of a reasoner to make inferences and therefore affect the reasoner's usefulness. We propose a framework to automatically verify the reasoning capabilities of propositional memory-bounded reasoners which have a sequential architecture.
Given a problem (goal formula) and a reasoner, we represent the reasoner as a state transition system and use the model-based planner MBP to check whether the reasoner has sufficient resources to solve the problem (derive the formula). Our framework explicitly accounts for the use of memory both to store facts and to support backtracking in the course of deductions. Proof existence is recast as a strong planning problem; the results of experiments using the MBP planner indicate that memory bounds may not be trivial to infer even for simple problems, and that memory bounds and length of derivations are closely interrelated.

 
 

Robotic Navigation & Localisation

Robotic navigation problem, given their reliance on sensors and actuators that have a limited precision, involves the challenge of developing efficient robot localization processes, on the one hand, and integrating them with goal-driven behaviours on the other hand. Current approaches for this integration consider localization behaviours and goal-driven behaviours as two separate interleaved processes. This can lead to suboptimal or even failing robot behaviours, where decision choices made by one process negatively interfere with those made by the other, and where serendipitous situations created by one process are not exploited by the other.
On top of this, a robotics architecture have to evolve into domains with an high level of unknown. This means that the planning has to deal with complex nondeterministic and partial observable domains.

We propose a new idea for integrating localization and goal-driven behaviours that considers requirements for both types of behaviours as an integrated specification for a planning process. Sensory-activated and goal-driven plans are generated by applying a planning method that handles partially observable nondeterminisitc domains. This is obtained by a framework that integrates, within a behavioural robotic architecture, a planner providing strong solution plans for nondeterministic and partially observable domains (i.e. plans that achieve the goal whatever the initial uncertainty about the domain is).