Visual Place Recognition (VPR) is a crucial part of mobile robotics and autonomous driving as well as other computer vision tasks. It refers to the process of identifying a place depicted in a query image using only computer vision. At large scale, repetitive structures, weather and illumination changes pose a real challenge, as appearances can drastically change over time. Along with tackling these challenges, an efficient VPR technique must also be practical in real-world scenarios where latency matters. To address this, we introduce MixVPR, a new holistic feature aggregation technique that takes feature maps from pre-trained backbones as a set of global features. Then, it incorporates a global relationship between elements in each feature map in a cascade of feature mixing, eliminating the need for local or pyramidal aggregation as done in NetVLAD or TransVPR. We demonstrate the effectiveness of our technique through extensive experiments on multiple large-scale benchmarks. Our method outperforms all existing techniques by a large margin while having less than half the number of parameters compared to CosPlace and NetVLAD. We achieve a new all-time high recall@1 score of 94.6% on Pitts250k-test, 88.0% on MapillarySLS, and more importantly, 58.4% on Nordland. Finally, our method outperforms two-stage retrieval techniques such as Patch-NetVLAD, TransVPR and SuperGLUE all while being orders of magnitude faster.

Despite the remarkable progress of deep learning models for semantic segmentation, the success of these models is strongly limited by the following aspects: 1) large datasets with pixel-level annotations must be available and 2) training must be performed with all classes simultaneously. Indeed, in incremental learning scenarios, where new classes are added to an existing framework, these models are prone to catastrophic forgetting of previous classes. To address these two limitations, we propose a weakly-supervised mechanism for continual semantic segmentation that can leverage cheap image-level annotations and a novel rehearsal strategy that intertwines the learning of past and new classes. Specifically, we explore two rehearsal technique variants: 1) imprinting past objects on new images and 2) transferring past representations in intermediate features maps. We conduct extensive experiments on Pascal-VOC by varying the proportion of fully- and weakly-supervised data in various setups and show that our contributions consistently improve the mIoU on both past and novel classes. Interestingly, we also observe that models trained with less data in incremental steps sometimes outperform the same architectures trained with more data. We discuss the significance of these results and propose some hypotheses regarding the dynamics between forgetting and learning.

One crucial objective of multi-task learning is to align distributions across tasks so that the information between them can be transferred and shared. However, existing approaches only focused on matching the marginal feature distribution while ignoring the semantic information, which may hinder the learning performance. To address this issue, we propose to leverage the label information in multi-task learning by exploring the semantic conditional relations among tasks. We first theoretically analyze the generalization bound of multi-task learning based on the notion of Jensen-Shannon divergence, which provides new insights into the value of label information in multi-task learning. Our analysis also leads to a concrete algorithm that jointly matches the semantic distribution and controls label distribution divergence. To confirm the effectiveness of the proposed method, we first compare the algorithm with several baselines on some benchmarks and then test the algorithms under label space shift conditions. Empirical results demonstrate that the proposed method could outperform most baselines and achieve state-of-the-art performance, particularly showing the benefits under the label shift conditions.

Few-shot Learning (FSL) aims to classify new concepts from a small number of examples. While there have been an increasing amount of work on few-shot object classification in the last few years, most current approaches are limited to images with only one centered object. On the opposite, humans are able to leverage prior knowledge to quickly learn new concepts, such as semantic relations with contextual elements.Inspired by the concept of contextual learning in educational sciences, we propose to make a step towards adopting this principle in FSL by studying the contribution that context can have in object classification in a low-data regime. To this end, we first propose an approach to perform FSL on images of complex scenes. We develop two plug-and-play modules that can be incorporated into existing FSL methods to enable them to leverage contextual learning. More specifically, these modules are trained to weight the most important context elements while learning a particular concept, and then use this knowledge to ground visual class representations in context semantics. Extensive experiments on Visual Genome and Open Images show the superiority of contextual learning over learning individual objects in isolation.

Multimodal sentiment analysis has recently received an increasing interest. However, most methods have considered that text and image modalities are always available at test time. This assumption is often violated in real environments (e.g. social media) since users do not always publish a text with an image. In this paper we propose a method based on a multitask framework to combine multimodal information when it is available, while being able to handle the cases where a modality is missing. Our model contains one classifier for analyzing the text, another for analyzing the image, and another performing the prediction by fusing both modalities. In addition to offer a solution to the problem of a missing modality, our experiments show that this multitask framework improves generalization by acting as a regularization mechanism. We also demonstrate that the model can handle a missing modality at training time, thus being able to be trained with image-only and text-only examples.

Grasping is a fundamental robotic task needed for the deployment of household robots or furthering warehouse automation. However, few approaches are able to perform grasp detection in real time (frame rate). To this effect, we present Grasp Quality Spatial Transformer Network (GQ-STN), a one-shot grasp detection network. Being based on the Spatial Transformer Network (STN), it produces not only a grasp configuration, but also directly outputs a depth image centered at this configuration. By connecting our architecture to an externally-trained grasp robustness evaluation network, we can train efficiently to satisfy a robustness metric via the backpropagation of the gradient emanating from the evaluation network. This removes the difficulty of training detection networks on sparsely annotated databases, a common issue in grasping. We further propose to use this robustness classifier to compare approaches, being more reliable than the traditional rectangle metric. Our GQ-STN is able to detect robust grasps on the depth images of the Dex-Net 2.0 dataset with 92.4 % accuracy in a single pass of the network. We finally demonstrate in a physical benchmark that our method can propose robust grasps more often than previous sampling-based methods, while being more than 60 times faster.

In this work, we consider the task of classifying binary positive-unlabeled (PU) data. The existing discriminative learning based PU models attempt to seek an optimal reweighting strategy for U data, so that a decent decision boundary can be found. However, given limited P data, the conventional PU models tend to suffer from overfitting when adapted to very flexible deep neural networks. In contrast, we are the first to innovate a totally new paradigm to attack the binary PU task, from perspective of generative learning by leveraging the powerful generative adversarial networks (GAN). Our generative positive-unlabeled (GenPU) framework incorporates an array of discriminators and generators that are endowed with different roles in simultaneously producing positive and negative realistic samples. We provide theoretical analysis to justify that, at equilibrium, GenPU is capable of recovering both positive and negative data distributions. Moreover, we show GenPU is generalizable and closely related to the semi-supervised classification. Given rather limited P data, experiments on both synthetic and real-world dataset demonstrate the effectiveness of our proposed framework. With infinite realistic and diverse sample streams generated from GenPU, a very flexible classifier can then be trained using deep neural networks.

Object recognition is an important task for improving the ability of visual systems to perform complex scene understanding. Recently, the Exponential Linear Unit (ELU) has been proposed as a key component for managing bias shift in Convolutional Neural Networks (CNNs), but defines a parameter that must be set by hand. In this paper, we propose learning a parameterization of ELU in order to learn the proper activation shape at each layer in the CNNs. Our results on the MNIST, CIFAR-10/100 and ImageNet datasets using the NiN, Overfeat, All-CNN and ResNet networks indicate that our proposed Parametric ELU (PELU) has better performances than the non-parametric ELU. We have observed as much as a 7.28% relative error improvement on ImageNet with the NiN network, with only 0.0003% parameter increase. Our visual examination of the non-linear behaviors adopted by Vgg using PELU shows that the network took advantage of the added flexibility by learning different activations at different layers.

In this work, we develop a fast sequential low-rank tensor regression framework, namely recursive higher-order partial least squares (RHOPLS). It addresses the great challenges posed by the limited storage space and fast processing time required by dynamic environments when dealing with large-scale high-speed general tensor sequences. Smartly integrating a low-rank modification strategy of Tucker into a PLS-based framework, we efficiently update the regression coefficients by effectively merging the new data into the previous low-rank approximation of the model at a small-scale factor (feature) level instead of the large raw data (observation) level. Unlike batch models, which require accessing the entire data, RHOPLS conducts a blockwise recursive calculation scheme and thus only a small set of factors is needed to be stored. Our approach is orders of magnitude faster than all other methods while maintaining a highly comparable predictability with the cutting-edge batch methods, as verified on challenging real-life tasks.

Pick-and-place is an important task in robotic manipulation. In industry, template-matching approaches are often used to provide the level of precision required to locate an object to be picked. However, if a robotic workstation is to handle numerous objects, brute-force template-matching becomes expensive, and is subject to notoriously hard-to-tune thresholds. In this paper, we explore the use of Deep Learning methods to speed up traditional methods such as template matching. In particular, we employed a Single Shot Detection (SSD) and a Residual Network (ResNet) for object detection and classification. Classification scores allows the re-ranking of objects so that template matching is performed in order of likelihood. Tests on a dataset containing 10 industrial objects demonstrated the validity of our approach, by getting an average ranking of 1.37 for the object of interest. Moreover, we tested our approach on the standard Pose dataset which contains 15 objects and got an average ranking of 1.99. Because SSD and ResNet operates essentially in constant time in a Graphics Processor Unit, our approach is able to reach near-constant time execution. We also compared the F1scores of LINE-2D, a state-of-the-art template matching method, using different strategies (including our own) and the results show that our method is competitive to a brute-force template matching approach. Coupled with near-constant time execution, it therefore opens up the possibility for performing template matching for databases containing hundreds of objects.

The ability to grasp ordinary and potentially never-seen objects is an important task in both domestic and industrial robotics. For a system to accomplish this, it must autonomously identify grasping locations by using information from various sensors, such as Microsoft Kinect 3D camera. Despite numerous progress, significant work still remains to be done for this task. To this effect, we propose a dictionary learning and sparse representation (DLSR) framework for representing RGBD images from 3D sensors in the context of identifying grasping locations. In contrast to previously proposed approaches that relied on sophisticated regularization or very large datasets, our derived perception system has a fast training phase and can work with small datasets. It is also theoretically founded for dealing with masked-out entries, which are common with 3D sensors. We contribute by presenting a comparative study of several DLSR approach combinations for recognizing and detecting grasp candidates on the standard Cornell dataset. Experimental results show a performance improvement of 1.69% in detection and 3.16% in recognition over current state-of-the-art convolutional neural network (CNN). Even though nowadays most popular vision-based approach is CNN, this suggests that DLSR is also a viable alternative with interesting advantages that CNN has not.

In this work, we introduce a new generalized nonlinear tensor regression framework called kernel-based multiblock tensor partial least squares (KMTPLS) for predicting a set of dependent tensor blocks from a set of independent tensor blocks through the extraction of a small number of common and discriminative latent components. By considering both common and discriminative features, KMTPLS effectively fuses the information from multiple tensorial data sources and unifies the single and multiblock tensor regression scenarios into one general model. Moreover, in contrast to multilinear model, KMTPLS successfully addresses the nonlinear dependencies between multiple response and predictor tensor blocks by combining kernel machines with joint Tucker decomposition, resulting in a significant performance gain in terms of predictability. An efficient learning algorithm for KMTPLS based on sequentially extracting common and discriminative latent vectors is also presented. Finally, to show the effectiveness and advantages of our approach, we test it on the real-life regression task in computer vision, i.e., reconstruction of human pose from multiview video sequences.

A deep Gaussian process (DGP) is a deep network in which each layer is modelled with a Gaussian process (GP). It is a flexible model that can capture highly-nonlinear functions for complex data sets. However, the network structure of DGP often makes inference computationally expensive. In this paper, we propose an efficient sequential inference framework for DGP, where the data is processed sequentially. We also propose two DGP extensions to handle heteroscedasticity and multi-task learning. Our experimental evaluation shows the effectiveness of our sequential inference framework on a number of important learning tasks.

The higher-order partial least squares (HOPLS) is considered as the state-of-the-art tensor-variate regression modeling for predicting a tensor response from a tensor input. However, the standard HOPLS can quickly become computationally prohibitive or merely impossible, especially when huge and time-evolving tensorial streams arrive over time in dynamic application environments. In this paper, we present a computationally efficient online tensor regression algorithm, namely incremental higher-order partial least squares (IHOPLS), for adapting HOPLS to the setting of infinite time-dependent tensor streams. By incrementally clustering the projected latent variables in latent space and summarizing the previous data, IHOPLS is able to recursively update the projection matrices and core tensors over time, resulting in greatly reduced costs in terms of both memory and running time while maintaining high prediction accuracy. To show the effectiveness and scalability of our approach for large databases, we apply IHOPLS to two real-life applications as reconstruction of 3D motion trajectories from video and ECoG streaming signals.

Tensor-variate regression approaches have been spotlighted over the past years, due to the fact that many challenging regression tasks in the real world involve in high-order tensorial data. However, these approaches are often computationally prohibitive, which limits the predictive performance for large data sets. In this paper, we propose a computationally-efficient tensor-variate regression approach in which the latent function is flexibly modeled by using online local Gaussian process (OLGP). By doing so, the large data set is efficiently processed by constructing a number of small-sized GP experts in an online fashion. Furthermore, we introduce two efficient search strategies to find local GP experts to make accurate predictions with a Gaussian mixture representation. Finally, we evaluate our approach on a real-life regression task, reconstruction of limb movements from brain signal, to show its effectiveness and scalability for large data sets.

We present a novel generalized linear tensor regression model, which takes tensor-variate inputs as covariates and finds low-rank (almost) best approximation of regression coefficient arrays using hierarchical Tucker decomposition. With limited sample size, our model is highly compact and extremely efficient as it requires only O(dr3+ dpr) parameters for order d tensors of mode size p and rank r, which avoids the exponential growth in d, in contrast to O(rd+ dpr) parameters of Tucker regression modeling. Our model also maintains the flexibility like classical Tucker regression by allowing distinct ranks on different modes according to a dimension tree structure. We evaluate our new model on both synthetic data and real-life MRI images to show its effectiveness.

Combinatorial optimization problems are often very difficult to solve and the choice of a search strategy has a tremendous influence over the solver's performance. A search strategy is said to be adaptive when it dynamically adapts to the structure of the problem instance and identifies the areas of the search space that contain good solutions. We introduce an algorithm (RLBS) that learns to efficiently backtrack when searching non-binary trees. Branching can be carried on using any usual variable/value selection strategy. However, when backtracking is needed, the selection of the node to target involves reinforcement learning. As the trees are non-binary, we have the opportunity to backtrack many times to each node during the search, which allows learning which nodes generally lead to the best rewards (that is, to the most interesting leaves). RLBS is evaluated for a scheduling problem using real industrial data. It outperforms classic (nonadaptive) backtracking strategies (DFS, LDS) as well as an adaptive branching strategy (IBS).

One of the major goals for mobile robots is to be able to traverse any kind of terrains. A possible way to achieve this goal is by the use of legged robots, as they have increased mobility. However, this would require them to be able to modify their gaits, based on the identification of the terrain that they are currently traversing. In this paper, we introduce a number of novel methods to address this issue of autonomous terrain classification and clustering, based on tactile data collected with a walking robot. The proposed learning methods are based on the Pitman-Yor process mixture of Gaussians, a Bayesian nonparametric prior, well-suited for density estimation. This model is initially used to learn the non-Gaussian distribution of the features produced from proprioceptive (force/torque) signals from the legs, registered during the interaction of one robot foot with a terrain. Then, we exploit its capacity on clustering and discovering structures in the data to identify terrains in the feature space. Experiments were conducted on a six-legged robot, thus demonstrating the applicability of the Pitman-Yor process mixture of Gaussians for terrain identification. In particular, we obtained a classification success rate of 82% and 51% accuracy, with our supervised learning and unsupervised learning approach respectively.

This paper presents an extension of the cascading Indian buffet process (CIBP) intended to learning arbitrary directed acyclic graph structures as opposed to the CIBP, which is limited to purely layered structures. The extended cascading Indian buffet process (eCIBP) essentially consists in adding an extra sampling step to the CIBP to generate connections between non-consecutive layers. In the context of graphical model structure learning, the proposed approach allows learning structures having an unbounded number of hidden random variables and automatically selecting the model complexity. We evaluated the extended process on multivariate density estimation and structure identification tasks by measuring the structure complexity and predictive performance. The results suggest the extension leads to extracting simpler graphs without scarifying predictive precision.

In this paper, we propose an algorithm for learning a reward model from an expert policy in partially observable Markov decision processes (POMDPs). The problem is formulated as inverse reinforcement learning (IRL) in the POMDP framework. The proposed algorithm then uses the expert trajectories to find an unknown reward model-based on the known POMDP model components. Similar to previous IRL work in Markov Decision Processes (MDPs), our algorithm maximizes the sum of the margin between the expert policy and the intermediate candidate policies. However, in contrast to previous work, the expert and intermediate candidate policy values are approximated using the beliefs recovered from the expert trajectories, specifically by approximating expert belief transitions. We apply our IRL algorithm to a healthcare dialogue POMDP where the POMDP model components are estimated from real dialogues. Our experimental results show that the proposed algorithm is able to learn a reward model that accounts for the expert policy.

Particle filter is one of the most widely applied stochastic sampling tools for state estimation problems in practice. However, the proposal distribution in the traditional particle filter is the transition probability based on state equation, which would heavily affect estimation performance in that the samples are blindly drawn without considering the current observation information. Additionally, the fixed particle number in the typical particle filter would lead to wasteful computation, especially when the posterior distribution greatly varies over time. In this paper, an advanced adaptive nonparametric particle filter is proposed by incorporating gaussian process based proposal distribution into KLD-Sampling particle filter framework so that the high-qualified particles with adaptively KLD based quantity are drawn from the learned proposal with observation information at each time step to improve the approximation accuracy and efficiency. Our state estimation experiments on univariate nonstationary growth model and two-link robot arm show that the adaptive nonparametric particle filter outperforms the existing approaches with smaller size of particles.

We present a novel marginalized particle Gaussian process (MPGP) regression, which provides a fast, accurate online Bayesian filtering framework to model the latent function. Using a state space model established by the data construction procedure, our MPGP recursively filters out the estimation of hidden function values by a Gaussian mixture. Meanwhile, it provides a new online method for training hyperparameters with a number of weighted particles. We demonstrate the estimated performance of our MPGP on both simulated and real large data sets. The results show that our MPGP is a robust estimation algorithm with high computational efficiency, which outperforms other state-of-art sparse GP methods.

Recently, improvements in sensing, communicating, and computing technologies have led to the development of driver-assistance systems (DASs). Such systems aim at helping drivers by either providing a warning to reduce crashes or doing some of the control tasks to relieve a driver from repetitive and boring tasks. Thus, for example, adaptive cruise control (ACC) aims at relieving a driver from manually adjusting his/her speed to maintain a constant speed or a safe distance from the vehicle in front of him/her. Currently, ACC can be improved through vehicle-to-vehicle communication, where the current speed and acceleration of a vehicle can be transmitted to the following vehicles by intervehicle communication. This way, vehicle-to-vehicle communication with ACC can be combined in one single system called cooperative adaptive cruise control (CACC). This paper investigates CACC by proposing a novel approach for the design of autonomous vehicle controllers based on modern machine-learning techniques. More specifically, this paper shows how a reinforcement-learning approach can be used to develop controllers for the secure longitudinal following of a front vehicle. This approach uses function approximation techniques along with gradient-descent learning algorithms as a means of directly modifying a control policy to optimize its performance. The experimental results, through simulation, show that this design approach can result in efficient behavior for CACC.

This paper presents a technique for approximating, up to any precision, the set of subgame-perfect equilibria (SPE) in repeated games with discounting. The process starts with a single hypercube approximation of the set of SPE payoff profiles. Then the initial hypercube is gradually partitioned on to a set of smaller adjacent hypercubes, while those hypercubes that cannot contain any SPE point are gradually withdrawn. Whether a given hypercube can contain an equilibrium point is verified by an appropriate mixed integer program. A special attention is paid to the question of extracting players' strategies and their representability in form of finite automata.

Abstract — We consider the problem of apprenticeship learning when the expert’s demonstration covers only a small part of a large state space. Inverse Reinforcement Learning (IRL) provides an efficient solution to this problem based on the assumption that the expert is optimally acting in a Markov Decision Process (MDP). However, past work on IRL requires an accurate estimate of the frequency of encountering each feature of the states when the robot follows the expert’s policy. Given that the complete policy of the expert is unknown, the features frequencies can only be empirically estimated from the demonstrated trajectories. In this paper, we propose to use a transfer method, known as soft homomorphism, in order to generalize the expert’s policy to unvisited regions of the state space. The generalized policy can be used either as the robot’s final policy, or to calculate the features frequencies within an IRL algorithm. Empirical results show that our approach is able to learn good policies from a small number of demonstrations. I.

This paper compares two algorithms to solve a multiagent patrol problem with uncertain durations. The first algorithm is reactive and allows adaptive and robust behavior, while the second one uses planning to maximize longterm information retrieval. Experiments suggest that on the considered instances, using a reactive and local coordination algorithm performs almost as well as planning for long-term, while using much less computation time.

We consider the problem of apprenticeship learning where the examples, demonstrated by an expert, cover only a small part of a large state space. Inverse Reinforcement Learning (IRL) provides an efficient tool for generalizing the demonstration, based on the assumption that the expert is maximizing a utility function that is a linear combination of state-action features. Most IRL algorithms use a simple Monte Carlo estimation to approximate the expected feature counts under the expert's policy. In this paper, we show that the quality of the learned policies is highly sensitive to the error in estimating the feature counts. To reduce this error, we introduce a novel approach for bootstrapping the demonstration by assuming that: (i), the expert is (near-)optimal, and (ii), the dynamics of the system is known. Empirical results on gridworlds and car racing problems show that our approach is able to learn good policies from a small number of demonstrations.

We consider the problem of estimating the policy gradient in Partially Observable Markov Decision Processes (POMDPs) with a special class of policies that are based on Predictive State Representations (PSRs). We compare PSR policies to Finite-State Controllers (FSCs), which are considered as a standard model for policy gradient methods in POMDPs. We present a general Actor-Critic algorithm for learning both FSCs and PSR policies. The critic part computes a value function that has as variables the parameters of the policy. These latter parameters are gradually updated to maximize the value function. We show that the value function is polynomial for both FSCs and PSR policies, with a potentially smaller degree in the case of PSR policies. Therefore, the value function of a PSR policy can have less local optima than the equivalent FSC, and consequently, the gradient algorithm is more likely to converge to a global optimal solution.

Partially Observable Markov Decision Processes (POMDPs) provide a rich mathematical model to handle real-world sequential decision processes but require a known model to be solved by most approaches. However, mainstream POMDP research focuses on the discrete case and this complicates its application to most realistic problems that are naturally modeled using continuous state spaces. In this paper, we consider the problem of optimal control in continuous and partially observable environments when the parameters of the model are unknown. We advocate the use of Gaussian Process Dynamical Models (GPDMs) so that we can learn the model through experience with the environment. Our results on the blimp problem show that the approach can learn good models of the sensors and actuators in order to maximize long-term rewards.

High dimensionality of belief space in partially observable Markov decision processes (POMDPs) is one of the major causes that severely restricts the applicability of this model. Previous studies have demonstrated that the dimensionality of a POMDP can eventually be reduced by transforming it into an equivalent predictive state representation (PSR). In this paper, we address the problem of finding an approximate and compact PSR model corresponding to a given POMDP model. We formulate this problem in an optimization framework. Our algorithm tries to minimize the potential error that missing some core tests may cause. We also present an empirical evaluation on benchmark problems, illustrating the performance of this approach.

This paper treats the problem of distributed planning in general-sum stochastic games with communication when the model is known. Our main contribution is a novel, game theoretic approach to the problem of distributed equilibrium computation and selection. We show theoretically and via experiments that our approach, when adopted by all agents, facilitates an efficient distributed equilibrium computation and leads to a unique equilibrium selection in general-sum stochastic games with communication.

We consider the problem of optimal control in continuous and partially observable environments when the parameters of the model are not known exactly. Partially observable Markov decision processes (POMDPs) provide a rich mathematical model to handle such environments but require a known model to be solved by most approaches. This is a limitation in practice as the exact model parameters are often difficult to specify exactly. We adopt a Bayesian approach where a posterior distribution over the model parameters is maintained and updated through experience with the environment. We propose a particle filter algorithm to maintain the posterior distribution and an online planning algorithm, based on trajectory sampling, to plan the best action to perform under the current posterior. The resulting approach selects control actions which optimally trade-off between 1) exploring the environment to learn the model, 2) identifying the system's state, and 3) exploiting its knowledge in order to maximize long-term rewards. Our preliminary results on a simulated robot navigation problem show that our approach is able to learn good models of the sensors and actuators, and performs as well as if it had the true model.

Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.

The problem of an effective coordination of multiple autonomous robots is one of the most important tasks of the modern robotics. In turn, it is well known that the learning to coordinate multiple autonomous agents in a multiagent system is one of the most complex challenges of the state-of-the-art intelligent system design. Principally, this is because of the exponential growth of the environment's dimensionality with the number of learning agents. This challenge is known as "curse of dimensionality", and relates to the fact that the dimensionality of the multiagent coordination problem is exponential in the number of learning agents, because each state of the system is a joint state of all agents and each action is a joint action composed of actions of each agent. In this paper, we address this problem for the restricted class of environments known as goal-directed stochastic games with action-penalty representation. We use a single-agent problem solution as a heuristic approximation of the agents' initial preferences and, by so doing, we restrict to a great extent the space of multiagent learning. We show theoretically the correctness of such an initialization, and the results of experiments in a well-known two-robot grid world problem show that there is a significant reduction of complexity of the learning process.

Bayesian Reinforcement Learning has generated substantial interest recently, as it provides an elegant solution to the exploration-exploitation trade-off in reinforce- ment learning. However most investigations of Bayesian reinforcement learning to date focus on the standard Markov Decision Processes (MDPs). Our goal is to extend these ideas to the more general Partially Observable MDP (POMDP) framework, where the state is a hidden variable. To address this problem, we in- troduce a new mathematical model, the Bayes-Adaptive POMDP. This new model allows us to (1) improve knowledge of the POMDP domain through interaction with the environment, and (2) plan optimal sequences of actions which can trade- off between improving the model, identifying the state, and gathering reward. We show how the model can be finitely approximated while preserving the value func- tion. We describe approximations for belief tracking and planning in this model. Empirical results on two domains show that the model estimate and agent’s return improve over time, as the agent learns better model estimates.

Planning in partially observable environments remains a challenging problem, despite significant recent advances in offline approximation techniques. A few online methods have also been proposed recently, and proven to be remarkably scalable, but without the theoretical guarantees of their offline counterparts. Thus it seems natural to try to unify offline and online techniques, preserving the theoretical properties of the former, and exploiting the scalability of the latter. In this paper, we provide theoretical guarantees on an anytime algorithm for POMDPs which aims to reduce the error made by approximate offline value iteration algorithms through the use of an efficient online searching procedure. The algorithm uses search heuristics based on an error analysis of lookahead search, to guide the online search towards reachable beliefs with the most potential to reduce error. We provide a general theorem showing that these search heuristics are admissible, and lead to complete and epsilon-optimal algorithms. This is, to the best of our knowledge, the strongest theoretical result available for online POMDP solution methods. We also provide empirical evidence showing that our approach is also practical, and can find (provably) near-optimal solutions in reasonable time.

The use of agent and multiagent techniques to assist humans in their daily routines has been increasing for many years, notably in command and control C2 systems. In this context, we propose using multiagent planning and coordination techniques for resources management in C2 systems. The particular problem we studied is the design of a decision-support for antiair warfare on combat ships. In this paper, we refer to the specific case of several combat ships defending against incoming threats and where coordination of their respective resources is a complex problem of capital importance. Efficient coordination mechanisms between the different combat ships are then important to avoid redundancy in engagements and inefficient defence caused by the conflicting actions. To this end, we present four different coordination mechanisms based on task sharing. Three of these mechanisms are communication-based: central coordination, contract Net coordination, and ~ Brown coordination, while the last one is a zone defence coordination and is based on conventions. Finally, we present the results obtained while simulating these various mechanisms

The bullwhip effect is an amplification of the variability of the orders placed by companies in a supply chain. This variability reduces the efficiency of supply chains, since it incurs costs due to higher inventory levels and supply chain agility reduction. Eliminating the bullwhip effect is surely simple; every company just has to order following the market demand, i.e., each company should use a lot-for-lot type of ordering policy. However, many reasons, such as inventory management, lot-sizing, and market, supply, or operation uncertainties, motivate companies not to use this strategy. Therefore, the bullwhip effect cannot be totally eliminated. However, it can be reduced by information sharing, which is the form of collaboration considered in this paper. More precisely, we study how to separate demand into original demand and adjustments. We describe two principles explaining how to use the shared information to reduce the amplification of order variability induced by lead times, which we propose as a cause of the effect. Simulations confirm the value of these two principles with regard to costs and customer service levels.

Software agents can be useful in forming buyers’ groups since humans have considerable difficulties in finding Pareto-optimal deals (no buyer can be better without another being worse) in negotiation situations. What are the computational and economical performances of software agents for a group buying problem? We have developed a negotiation protocol for software agents which we have evaluated to see if the problem is difficult on average and why. This protocol probably finds a Pareto-optimal solution and, furthermore, minimizes the worst distance to ideal among all software agents given strict preference ordering. This evaluation demonstrated that the performance of software agents in this group buying problem is limited by memory requirements (and not execution time complexity). We have also investigated whether software agents following the developed protocol have a different buying behaviour from that which the customer they represented would have had in the same situation. Results show that software agents have a greater difference of behaviour (and better behaviour since they can always simulate the obvious customer behaviour of buying alone their preferred product) when they have similar preferences over the space of available products. We also discuss the type of behaviour changes and their frequencies based on the situation.

Agent technology is an exciting and important new way to create complex software systems. Agents blend many of the traditional properties of AI programs—knowledge–level reasoning, flexibility, proactiveness, goal–directedness, and so forth—with insights gained from distributed software engineering, machine learning, negotiation and teamwork theory, and the social sciences. An important part of the agent approach is the principle that agents (like humans) can function more effectively in groups that are characterized by cooperation and division of labor. Agent programs are designed to autonomously collaborate with each other in order to satisfy both their internal goals and the shared external demands generated by virtue of their participation in agent societies. This type of collaboration depends on a sophisticated system of inter–agent communication. The assumption that inter–agent communication is best handled through the explicit use of an agent communication language (ACL) underlies each of the articles in this special issue. In this introductory article, we will supply a brief background and introduction to the main topics in agent communication.

Analytical techniques are generally inadequate for dealing with causal interrelationships among a set of individual and social concepts. Usually, causal maps are used to cope with this type of interrelationships. However, the classical view of causal maps is based on an intuitive view with ad hoc rules and no precise semantics of the primitive concepts, nor a sound formal treatment of relations between concepts. We solve this problem by proposing a formal model for causal maps with a precise semantics based on relational algebra and the software tool, CM-RELVIEW, in which it has been implemented. Then, we investigate the issue of using this tool in multiagent environments by explaining through different examples how and why this tool is useful for the following aspects: 1) the reasoning on agents' subjective views, 2) the qualitative distributed decision making, and 3) the organization of agents considered as a holistic approach. For each of these aspects, we focus on the computational mechanisms developed within CM-RELVIEW to support it.

Presents AGENDA (A GENeral testbed for Distributed AI Applications), a simulation tool developed for the simulation and design of applications involving interacting entities. This testbed consists of two different levels, the architecture level and the system development level. The architecture level describes a methodology for designing software agents by providing several important functionalities an agent should have. On the other hand, the system development level provides the basic knowledge representation formalism, general inference mechanisms, and a simulation tool-box supporting visualization and monitoring of agents. Following this, the applicability of AGENDA to the transportation domain is presented in detail. The main challenge of AGENDA in the context of this domain has been to provide different cooperation-scalable methods based on negotiation, leading to different scheduling mechanisms, and to experimentally evaluate these mechanisms. This evaluation shows that: (1) AGENDA is suitable for realistic application in the transportation domain; (2) the mechanisms used for vertical negotiation (between trucks considered as agents) and for horizontal negotiation (between companies considered as agents) are applicable for the real-world transportation domain applications. Finally, a complete study of the scalability of the simulation tool and the algorithms used for the negotiation is presented. This study, along with the evaluation of the different mechanisms, can help designers of transportation companies, particularly in the case of large companies.

A framework for designing a Multiagent System (MAS) in which agents are capable of coordinating their activities in routine, familiar, and unfamiliar situations is proposed. This framework is based on the Skills, Rules and Knowledge (S-R-K) taxonomy of Rasmussen. Thus, the proposed framework should allow agents to prefer the lower skill-based and rule-based levels rather than the higher knowledge-based level because it is generally easier to obtain and maintain coordination between agents in routine and familiar situations than in unfamiliar situations. The framework should also support each of the three levels because complex tasks combined with complex interactions require all levels. To permit agents to rely on low levels, a suggestion is developed: agents are provided with social laws so as to guarantee coordination between agents and minimize the need for calling a central coordinator or for engaging in negotiation which requires intense communication. Finally, implementation and experiments demonstrated, on some scenarios of urban traffic, the applicability of major concepts developed in this article.

In this paper, a framework based on the skills, rules and knowledge taxonomy of Rasmussen is proposed. Precisely, a reflexive level is developed so as to reflect the fully automated activities, then a rule level to reflect stereotyped actions, and finally a knowledge level to reflect conscious activities involving distributed decision making. In fact, the basic goal of this framework is twofold: first, not to force processing to a higher level (i.e. the knowledge level) than the situation requires, and to support each of the three levels of cognitive control. More precisely, the proposed framework should allow agents to prefer the lower skills and rules levels rather than the higher knowledge level because it is generally easier to obtain and maintain coordination between agents in routine and familiar situations than in unfamiliar situations. The framework should also support each of the three levels because complex tasks combined with complex interactions require all levels. To permit agents to rely on low levels, a suggestion is developed. When it is possible, agents have to communicate by signals and signs since signals generally invoke a stimulus or a reaction that is a routine situation, whereas signs generally activate familiar situations. Finally, implementation and experiments demonstrated, on some scenarios of urban traffic, the applicability of concepts developed in this article.