"Planning is the process of generating (possibly partial) representations of future behavior prior to the use of such plans to constrain or control that behavior. The outcome is usually a set of actions, with temporal and other constraints on them, for execution by some agent or agents. As a core aspect of human intelligence, planning has been studied since the earliest days of AI and cognitive science. Planning research has led to many useful tools for real-world applications, and has yielded significant insights into the organization of behavior and the nature of reasoning about actions."
– Planning entry by Austin Tate in the MIT Encyclopedia of Cognitive Science.
Parsons Corporation (NYSE: PSN) is developing and deploying artificial intelligence (AI) across a wide array of federal solutions and critical infrastructure projects to solve our customer's most challenging problems, produce actionable intelligence, and improve the user experience. Data analytics, AI, and edge computing are ingrained in company offerings across all business units. For example, the company developed an AI-enabled weapon-target pairing algorithm, with initial tests showing outstanding accuracy and speed results; produced an electronic warfare (EW) planning optimization tool-set named TEMPO (Tactical Electronic Warfare Machine Learning Planning Optimization); and recently won a classified research and development contract to develop constellation task scheduling algorithms based on organically developed AI technology. "Parsons' artificial intelligence capabilities align with our customer's vision by improving situational awareness, decision-making, the safety of operating equipment, streamlining business processes, and protecting critical infrastructure," said Ricardo Lorenzo, chief technology officer for Parsons. "By combining our AI technical expertise with our operational understanding of the all-domain environment and critical infrastructure markets, we're working closely with our customers to develop leap-ahead technology that empowers operators at the tactical edge and beyond. We're also developing differentiated capabilities that ensure the efficiency and security of existing energy and water networks."
Model-based planning and prospection are widely studied in both cognitive neuroscience and artificial intelligence (AI), but from different perspectives - and with different desiderata in mind (biological realism versus scalability) that are difficult to reconcile. Here, we introduce a novel method to plan in large POMDPs - Active Tree Search - that combines the normative character and biological realism of a leading planning theory in neuroscience (Active Inference) and the scalability of Monte-Carlo methods in AI. This unification is beneficial for both approaches. On the one hand, using Monte-Carlo planning permits scaling up the biologically grounded approach of Active Inference to large-scale problems. On the other hand, the theory of Active Inference provides a principled solution to the balance of exploration and exploitation, which is often addressed heuristically in Monte-Carlo methods. Our simulations show that Active Tree Search successfully navigates binary trees that are challenging for sampling-based methods, problems that require adaptive exploration, and the large POMDP problem Rocksample. Furthermore, we illustrate how Active Tree Search can be used to simulate neurophysiological responses (e.g., in the hippocampus and prefrontal cortex) of humans and other animals that contain large planning problems. These simulations show that Active Tree Search is a principled realisation of neuroscientific and AI theories of planning, which offers both biological realism and scalability.
Yesterday, while watching Intel's new CEO lay out his plan for the company's future, I started thinking back on the last 15 years of tech. In 2005 I owned a smartphone powered by an Intel processor. The HTC Magician was, like every smartphone in 2005, not great, but it was fully functional, well-received and powered by an XScale ARM chip. A year after I bought the Magician, Intel sold its XScale business for $600 million, believing it would have an ultra-efficient (0.5W!) x86 CPU capable of running Windows Vista by 2010. ARM-based chips were sold inside phones, laptops, games consoles and thousands of IoT devices.
A desirable goal for autonomous agents is to be able to coordinate on the fly with previously unknown teammates. Known as "ad hoc teamwork", enabling such a capability has been receiving increasing attention in the research community. One of the central challenges in ad hoc teamwork is quickly recognizing the current plans of other agents and planning accordingly. In this paper, we focus on the scenario in which teammates can communicate with one another, but only at a cost. Thus, they must carefully balance plan recognition based on observations vs. that based on communication. This paper proposes a new metric for evaluating how similar are two policies that a teammate may be following - the Expected Divergence Point (EDP). We then present a novel planning algorithm for ad hoc teamwork, determining which query to ask and planning accordingly. We demonstrate the effectiveness of this algorithm in a range of increasingly general communication in ad hoc teamwork problems.
Surveillance and exploration of large environments is a tedious task. In spaces with limited environmental cues, random-like search appears to be an effective approach as it allows the robot to perform online coverage of environments using a simple design. One way to generate random-like scanning is to use nonlinear dynamical systems to impart chaos into the robot's controller. This will result in generation of unpredictable but at the same time deterministic trajectories, allowing the designer to control the system and achieve a high scanning coverage. However, the unpredictability comes at the cost of increased coverage time and lack of scalability, both of which have been ignored by the state-of-the-art chaotic path planners. This study introduces a new scalable technique that helps a robot to steer away from the obstacles and cover the entire space in a short period of time. The technique involves coupling and manipulating two chaotic systems to minimize the coverage time and enable scanning of unknown environments with different properties online. Using this technique resulted in 49% boost, on average, in the robot's performance compared to the state-of-the-art planners. While ensuring unpredictability in the paths, the overall performance of the chaotic planner remained comparable to optimal systems.
Goal Recognition is the task of discerning the correct intended goal that an agent aims to achieve, given a set of possible goals, a domain model, and a sequence of observations as a sample of the plan being executed in the environment. Existing approaches assume that the possible goals are formalized as a conjunction in deterministic settings. In this paper, we develop a novel approach that is capable of recognizing temporally extended goals in Fully Observable Non-Deterministic (FOND) planning domain models, focusing on goals on finite traces expressed in Linear Temporal Logic (LTLf) and (Pure) Past Linear Temporal Logic (PLTLf). We empirically evaluate our goal recognition approach using different LTLf and PLTLf goals over six common FOND planning domain models, and show that our approach is accurate to recognize temporally extended goals at several levels of observability.
Agha, Ali, Otsu, Kyohei, Morrell, Benjamin, Fan, David D., Thakker, Rohan, Santamaria-Navarro, Angel, Kim, Sung-Kyun, Bouman, Amanda, Lei, Xianmei, Edlund, Jeffrey, Ginting, Muhammad Fadhil, Ebadi, Kamak, Anderson, Matthew, Pailevanian, Torkom, Terry, Edward, Wolf, Michael, Tagliabue, Andrea, Vaquero, Tiago Stegun, Palieri, Matteo, Tepsuporn, Scott, Chang, Yun, Kalantari, Arash, Chavez, Fernando, Lopez, Brett, Funabiki, Nobuhiro, Miles, Gregory, Touma, Thomas, Buscicchio, Alessandro, Tordesillas, Jesus, Alatur, Nikhilesh, Nash, Jeremy, Walsh, William, Jung, Sunggoo, Lee, Hanseob, Kanellakis, Christoforos, Mayo, John, Harper, Scott, Kaufmann, Marcel, Dixit, Anushri, Correa, Gustavo, Lee, Carlyn, Gao, Jay, Merewether, Gene, Maldonado-Contreras, Jairo, Salhotra, Gautam, Da Silva, Maira Saboia, Ramtoula, Benjamin, Fakoorian, Seyed, Hatteland, Alexander, Kim, Taeyeon, Bartlett, Tara, Stephens, Alex, Kim, Leon, Bergh, Chuck, Heiden, Eric, Lew, Thomas, Cauligi, Abhishek, Heywood, Tristan, Kramer, Andrew, Leopold, Henry A., Choi, Chris, Daftry, Shreyansh, Toupet, Olivier, Wee, Inhwan, Thakur, Abhishek, Feras, Micah, Beltrame, Giovanni, Nikolakopoulos, George, Shim, David, Carlone, Luca, Burdick, Joel
This paper presents and discusses algorithms, hardware, and software architecture developed by the TEAM CoSTAR (Collaborative SubTerranean Autonomous Robots), competing in the DARPA Subterranean Challenge. Specifically, it presents the techniques utilized within the Tunnel (2019) and Urban (2020) competitions, where CoSTAR achieved 2nd and 1st place, respectively. We also discuss CoSTAR's demonstrations in Martian-analog surface and subsurface (lava tubes) exploration. The paper introduces our autonomy solution, referred to as NeBula (Networked Belief-aware Perceptual Autonomy). NeBula is an uncertainty-aware framework that aims at enabling resilient and modular autonomy solutions by performing reasoning and decision making in the belief space (space of probability distributions over the robot and world states). We discuss various components of the NeBula framework, including: (i) geometric and semantic environment mapping; (ii) a multi-modal positioning system; (iii) traversability analysis and local planning; (iv) global motion planning and exploration behavior; (i) risk-aware mission planning; (vi) networking and decentralized reasoning; and (vii) learning-enabled adaptation. We discuss the performance of NeBula on several robot types (e.g. wheeled, legged, flying), in various environments. We discuss the specific results and lessons learned from fielding this solution in the challenging courses of the DARPA Subterranean Challenge competition.
AlphaZero, using a combination of Deep Neural Networks and Monte Carlo Tree Search (MCTS), has successfully trained reinforcement learning agents in a tabula-rasa way. The neural MCTS algorithm has been successful in finding near-optimal strategies for games through self-play. However, the AlphaZero algorithm has a significant drawback; it takes a long time to converge and requires high computational power due to complex neural networks for solving games like Chess, Go, Shogi, etc. Owing to this, it is very difficult to pursue neural MCTS research without cutting-edge hardware, which is a roadblock for many aspiring neural MCTS researchers. In this paper, we propose a new neural MCTS algorithm, called Dual MCTS, which helps overcome these drawbacks. Dual MCTS uses two different search trees, a single deep neural network, and a new update technique for the search trees using a combination of the PUCB, a sliding-window, and the epsilon-greedy algorithm. This technique is applicable to any MCTS based algorithm to reduce the number of updates to the tree. We show that Dual MCTS performs better than one of the most widely used neural MCTS algorithms, AlphaZero, for various symmetric and asymmetric games.
We propose a novel method for reconstructing floor plans from noisy 3D point clouds. Our main contribution is a principled approach that relies on the Monte Carlo Tree Search (MCTS) algorithm to maximize a suitable objective function efficiently despite the complexity of the problem. Like previous work, we first project the input point cloud to a top view to create a density map and extract room proposals from it. Our method selects and optimizes the polygonal shapes of these room proposals jointly to fit the density map and outputs an accurate vectorized floor map even for large complex scenes. To do this, we adapted MCTS, an algorithm originally designed to learn to play games, to select the room proposals by maximizing an objective function combining the fitness with the density map as predicted by a deep network and regularizing terms on the room shapes. We also introduce a refinement step to MCTS that adjusts the shape of the room proposals. For this step, we propose a novel differentiable method for rendering the polygonal shapes of these proposals. We evaluate our method on the recent and challenging Structured3D and Floor-SP datasets and show a significant improvement over the state-of-the-art, without imposing any hard constraints nor assumptions on the floor plan configurations.
In dense and dynamic scenarios, planning a safe and comfortable trajectory is full of challenges when traffic participants are driving at high speed. The classic graph search and sampling methods first perform path planning and then configure the corresponding speed, which lacks a strategy to deal with the high-speed obstacles. Decoupling optimization methods perform motion planning in the S-L and S-T domains respectively. These methods require a large free configuration space to plan the lane change trajectory. In dense dynamic scenes, it is easy to cause the failure of trajectory planning and be cut in by others, causing slow driving speed and bring safety hazards. We analyze the collision relationship in the spatio-temporal domain, and propose an instantaneous analysis model which only analyzes the collision relationship at the same time. In the model, the collision-free constraints in 3D spatio-temporal domain is projected to the 2D space domain to remove redundant constraints and reduce computational complexity. Experimental results show that our method can plan a safe and comfortable lane-changing trajectory in dense dynamic scenarios. At the same time, it improves traffic efficiency and increases ride comfort.