This paper deals with the problem of planning multiple agent movements through a mission area modeled as a graph. The agents undergo classic communication and temporal constraints, and the quantitative objective is the minimization of the team’s traversal makespan. Additional specificities make the problem a particularly complex routing one: on some nodes are associated durative and coordinated actions to perform, which can involve either the co-presence of several agents or time dependencies. Also, some agents are deployable and able to move on denser graphs: namely, aerial robots can take off and land on the ground vehicle at any planned position, and can fly above ground obstacles. We model the problem as a CSP and solve it with a network flow model. Results show the efficacy of the model and resolution scheme, which provides solutions with one or two orders of magnitude smaller time than a numerical temporal hierarchical planning model, with only a few percent loss of optimality.

The Multi-Agent Path Finding with Task Assignment (MAPF-TA) problem combines task allocation and collision-free path finding for multiple agents within a graph. It can be solved by an extension of the well-known Conflict-Based Search (CBS) algorithm called CBS-TA, which has been demonstrated to be optimal in terms of the sum of costs of all agents. While coordination between agents in MAPF-TA is limited to no-collision constraints, real-world scenarios may require cooperation between agents. For instance, in an exploration mission involving a system of multiple robots, one robot might need to enter a hazardous area only if another agent is able to monitor this area from a support location. Given a hazardous location and its corresponding support location, this coordination requirement can be modeled by a support constraint. In this paper, we propose an extension of the CBS-TA algorithm to handle these support conflicts. In addition, we improve the algorithm’s performance by introducing an alternative cost matrix for task assignment, which takes into account support coordination while maintaining the optimality of the CBS-TA algorithm. We compare the proposed approach to a greedy algorithm in which the task assignment and path finding problems are decoupled, and using two different assignment matrices: the original matrix of CBS-TA and our support-aware matrix. Experiments are carried out using standard MAPF benchmark instances, showing that the proposed cost matrix improves search time and increases the number of instances solved within a given timeout.

Countries with access to large bodies of water often aim to protect their maritime transport by employing maritime surveillance systems. However, the number of available sensors (e.g., cameras) is typically small compared to the to-be-monitored targets, and their Field of View (FOV) and range are often limited. This makes improving the situational awareness of maritime transports challenging. To this end, we propose a method that not only distributes multiple sensors but also plans paths for them to observe multiple targets, while minimizing the time needed to achieve situational awareness. In particular, we provide a formulation of this sensor allocation and path planning problem which considers the partial awareness of the targets’ state, as well as the unawareness of the targets’ trajectories. To solve the problem we present two algorithms: 1) a greedy algorithm for assigning sensors to targets, and 2) a distributed multi-agent path planning algorithm based on regret-matching learning. Because a quick convergence is a requirement for algorithms developed for high mobility environments, we employ a forgetting factor to quickly converge to correlated equilibrium solutions. Experimental results show that our combined approach achieves situational awareness more quickly than related work.

We are interested in realistic planning problems to model the behavior of Non-Playable Characters (NPCs) in video games. Search-based action planning, introduced by the game F.E.A.R. in 2005, has an exponential time complexity allowing to control only a dozen NPCs between two frames. A close study of the plans generated in first-person shooters shows that: (1) actions are unary, (2) actions are contextually post-unique and (3) there is no two instances of the same action in an NPC’s plan. By considering (1), (2) and (3) as restrictions, we introduce new classes of problems with the Simplified Action Structure formalism which indeed allow to model realistic problems and whose instances are solvable by a linear-time algorithm. We also experimentally show that our algorithm is capable of managing millions of NPCs per frame.

Route planning for autonomous vehicles is a challenging task, especially in dense road networks with multiple delivery points. Additional external constraints can quickly add overhead to this already-difficult problem that often requires prompt, on-the-fly decisions. This work introduces a hybrid method combining machine learning and Constraint Programming (CP) to improve search performance. A new message passing-based graph neural network tailored to constraint solving and global search is defined. Once trained, a single neural network inference is enough to guide CP search while ensuring solution optimality. Large-scale experiments using real road networks from cities worldwide are presented. The hybrid method is effective in solving complex routing problems, addressing larger problems than those used for model training.

Scheduling under uncertainty is an area of interest in artificial intelligence. We study the problem of Dynamic Controllability (DC) of Disjunctive Temporal Networks with Uncertainty (DTNU), which seeks a reactive scheduling strategy to satisfy temporal constraints in response to uncontrollable action durations. We introduce new semantics for reactive scheduling: Time-based Dynamic Controllability (TDC) and a restricted subset of TDC, R-TDC. We present a tree search approach to determine whether or not a DTNU is R-TDC. Moreover, we leverage the learning capability of a Graph Neural Network (GNN) as a heuristic for tree search guidance. Finally, we conduct experiments on a known benchmark on which we show R-TDC to retain significant completeness with regard to DC, while being faster to prove. This results in the tree search processing fifty percent more DTNU problems in R-TDC than the state-of-the-art DC solver does in DC with the same time budget. We also observe that GNN tree search guidance leads to substantial performance gains on benchmarks of more complex DTNUs, with up to eleven times more problems solved than the baseline tree search.

Learning-based methods are growing prominence for planning purposes. However, there are very few approaches for learning-assisted constrained path-planning on graphs, while there are multiple downstream practical applications. This is the case for constrained path-planning for Autonomous Unmanned Ground Vehicles (AUGV), typically deployed in disaster relief or search and rescue applications. In off-road environments, the AUGV must dynamically optimize a source-destination path under various operational constraints, out of which several are difficult to predict in advance and need to be addressed on-line. We propose a hybrid solving planner that combines machine learning models and an optimal solver. More specifically, a graph convolutional network(GCN) is used to assist a branch and bound(B&B) algorithm in handling the constraints. We conduct experiments on realistic scenarios and show that GCN support enables substantial speedup and smoother scaling to harder problems.

Complex operational environments require improved tactical mission command capabilities with a high level of interoperability among coalition control and command (C2) systems. This paper focuses on two areas of interest: decision support based on automated planning and Service Oriented Architecture (SOA) for rapid service development. Previous experiments were performed bilaterally by US, France and Germany to focus on collaborative mission planning using Web Services (WSs). The results reported herein were obtained from a unified experiment performed by US, France and Germany involving a common scenario. The operational benefit from the experimentation has been to improve mutual understanding among allied forces, to dynamically plan for assistance among ground support troops (logistics, MEDEVAC, and other areas) as well as to improve their coordination. The effort addressed system design, and integration within an experimental framework. It enabled the evolution of the CERDEC Mission Command Gateway (MCG) architecture as well as a constraint based planner ORTAC, developed by French DGA and Sagem. It takes into account near real-time multimodal Situation Awareness and readiness status from tactical edge units. The trilateral experiment, entitled From Data to Decision included Net-Centric manned and unmanned assets from all three nations (France Germany US) operating as a cohesive coalition force while preserving command and support relationships as required through their respective chains of command.

The world we live in is becoming smarter. Miniature sensors and actuators integrated with processors are being embedded in our environments to monitor and control the physical processes. These sensor and actuator systems are evolving towards a physically heterogeneous and distributed but functionally coherent environment consisting of both wired and wireless communication components. Battery-powered networked devices are increasingly more common. Mobile ad hoc and wireless sensor and actuator networks are receiving considerable research attention. Applications of intelligent networked sensor and actuator systems are tremendous and have the potential to dwarf the 20th century computing revolution. They include intelligent traffic control and safety, advanced automotive systems, process control, energy conservation, environmental control, advanced medical and health care devices and systems, critical infrastructure control, communications systems, distributed robotics, and security surveillance and protection. For example, transportation systems could benefit considerably from better embedded intelligence in automobiles and in transportation infrastructures, which could improve safety and efficiency. Embedded sensor and actuator systems are not new. Yet most existing systems are special purpose, closed systems with tightly coupled components. Networking and managing a large number of embedded sensors and actuators poses significant technical challenges. For example, in a network environment, the behaviors of sensor and actuator systems are much more unpredictable, and it is impossible to test software under all possible conditions. The technical challenges are not only efficiency, but also robustness, scalability, and predictability. These unique characteristics in the design of distributed systems of sensors and actuators have motivated a growing interest and a considerable amount of research activities in this emerging area. This special issue includes a collection of 13 outstanding research papers which cover diverse topics on the design, analysis, experimental evaluation, and applications of distributed systems of sensors and actuators, particularly the ones connected through wireless networks. This special issue begins with three survey papers on wireless sensor networks (WSN): applications in intelligent transportation systems, radio power management, and mobility-aware MAC protocols. In “Wireless sensor networks in intelligent transportation systems,” Tubaishat et al. reviewed existing sensor network technologies and applications for intelligent transportation systems and proposed new methods for using WSN in traffic modeling and estimation and traffic control that outperform existing methods. In “Mobility handling in MAC for wireless ad hoc networks,” Raja and Su reviewed the current state of the arts in handling mobility in sensor networks, presented simulation results to analyze existing mobility-aware MAC protocols, and discussed open issues in dealing with mobility in sensor networks. In “Towards unified radio power management for wireless sensor networks,” Xing et al. reviewed existing transmission power control and sleep scheduling approaches to reducing radio power consumption in the transmission state and the idle state and proposed a Unified Radio Power Management framework for the design and implementation of holistic radio power management solutions in WSN. The next three papers address architecture, middleware, and data storage issues in WSN. In “Lifetime-maximized cluster association in two-tiered wireless sensor networks,” Song et al. studied the two-tiered WSN architecture and proposed an optimal cluster association algorithm to maximize the overall network lifetime. In “Embedding standard distributed object-oriented middlewares in wireless sensor networks,” Moya et al. analyzed the design space available to middleware developers in the context of WSN and presented a development framework based on standard distributed objects and a set of specific services designed to support highly dynamic and scalable WSN applications. In “Improving data centric storage with diffuse caching in wireless sensor networks,” Ma et al. studied data-centric storage problems in a sensor network and proposed new diffuse caching techniques to alleviate the hot-spot problem and reduce the message overheads. The following three papers present new methods for data aggregation and image delivery in sensor networks. In “Isolines: Efficient spatio-temporal data aggregation in sensor networks,” Solis and Obraczka introduced an energy-efficient data collection technique that takes advantage of spatial and temporal data correlation for monitoring continuously changing conditions. In “Reward oriented packet filtering algorithm for wireless sensor networks,” Shu et al. studied packet filtering for reducing energy consumption in sensor networks and proposed a two-tier buffer model and two packet filtering algorithms for real time and non-real time transmissions, respectively. In “An adaptive approach for image encryption and secure transmission over multirate wireless sensor networks,” Wang et al. proposed a new adaptive secure image delivery approach to achieve effective and efficient image encryption based on an optimal transmission rate in terms of energy efficiency in WSN. The final four papers propose new methods for routing and topology control in wireless networks. In “Energy-efficient geographic multicast routing for error-prone wireless sensor networks,” Sanchez and Ruiz proposed a new protocol, Localized Energy-Efficient Multicast Algorithm, to address the error-prone nature of wireless links when designing routing protocols for WSN. In “Receiver-oriented load-balancing and reliable routing in wireless sensor networks,” Chen et al. proposed a novel receiver-oriented load-balancing and reliable routing protocol that achieves relatively longer network lifetime and higher reliability than other existing schemes. In “QuESt: A QoS-based energy efficient sensor routing protocol,” Saxena et al. used multi-objective genetic algorithm to design a QoS-based energy-efficient sensor routing protocol that determines application-specific, near-optimal sensory-routes demand by optimizing multiple QoS parameters and energy consumption. In “A novel distributed MCDS approximation algorithm for wireless sensor networks,” Xie et al. proposed a novel distributed approximation algorithm to construct the minimal connected dominating set for WSN. This algorithm generates smaller connected dominating sets while requiring less communication overhead compared with the existing distributed approximation algorithms. We thank all the authors who submitted their papers to this special issue. Owing to the limitation of space, we can only include limited number of papers in the special issue. We are grateful to all the reviewers for their time and efforts in carefully reviewing all the papers and providing valuable review comments. We also thank the Editor-in-Chief, Mohsen Guizani, for his continuous support for this special issue, and all the publication staff for their support during the publishing process.

This paper presents a technique to map automatically a complete digital signal processing (DSP) application onto a parallel machine with distributed memory. Unlike other applications where coarse or medium grain scheduling techniques can be used, DSP applications integrate several thousand of tasks and hence necessitate fine grain considerations. Moreover finding an effective mapping imperatively require to take into account both architectural resources constraints and real time constraints. The main contribution of this paper is to show how it is possible to handle and to solve data partitioning, and fine-grain scheduling under the above operational constraints using concurrent constraints logic programming languages (CCLP). Our concurrent resolution technique undertaking linear and nonlinear constraints takes advantage of the special features of signal processing applications and provides a solution equivalent to a manual solution for the representative panoramic analysis (PA) application.