Monthly Archives: March 2015

You are browsing the site archives by month.

Survey of Hierarchical Task Planning

Ilche Georgievski, Marco Aiello, 2015, HTN planning: Overview, comparison, and beyond, Artificial Intelligence, Volume 222, May 2015, Pages 124-156, ISSN 0004-3702, DOI: 10.1016/j.artint.2015.02.002.

Hierarchies are one of the most common structures used to understand and conceptualise the world. Within the field of Artificial Intelligence (AI) planning, which deals with the automation of world-relevant problems, Hierarchical Task Network (HTN) planning is the branch that represents and handles hierarchies. In particular, the requirement for rich domain knowledge to characterise the world enables HTN planning to be very useful, and also to perform well. However, the history of almost 40 years obfuscates the current understanding of HTN planning in terms of accomplishments, planning models, similarities and differences among hierarchical planners, and its current and objective image. On top of these issues, the ability of hierarchical planning to truly cope with the requirements of real-world applications has been often questioned. As a remedy, we propose a framework-based approach where we first provide a basis for defining different formal models of hierarchical planning, and define two models that comprise a large portion of HTN planners. Second, we provide a set of concepts that helps in interpreting HTN planners from the aspect of their search space. Then, we analyse and compare the planners based on a variety of properties organised in five segments, namely domain authoring, expressiveness, competence, computation and applicability. Furthermore, we select Web service composition as a real-world and current application, and classify and compare the approaches that employ HTN planning to solve the problem of service composition. Finally, we conclude with our findings and present directions for future work. In summary, we provide a novel and comprehensive viewpoint on a core AI planning technique.

On the process of the brain for detecting similarities, with a proposal for its structure and its timing

Qingfei Chen, Xiuling Liang, Peng Li, Chun Ye, Fuhong Li, Yi Lei, Hong Li, 2015, The processing of perceptual similarity with different features or spatial relations as revealed by P2/P300 amplitude, International Journal of Psychophysiology, Volume 95, Issue 3, March 2015, Pages 379-387, ISSN 0167-8760, DOI: 10.1016/j.ijpsycho.2015.01.009.

Visual features such as “color” and spatial relations such as “above” or “beside” have complex effects on similarity and difference judgments. We examined the relative impact of features and spatial relations on similarity and difference judgments via ERPs in an S1–S2 paradigm. Subjects were required to compare a remembered geometric shape (S1) with a second one (S2), and made a “high” or “low” judgment of either similarity or difference in separate blocks of trials. We found three main differences that suggest that the processing of features and spatial relations engages distinct neural processes. The first difference is a P2 effect in fronto-central regions which is sensitive to the presence of a feature difference. The second difference is a P300 in centro-parietal regions that is larger for difference judgments than for similarity judgments. Finally, the P300 effect elicited by feature differences was larger relative to spatial relation differences. These results supported the view that similarity judgments involve structural alignment rather than simple feature and relation matches, and furthermore, indicate the similarity judgment could be divided into three phases: feature or relation comparison (P2), structural alignment (P3 at 300–400 ms), and categorization (P3 at 450–550 ms).

On the role of emotions in cognition, in particular in cognitive control

Michael Inzlicht, Bruce D. Bartholow, Jacob B. Hirsh, 2015, Emotional foundations of cognitive control, Trends in Cognitive Sciences, Volume 19, Issue 3, March 2015, Pages 126-132, DOI: 10.1016/j.tics.2015.01.004.

Often seen as the paragon of higher cognition, here we suggest that cognitive control is dependent on emotion. Rather than asking whether control is influenced by emotion, we ask whether control itself can be understood as an emotional process. Reviewing converging evidence from cybernetics, animal research, cognitive neuroscience, and social and personality psychology, we suggest that cognitive control is initiated when goal conflicts evoke phasic changes to emotional primitives that both focus attention on the presence of goal conflicts and energize conflict resolution to support goal-directed behavior. Critically, we propose that emotion is not an inert byproduct of conflict but is instrumental in recruiting control. Appreciating the emotional foundations of control leads to testable predictions that can spur future research.

On the not-so-domain-generic nature of statistical learning in the human brain

Ram Frost, Blair C. Armstrong, Noam Siegelman, Morten H. Christiansen, 2015, Domain generality versus modality specificity: the paradox of statistical learning, Trends in Cognitive Sciences, Volume 19, Issue 3, March 2015, Pages 117-125, DOI: 10.1016/j.tics.2014.12.010.

Statistical learning (SL) is typically considered to be a domain-general mechanism by which cognitive systems discover the underlying distributional properties of the input. However, recent studies examining whether there are commonalities in the learning of distributional information across different domains or modalities consistently reveal modality and stimulus specificity. Therefore, important questions are how and why a hypothesized domain-general learning mechanism systematically produces such effects. Here, we offer a theoretical framework according to which SL is not a unitary mechanism, but a set of domain-general computational principles that operate in different modalities and, therefore, are subject to the specific constraints characteristic of their respective brain regions. This framework offers testable predictions and we discuss its computational and neurobiological plausibility.

Automatic synthetis of controllers for robotic tasks from the specification of state-machine-like missions, nonlinear models of the robot and a representation of the robot workspace

Jonathan A. DeCastro and Hadas Kress-Gazit, 2015, Synthesis of nonlinear continuous controllers for verifiably correct high-level, reactive behaviors, The International Journal of Robotics Research, 34: 378-394, DOI: 10.1177/0278364914557736.

Planning robotic missions in environments shared by humans involves designing controllers that are reactive to the environment yet able to fulfill a complex high-level task. This paper introduces a new method for designing low-level controllers for nonlinear robotic platforms based on a discrete-state high-level controller encoding the behaviors of a reactive task specification. We build our method upon a new type of trajectory constraint which we introduce in this paper, reactive composition, to provide the guarantee that any high-level reactive behavior may be fulfilled at any moment during the continuous execution. We generate pre-computed motion controllers in a piecewise manner by adopting a sample-based synthesis method that associates a certificate of invariance with each controller in the sample set. As a demonstration of our approach, we simulate different robotic platforms executing complex tasks in a variety of environments.

A nice review of the problem of kinematic modeling of wheeled mobile robots and a new approach that delays the use of coordinate frames

Alonzo Kelly and Neal Seegmiller, 2015, Recursive kinematic propagation for wheeled mobile robots, The International Journal of Robotics Research, 34: 288-313, DOI: 10.1177/0278364914551773.

The problem of wheeled mobile robot kinematics is formulated using the transport theorem of vector algebra. Doing so postpones the introduction of coordinates until after the expressions for the relevant Jacobians have been derived. This approach simplifies the derivation while also providing the solution to the general case in 3D, including motion over rolling terrain. Angular velocity remains explicit rather than encoded as the time derivative of a rotation matrix. The equations are derived and can be implemented recursively using a single equation that applies to all cases. Acceleration kinematics are uniquely derivable in reasonable effort. The recursive formulation also leads to efficient computer implementations that reflect the modularity of real mechanisms.

Interesting and gentle introduction to WCET analysis and synchronous design for hard real-time systems

Pascal Raymond, Claire Maiza, Catherine Parent-Vigouroux, Fabienne Carrier, Mihail Asavoae, 2015, Timing analysis enhancement for synchronous program, Real-Time Systems, Volume 51, Issue 2, pp 192-220, DOI: 10.1007/s11241-015-9219-y.

Real-time critical systems can be considered as correct if they compute both right and fast enough. Functionality aspects (computing right) can be addressed using high level design methods, such as the synchronous approach that provides languages, compilers and verification tools. Real-time aspects (computing fast enough) can be addressed with static timing analysis, that aims at discovering safe bounds on the worst-case execution time (WCET) of the binary code. In this paper, we aim at improving the estimated WCET in the case where the binary code comes from a high-level synchronous design. The key idea is that some high-level functional properties may imply that some execution paths of the binary code are actually infeasible, and thus, can be removed from the worst-case candidates. In order to automatize the method, we show (1) how to trace semantic information between the high-level design and the executable code, (2) how to use a model-checker to prove infeasibility of some execution paths, and (3) how to integrate such infeasibility information into an existing timing analysis framework. Based on a realistic example, we show that there is a large possible improvement for a reasonable computation time overhead.

A survey of semantic mapping for mobile robots

Ioannis Kostavelis, Antonios Gasteratos, 2015, Semantic mapping for mobile robotics tasks: A survey, Robotics and Autonomous Systems, Volume 66, April 2015, Pages 86-103, ISSN 0921-8890, DOI: 10.1016/j.robot.2014.12.006.

The evolution of contemporary mobile robotics has given thrust to a series of additional conjunct technologies. Of such is the semantic mapping, which provides an abstraction of space and a means for human\u2013robot communication. The recent introduction and evolution of semantic mapping motivated this survey, in which an explicit analysis of the existing methods is sought. The several algorithms are categorized according to their primary characteristics, namely scalability, inference model, temporal coherence and topological map usage. The applications involving semantic maps are also outlined in the work at hand, emphasizing on human interaction, knowledge representation and planning. The existence of publicly available validation datasets and benchmarking, suitable for the evaluation of semantic mapping techniques is also discussed in detail. Last, an attempt to address open issues and questions is also made.