bluuebunny/crossref_metadata_2025 huggingface dataset:
Michel Maffesoli e as definições do contemporâneo
Authors: Schroeder Tania Maria Rechia , Abreu Claudia Barcelos de Moura , Alves Fabio Lopes
Published: September 2022

Resumo A presente resenha analisa a obra Être postmoderne, de autoria do sociólogo Michel Maffesoli, publicada pela editora Éditions du Cerf (Paris), ainda sem tradução para a língua portuguesa. Ao longo do livro, o autor reafirma, assim como em obras anteriores, que estamos vivendo em um momento de saturação dos valores modernos e de emergência de valores pós-modernos. Être Postmoderne está estruturado em nove capítulos: 1. L’Oxymore; 2. Juvenoïa; 3. Métapolitique; 4. Sacral; 5. Nous; 6. Initiation; 7. Tradition; 8. Naturalisme; 9. Épinoïa. A leitura dessa obra instiga a pensarmos variadas questões sobre os valores que regem a vida cotidiana na atualidade. Desse modo, o texto examina, sem perder de vista o debate com seus críticos, os principais aspectos discutidos por Maffesoli ao longo do livro.
Estadísticas y gestión política del primer año de pandemia de Covid-19 en Argentina
Authors: Daniel Claudia , Marchesini Natalia Romero , Lanata-Briones Cecilia T.
Published: September 2022

Resumen La pandemia de Covid-19 estimuló la generación y amplia circulación de estadísticas sanitarias. Este artículo examina el rol que adquirieron las estadísticas del Covid-19 en la gestión política de la emergencia sanitaria en la Argentina, un país que se caracterizó por adoptar medidas tempranas, un confinamiento social estricto inicial y posteriores flexibilizaciones que significaban todo un desafío de coordinación en una sociedad en crisis. La investigación adoptó una estrategia metodológica cualitativa apoyada en el análisis sistemático de una variedad de fuentes: normativa, informes gubernamentales, prensa y registros en video de las conferencias de prensa presidenciales. Por un lado, el artículo explora la trama institucional de elaboración de esas estadísticas, deteniéndose en algunos puntos de esa cadena como las clasificaciones estadísticas, y subraya la serie de tensiones a las que estuvo expuesta. Por otro lado, muestra cómo las estadísticas fueron utilizadas para conferir legitimidad a las decisiones de la autoridad política, escenificadas en verdaderos rituales de cuantificación, a la vez que resultaron un medio a través del cual esa autoridad fue ejercida. Además de atribuir significado a la experiencia compartida, los indicadores estadísticos formaron parte de un dispositivo de coordinación de la acción a distancia y desde el centro que restringía los márgenes de acción discrecional de las autoridades subnacionales y operaba como un mecanismo externo e impersonal de regulación en una sociedad convulsionada por una situación tan excepcional como la pandemia.
“Limpar o mundo” em tempos de Covid-19: trabalhadoras domésticas entre a reprodução e a expropriação social
Authors: Teixeira Alessandra , Rodrigues Priscila dos Santos
Published: September 2022

Resumo O objetivo do artigo consiste em pensar o trabalho doméstico remunerado no Brasil em meio à crise pandêmica associada ao novo coronavírus, à luz de perspectivas teóricas que reposicionam, sobre novas bases epistêmicas, as intersecções das opressões de classe, gênero e raça enquanto elementos estruturantes do sistema capitalista. Dados estatísticos mostram o impacto da Covid-19 e da crise econômica subsequente no aprofundamento da desvalorização, precarização e no empobrecimento de trabalhadoras domésticas, em sua maioria mulheres negras, pouco escolarizadas e com baixo acesso a políticas sociais. A pandemia, em suas graves consequências tornou latentes as hierarquias raciais e de gênero, tributárias da experiência da colonialidade e da escravidão, prolongadas e mantidas em permanente reinvenção no contexto brasileiro. Por fim, o artigo, apoiando-se na proposição teórica inovadora de Nancy Fraser a respeito da categoria “expropriação”, propõe aplicá-la em combinação à noção de “reprodução social”, encetada pelo feminismo marxista há mais de quatro décadas, para situar o trabalho doméstico remunerado no encontro dessas duas “condições de possibilidade” do capitalismo contemporâneo.
Educação matemática e a formação do homo oeconomicus
Authors: Souza Jéssica Ignácio de , Flores Cláudia Regina
Published: September 2022

Resumo Uma educação financeira é inserida na agenda global educacional, especialmente pela disseminação de documentos propositivos da Organização para a Cooperação e Desenvolvimento Econômico (OCDE), e se inscreve na Base Nacional Comum Curricular (BNCC) em articulação aos conteúdos da matemática que se ensina na escola. Além disso, há que se notar um interesse no campo da pesquisa em Educação Matemática, que passa a tomar a educação financeira como um importante problema a ser investigado para os processos de ensino e aprendizagem. Neste artigo objetivamos analisar práticas matemáticas historicamente situadas que, em suas conexões, forma o homo oeconomicus, entendido como aquele sujeito requerido ao bom funcionamento da economia, à luz de Michel Foucault. Para isso, analisamos livros didáticos de matemática de outros momentos históricos, coletados no Museu da Escola Catarinense, do Ensino Fundamental, da coleção A conquista da matemática, bem como teses e dissertações que tratam da temática educação financeira. Os procedimentos teórico-metodológicos são inspirados na genealogia, conceito empregado por Michel Foucault. Disso inferimos que permanece na educação matemática uma função econômica que se atualiza: dos conteúdos técnicos, formas de calcular e pensar economicamente a partir do trabalho comerciário e fabril até a primeira metade do século XX, passa-se também a exercitar comportamentos e valores de como consumir, construir orçamentos e poupar no neoliberalismo.
Compreender e compreender-se: o campo educacional brasileiro num itinerário de leituras de Pierre Bourdieu
Authors: Catani Denice Barbara
Published: September 2022

Resumo O texto explicita e analisa uma modalidade de apropriação do pensamento de Pierre Bourdieu, indicando alguns pontos fundamentais para os estudos da área educacional. Remete às possibilidades de entendimento inscritas em sua sociologia no tocante à elaboração dos conhecimentos científicos e aos determinantes do campo, habitus e capitais ligados aos sujeitos e suas posições. Acentua, assim, a íntima conexão entre conhecimento científico e autoconhecimento. Entre seus objetivos, o texto pretende ser útil aos jovens pesquisadores ao mostrar possibilidades de pensamento “com Bourdieu” ao refazer um caso, e chamar a atenção para os problemas da produção dos conhecimentos em educação, histórica e socialmente. Sob a forma de um ensaio e valendo-se desta como método, constrói-se um itinerário pessoal de leituras da obra do autor, salientando duas perspectivas que orientaram as escolhas em diferentes momentos. Uma delas se refere ao desenvolvimento de investigações da história da educação brasileira e outra, aos trabalhos de pesquisa, ensino e intervenção para a formação de professores. Dada a natureza da escrita e a convicção de que são possíveis e desejáveis diversos modos de produção dos estudos educacionais, não se explicitam conclusões, em vez disso, propõe-se a multiplicação de perguntas que se desdobram da construção das ideias e dos percursos do pensamento.
Chilean and Spanish teachers’ beliefs and disposition when teaching writing in the pandemic: a contrastive study
Authors: Ibáñez Ester Trigo , Azagra Marcela Jarpa , Landero Rocío Maraver
Published: September 2022

Abstract National and international researches have shown how students and teachers face the teaching of writing. Nevertheless, the pandemic has created new needs of pedagogical research on topics like the teaching of writing in distance learning processes. The research aims to compare pedagogical experiences and practices a group of Chilean and Spanish teachers had during distance learning in the COVID-19 pandemic times. This is a qualitative study that approaches from a digital ethnographic perspective, and it is circumscribed by the socio-critical paradigm. 20 Chilean and 20 Spanish primary school teachers volunteered to participate. They all confronted distance learning after the pandemic started in March 2020. A semi structured interview was conducted to gather data. The obtained information has been processed with the qualitative data analysis software NVivo 12. The answers of the teachers indicate a general change in the pedagogical practices after the pandemic, particularly in the teaching of writing. However, on the one hand, Chilean teachers are especially concerned about the students, on the other hand Spanish teachers are about training. The need of further training in distance teaching of writing can be detected in both contexts.
SAT-Based Parallel Planning Using a Split Representation of Actions
Authors: Robinson Nathan , Gretton Charles , Pham Duc Nghia , Sattar Abdul
Published: September 2022

Planning based on propositional SAT(isfiability) is a powerful approach to computing step-optimal plans given a parallel execution semantics. In this setting: (i) a solution plan must be minimal in the number of plan steps required, and (ii) non-conflicting actions can be executed instantaneously in parallel at a plan step. Underlying SAT-based approaches is the invocation of a decision procedure on a SAT encoding of a bounded version of the problem. A fundamental limitation of existing approaches is the size of these encodings. This problem stems from the use of a direct representation of actions — i.e. each action has a corresponding variable in the encoding. A longtime goal in planning has been to mitigate this limitation by developing a more compact split — also termed lifted — representation of actions in SAT encodings of parallel step-optimal problems. This paper describes such a representation. In particular, each action and each parallel execution of actions is represented uniquely as a conjunct of variables. Here, each variable is derived from action pre and post-conditions. Because multiple actions share conditions, our encoding of the planning constraints is factored and relatively compact. We find experimentally that our encoding yields a much more efficient and scalable planning procedure over the state-of-the-art in a large set of planning benchmarks.
Exploiting Coordination Locales in Distributed POMDPs via Social Model Shaping
Authors: Varakantham Pradeep , Kwak Jun-young , Taylor Matthew , Marecki Janusz , Scerri Paul , Tambe Milind
Published: September 2022

Distributed POMDPs provide an expressive framework for modeling multiagent collaboration problems, but NEXP-Complete complexity hinders their scalability and application in real-world domains. This paper introduces a subclass of distributed POMDPs, and TREMOR, an algorithm to solve such distributed POMDPs. The primary novelty of TREMOR is that agents plan individually with a single agent POMDP solver and use social model shaping to implicitly coordinate with other agents. Experiments demonstrate that TREMOR can provide solutions orders of magnitude faster than existing algorithms while achieving comparable, or even superior, solution quality.
Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?
Authors: Helmert Malte , Domshlak Carmel
Published: September 2022

Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxations, critical paths, abstractions, and, most recently, landmarks. Previously, these different ideas for deriving heuristic functions were largely unconnected.We prove that admissible heuristics based on these ideas are in fact very closely related. Exploiting this relationship, we introduce a new admissible heuristic called the landmark cut heuristic, which compares favourably with the state of the art in terms of heuristic accuracy and overall performance.
A Decision-Theoretic Approach to Dynamic Sensor Selection in Camera Networks
Authors: Spaan Matthijs , Lima Pedro
Published: September 2022

Nowadays many urban areas have been equipped with networks of surveillance cameras, which can be used for automatic localization and tracking of people. However, given the large resource demands of imaging sensors in terms of bandwidth and computing power, processing the image streams of all cameras simultaneously might not be feasible. In this paper, we consider the problem of dynamical sensor selection based on user-defined objectives, such as maximizing coverage or improved localization uncertainty.  We propose a decision-theoretic approach modeled as a POMDP, which selects k sensors to consider in the next time frame, incorporating all observations made in the past. We show how, by changing the POMDP's reward function, we can change the system's behavior in a straightforward manner, fulfilling the user's chosen objective. We successfully apply our techniques to a network of 10 cameras.
Computing Applicability Conditions for Plans with Loops
Authors: Srivastava Siddharth , Immerman Neil , Zilberstein Shlomo
Published: September 2022

The utility of including loops in plans has been long recognized by the planning community. Loops in a plan help increase both its applicability and the compactness of representation. However, progress in finding such plans has been limited largely due to lack of methods for reasoning about the correctness and safety properties of loops of actions. We present novel algorithms for determining the applicability and progress made by a general class of loops of actions. These methods can be used for directing the search for plans with loops towards greater applicability while guaranteeing termination, as well as in post-processing of computed plans to precisely characterize their applicability. Experimental results demonstrate the efficiency of these algorithms.
A New Approach to Conformant Planning Using CNF∗
Authors: To Son , Son Tran , Pontelli Enrico
Published: September 2022

In this paper, we develop a heuristic, progression based conformant planner, called CNF, which represents belief states by a special type of CNF formulae, called CNF CNF-state. We define a transition function φCNF for computing the successor belief state resulting from the execution of an action in a belief state and prove that it is sound and complete with respect to the complete semantics defined in the literature for conformant planning. We evaluate the performance of CNF against other state-of-the-art conformant planners and identify the classes of problems where CNF is comparable with other state-of-the-art planners or scales up better than other planners. We also develop a technique called oneof relaxation which helps boost the performance of CNF. We characterize the domains where this technique can be applied and validate this idea by proposing a new set of benchmarks that is really difficult for other planners yet easy for CNF.
A PDDL+ Benchmark Problem: The Batch Chemical Plant
Authors: Della Penna Giuseppe , Intrigila Benedetto , Magazzeni Daniele , Mercorio Fabio
Published: September 2022

The PDDL+ language has been mainly devised to allow modelling of real-world systems, with continuous, time-dependant dynamics. Several interesting case studies with these characteristics have been also proposed, to test the language expressiveness and the capabilities of the support tools. However, most of these case studies have not been completely developed so far. In this paper we focus on the batch chemical plant case study, a very complex hybrid system with nonlinear dynamics that could represent a challenging benchmark problem for planning techniques and tools. We present a complete PDDL+ model for such system, and show an example application where the UPMurphi universal planner is used to generate a set of production policies for the plant.
Genome Rearrangement and Planning: Revisited
Authors: Uras Tansel , Erdem Esra
Published: September 2022

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.
Combined Task and Motion Planning for Mobile Manipulation
Authors: Wolfe Jason , Marthi Bhaskara , Russell Stuart
Published: September 2022

We present a hierarchical planning system and its application to robotic manipulation.  The novel features of the system are: 1) it finds high-quality kinematic solutions to task-level problems; 2) it takes advantage of subtask-specific irrelevance information, reusing optimal solutions to state-abstracted subproblems across the search space.  We briefly describe how the system handles uncertainty during plan execution, and present results on discrete problems as well as pick-and-place tasks for a mobile robot.
On Adversarial Search Spaces and Sampling-Based Planning
Authors: Ramanujan Raghuram , Sabharwal Ashish , Selman Bart
Published: September 2022

Upper Confidence bounds applied to Trees (UCT), a bandit-based Monte-Carlo sampling algorithm for planning, has recently been the subject of great interest in adversarial reasoning. UCT has been shown to outperform traditional minimax based approaches in several challenging domains such as Go and Kriegspiel, although minimax search still prevails in other domains such as Chess. This work provides insights into the properties of adversarial search spaces that play a key role in the success or failure of UCT and similar sampling-based approaches. We show that certain "early loss" or "shallow trap" configurations, while unlikely in Go, occur surprisingly often in games like Chess (even in grandmaster games). We provide evidence that UCT, unlike minimax search, is unable to identify such traps in Chess and spends a great deal of time exploring much deeper game play than needed.
Scaling Up Multiagent Planning: A Best-Response Approach
Authors: Jonsson Anders , Rovatsos Michael
Published: September 2022

Multiagent planning is computationally hard in the general case due to the exponential blowup in the action space induced by concurrent action of different agents. At the same time, many scenarios require the computation of plans that are strategically meaningful for self-interested agents, in order to ensure that there would be sufficient incentives for those agents to participate in a joint plan. In this paper, we present a multiagent planning and plan improvement method that is based on conducting iterative best-response planning using standard single-agent planning algorithms. In constrained types of planning scenarios that correspond to congestion games, this is guaranteed to converge to a plan that is a Nash equilibrium with regard to agents' preference profiles over the entire plan space. Our empirical evaluation beyond these restricted scenarios shows, however, that the algorithm has much broader applicability as a method for plan improvement in general multiagent planning problems. Extensive empirical experiments in various domains illustrate the scalability of our method in both cases.
Distributed Control of Situated Assistance in Large Domains with Many Tasks
Authors: Hoey Jesse , Grzes Marek
Published: September 2022

This paper tackles the problem of building situated prompting and assistance systems for guiding a human with a cognitive disability through a large domain containing multiple tasks. This problem is challenging because the target population has difficulty maintaining goals, recalling necessary steps and recognizing objects and potential actions (affordances), and therefore may not appear to be acting rationally. Prompts or cues from an automated system can be very helpful in this regard, but the domain is inherently partially observable due to sensor noise and uncertain human behaviours, making the task of selecting an appropriate prompt very challenging. Prior work has shown how such automated assistance for a single task can be modeled as a partially observable Markov decision process (POMDP). In this paper, we generalise this to multiple tasks, and show how to build a scalable, distributed and hierarchical controller. We demonstrate the algorithm in a set of simulated domains and show it can perform as well as the full model in many cases, and can give solutions to large problems (over 1015 states and 109 observations) for which the full model fails to find a policy.
Learning Inadmissible Heuristics During Search
Authors: Thayer Jordan , Dionne Austin , Ruml Wheeler
Published: September 2022

Suboptimal search algorithms offer shorter solving times by sacrificing guaranteed solution optimality. While optimal searchalgorithms like A* and IDA* require admissible heuristics, suboptimalsearch algorithms need not constrain their guidance in this way. Previous work has explored using off-line training to transform admissible heuristics into more effective inadmissible ones. In this paper we demonstrate that this transformation can be performed on-line, during search. In addition to not requiring training instances and extensive pre-computation, an on-line approach allows the learned heuristic to be tailored to a specific problem instance. We evaluate our techniques in four different benchmark domains using both greedy best-first search and bounded suboptimal search. We find that heuristics learned on-line result in both faster search andbetter solutions while relying only on information readily available in any best-first search.
CP and MIP Methods for Ship Scheduling with Time-Varying Draft
Authors: Kelareva Elena , Brand Sebastian , Kilby Philip , Thiebaux Sylvie , Wallace Mark
Published: September 2022

Existing ship scheduling approaches either ignore constraints on ship draft (distance between the waterline and the keel), or model these in very simple ways, such as a constant draft limit that does not change with time. However, in most ports the draft restriction changes over time due to variation in environmental conditions. More accurate consideration of draft constraints would allow more cargo to be scheduled for transport on the same set of ships. We present constraint programming (CP) and mixed integer programming (MIP) models for the problem of scheduling ships at a port with time-varying draft constraints so as to optimise cargo throughput at the port. We also investigate the effect of several variations to the CP model, including a model containing sequence variables, and a model with ordered inputs. Our model allows us to solve realistic instances of the problem to optimality in a very short time, and produces better schedules than both scheduling with constant draft, and manual scheduling approaches used in practice at ports.
Planning Via Random Walk-Driven Local Search
Authors: Xie Fan , Nakhost Hootan , Müller Martin
Published: September 2022

The ideas of local search and random walks have been used successfully in several recent satisficing planners. Random Walk-Driven Local Search (RW-LS) is a strong new addition to this family of planning algorithms. The method uses a greedy best-first search driven by a combination of random walks and direct node evaluation. In this way, RW-LS balances between exploration and exploitation. The algorithm has been implemented in the system Arvand-LS. Its performance is evaluated against other state of the art planners on problems from IPC-2011, as well as on scaled up instances from several IPC domains. The results show significant improvements in both coverage and plan quality.
ITOMP: Incremental Trajectory Optimization for Real-Time Replanning in Dynamic Environments
Authors: Park Chonhyon , Pan Jia , Manocha Dinesh
Published: September 2022

We present a novel optimization-based algorithm for motion planning in dynamic environments. Our approach uses a stochastic trajectory optimization framework to avoid collisions and satisfy smoothness and dynamics constraints. Our algorithm does not require a priori knowledge about global motion or trajectories of dynamic obstacles. Rather, we compute a conservative local bound on the position or trajectory of each obstacle over a short time and use the bound to compute a collision-free trajectory for the robot in an incremental manner. Moreover, we interleave planning and execution of the robot in an adaptive manner to balance between the planning horizon and responsiveness to obstacle. We highlight the performance of our planner in a simulated dynamic environment with the 7-DOF PR2 robot arm and dynamic obstacles.
Improved Non-Deterministic Planning by Exploiting State Relevance
Authors: Muise Christian , McIlraith Sheila , Beck Christopher
Published: September 2022

We address the problem of computing a policy for fully observable non-deterministic (FOND) planning problems. By focusing on the relevant aspects of the state of the world, we introduce a series of improvements to the previous state of the art and extend the applicability of our planner, PRP, to work in an online setting. The use of state relevance allows our policy to be exponentially more succinct in representing a solution to a FOND problem for some domains. Through the introduction of new techniques for avoiding deadends and determining sufficient validity conditions, PRP has the potential to compute a policy up to several orders of magnitude faster than previous approaches. We also find dramatic improvements over the state of the art in online replanning when we treat suitable probabilistic domains as FOND domains.
Anticipatory On-Line Planning
Authors: Burns Ethan , Benton J. , Ruml Wheeler , Yoon Sungwook , Do Minh
Published: September 2022

We consider the problem of on-line continual planning, in whichadditional goals may arrive while plans for previous goals are stillexecuting and plan quality depends on how quickly goals are achieved.This is a challenging problem even in domains with deterministicactions. One common and straightforward approach is reactive planning,in which plans are synthesized when a new goal arrives. In this paper,we adapt the technique of hindsight optimization from on-line schedulingand probabilistic planning to create an anticipatory on-line planningalgorithm. Using an estimate of the goal arrival distribution, wesample possible futures and use a deterministic planner to estimate thevalue of taking possible actions at each time step. Results in twobenchmark domains based on unmanned aerial vehicle planning andmanufacturing suggest that an anticipatory approach yields a superiorplanner that is sensitive not only to which action should be executed,but when.
Faster Optimal Planning with Partial-Order Pruning
Authors: Hall David , Cohen Alon , Burkett David , Klein Dan
Published: September 2022

When planning problems have many kinds of resources or high concurrency, each optimal state has exponentially many minor variants, some of which are "better" than others. Standard methods like \Astar cannot effectively exploit these minor relative differences, and therefore must explore many redundant, clearly suboptimal plans. We describe a new optimal search algorithm for planning that leverages a partial order relation between states. Under suitable conditions, states that are dominated by other states with respect to this order can be pruned while provably maintaining optimality. We also describe a simple method for automatically discovering compatible partial orders in both serial and concurrent domains. In our experiments we find that more than 98% of search states can be pruned in some domains.
An Approach for Efficient Planning of Robotic Manipulation Tasks
Authors: Dearden Richard , Burbridge Chris
Published: September 2022

Robot manipulation is a challenging task for planning as itinvolves a mixture of symbolic planning and geometric plan-ning. We would like to express goals and many action ef-fects symbolically, for example specifying a goal such as forall x, if x is a cup, then x should be on the tray, but to ac-complish this we may need to plan the geometry of fitting allthe cups on the tray and how to grasp, move and release thecups to achieve that geometry. In the ideal case, this couldbe accomplished by a fully hybrid planner that alternates be-tween geometric and symbolic reasoning to generate a solu-tion. However, in practice this is very complex, and the fullpower of this approach may only be required for a small sub-set of problems. Instead, we plan completely symbolically,and then attempt to generate a geometric plan by translatingthe symoblic predicates into geometric relationships. We thenexecute this plan in simulation, and if it fails, we backtrack,first in geometric space, and then if necessary in symbolic.We show that this approach, while not complete, solves anumber of challenging manipulation problems, and demon-strate it running on a robotic platform.
HTN Planning for the Composition of Stream Processing Applications
Authors: Sohrabi Shirin , Udrea Octavian , Ranganathan Anand , Riabov Anton
Published: September 2022

Goal-driven automated composition of software components is an important problem with applications in Web service composition and stream processing systems. The popular approach to address this problem is to build the composition automatically using AI planning. However, it is shown that some of these planning approaches may neither be feasible nor scalable for many large-scale flow-based applications. Recent advances have proven that the automated composition problem can take advantage of expert knowledge describing the many ways in which different reusable components can be composed. This knowledge can be represented using an extensible composition template or pattern. In prior work, a flow pattern language called Cascade and its corresponding specialized planner have shown the best performance in these domains. In this paper, we propose the use of Hierarchical Task Network (HTN) planning for the composition of stream processing applications. To this end, we propose an automated approach of creating an HTN-based problem from the Cascade representation of the flow patterns. The resulting technique not only allows us to use the HTN planning paradigm and its many advantages including added expressivity but also enables optimization and customization of composition with respect to preferences and constraints. Further, we propose and develop a lookahead heuristic and show that it significantly reduces the planning time. We have performed extensive experimentation with stream processing applications and evaluated applicability and performance of our approach.
Symmetry Breaking: Satisficing Planning and Landmark Heuristics
Authors: Domshlak Carmel , Katz Michael , Shleyfman Alexander
Published: September 2022

Searching for computational tools that can further push the boundary of satisficing planning, we show that reasoning about state-space symmetries can substantially improve even the most effective heuristic-search satisficing planners, with respect to all standard performance measures. The improvement comes from the state-space pruning, as well as from transparent cost-to-state updates and heuristic enhancement by information obtained during the search at different symmetric states.
A Reformulation for the Problem of Scheduling Unrelated Parallel Machines with Sequence and Machine Dependent Setup Times
Authors: Avalos-Rosales Oliver , Alvarez Ada , Angel-Bello Francisco
Published: September 2022

In this paper we propose an improved formulation for an unrelated parallel machine problem with machine and job sequence-dependent setup times that outperforms the previously published formulations regarding size of instances and CPU time to reach optimal solutions. The main difference between the proposed formulation and previous ones is the way the makespan has been linearized. It provides improved dual bounds which speeds up the solution process when using a branch-and-bound commercial solver. Computational experiments show that, using this model, it is possible to solve instances four times larger than what was previously possible using other mixed integer programming formulations in the literature and obtain optimal solutions on instances of the same size up to three orders of magnitude faster.
Counterexample-Guided Cartesian Abstraction Refinement
Authors: Seipp Jendrik , Helmert Malte
Published: September 2022

Counterexample-guided abstraction refinement (CEGAR) is a method for incrementally computing abstractions of transition systems. We propose a CEGAR algorithm for computing abstraction heuristics for optimal classical planning. Starting from a coarse abstraction of the planning task, we iteratively compute an optimal abstract solution, check if and why it fails for the concrete planning task and refine the abstraction so that the same failure cannot occur in future iterations. A key ingredient of our approach is a novel class of abstractions for classical planning tasks that admits efficient and very fine-grained refinement. Our implementation performs tens of thousands of refinement steps in a few minutes and produces heuristics that are often significantly more accurate than pattern database heuristics of the same size.
Computing Solutions in Infinite-Horizon Discounted Adversarial Patrolling Games
Authors: Vorobeychik Yevgeniy , An Bo , Tambe Milind , Singh Satinder
Published: September 2022

Stackelberg games form the core of a number of tools deployed for computing optimal patrolling strategies in adversarial domains, such as the US Federal Air Marshall Service and the US Coast Guard. In traditional Stackelberg security game models the attacker knows only the probability that each target is covered by the defender, but is oblivious to the detailed timing of the coverage schedule. In many real-world situations, however, the attacker can observe the current location of the defender and can exploit this knowledge to reason about the defender’s future moves. We show that this general modeling framework can be captured using adversarial patrolling games (APGs) in which the defender sequentially moves between targets, with moves constrained by a graph, while the attacker can observe the defender’s current location and his (stochastic) policy concerning future moves. We offer a very general model of infinite-horizon discounted adversarial patrolling games. Our first contribution is to show that defender policies that condition only on the previous defense move (i.e., Markov stationary policies) can be arbitrarily suboptimal for general APGs. We then offer a mixed-integer non-linear programming (MINLP) formulation for computing optimal randomized policies for the defender that can condition on history of bounded, but arbitrary, length, as well as a mixed-integer linear programming (MILP) formulation to approximate these, with provable quality guarantees. Additionally, we present a non-linear programming (NLP) formulation for solving zero-sum APGs. We show experimentally that MILP significantly outperforms the MINLP formulation, and is, in turn, significantly outperformed by the NLP specialized to zero-sum games.
Landmark-Based Plan Distance Measures for Diverse Planning
Authors: Bryce Daniel
Published: September 2022

Prior approaches to generating diverse plans in domain-independent  planning seek out variations on plan structure such as actions or  causal links used, or states entered.  Measuring such syntactic  differences between plans can be misleading because syntactically  different plans can be semantically identical.  We develop a  landmark-based plan distance measure that captures semantic  differences between plans.The landmark-based distance measure focuses on the disjunctive landmarks  satisfied by each plan.  We develop a  simple algorithm for finding diverse plans that is based upon the LAMA planner.  We illustrate that, in comparison with plan distance  measures,  landmark-based plan distance is  not as susceptible to including irrelevant or redundant actions in  plans to increase plan distance. Through extensive empirical evaluation, we find that  high landmark distance between plans implies high action set  distance, but not vice versa.  Landmark-based plan distance overcomes some of the weaknesses of syntactic plan distance measures and can be used to find plan sets that are both landmark diverse and action set diverse.
Relaxation Heuristics for Multiagent Planning
Authors: Štolba Michal , Komenda Antonín
Published: September 2022

Similarly to classical planning, in MA-Strips multiagent planning, heuristics significantly improve efficiency of search-based planners. Heuristics based on solving a relaxation of the original planning problem are intensively studied and well understood. In particular, frequently used is the delete relaxation, where all delete effects of actions are omitted. In this paper, we present a unified view on distribution of delete relaxation heuristics for multiagent planning. Until recently, the most common approach to adaptation of heuristics for multiagent planning was to compute the heuristic estimate using only a projection of the problem for a single agent. In this paper, we place such approach in the context of techniques which allow sharing more information among the agents and thus improve the heuristic estimates. We thoroughly experimentally evaluate properties of our distribution of additive, max and Fast-Forward relaxation heuristics in a planner based on distributed Best-First Search. The best performing distributed relaxation heuristics favorably compares to a state-of-the-art MA-Strips planner in terms of benchmark problem coverage. Finally, we analyze impact of limited agent interactions by means of recursion depth of the heuristic estimates.
Plan, Repair, Execute, Explain — How Planning Helps to Assemble your Home Theater
Authors: Bercher Pascal , Biundo Susanne , Geier Thomas , Hoernle Thilo , Nothdurft Florian , Richter Felix , Schattenberg Bernd
Published: September 2022

In various social, work-related, or educational contexts, an increasing demand for intelligent assistance systems can be observed. In this paper, we present a domain-independent approach that combines a number of planning and interaction components to realize advanced user assistance. Based on a hybrid planning formalism, the components provide facilities including the generation, execution, and repair as well as the presentation and explanation of plans. We demonstrate the feasibility of our approach by means of a system that aims to assist users in the assembly of their home theater. An empirical evaluation shows the benefit of such a supportive system, in particular for persons with a lack of domain expertise.
Planning in Action Language BC while Learning Action Costs for Mobile Robots
Authors: Khandelwal Piyush , Yang Fangkai , Leonetti Matteo , Lifschitz Vladimir , Stone Peter
Published: September 2022

The action language BC provides an elegant way of formalizing dynamic domains which involve indirect effects of actions and recursively defined fluents. In complex robot task planning domains, it may be necessary for robots to plan with incomplete information, and reason about indirect or recursive action effects. In this paper, we demonstrate how BC can be used for robot task planning to solve these issues. Additionally, action costs are incorporated with planning to produce optimal plans, and we estimate these costs from experience making planning adaptive. This paper presents the first application of BC on a real robot in a realistic domain, which involves human-robot interaction for knowledge acquisition, optimal plan generation to minimize navigation time, and learning for adaptive planning.
Improved Features for Runtime Prediction of Domain-Independent Planners
Authors: Fawcett Chris , Vallati Mauro , Hutter Frank , Hoffmann Jörg , Hoos Holger , Leyton-Brown Kevin
Published: September 2022

State-of-the-art planners often exhibit substantial runtime variation, making it useful to be able to efficiently predict how long a given planner will take to run on a given instance. In other areas of AI, such needs are met by building so-called empirical performance models (EPMs), statistical models derived from sets of problem instances and performance observations. Historically, such models have been less accurate for predicting the running times of planners. A key hurdle has been a relative weakness in instance features for characterizing instances: mappings from problem instances to real numbers that serve as the starting point for learning an EPM. We propose a new, extensive set of instance features for planning, and investigate its effectiveness across a range of model families. We built EPMs for various prominent planning systems on several thousand benchmark problems from the planning literature and from IPC benchmark sets, and conclude that our models predict runtime much more accurately than the previous state of the art. We also study the relative importance of these features.
Contingent versus Deterministic Plans in Multi-Modal Journey Planning
Authors: Botea Adi , Braghin Stefano
Published: September 2022

Deterministic planning is the de facto standard in deployed multi-modal journey planning systems. However, in reality, transportation networks feature many types of uncertainty, including variations of the arrival and the departure times of public transport vehicles. Under uncertainty, deterministic plans could result in missed connections, leading to an arrival time much worse than originally planned. We contribute an empirical study using transportation network data from three European cities. We show that, in the presence of uncertainty, contingent plans can often provide significant savings in terms of travel time. We view our results as important because they advocate adopting uncertainty-aware multi-modal journey plans, shifting from the current practice based on using deterministic planning.
Robust Execution of Plans for Human-Robot Teams
Authors: Karpas Erez , Levine Steven , Yu Peng , Williams Brian
Published: September 2022

Humans and robots working together can efficiently complete tasks that are very difficult for either to accomplish alone. To collaborate fluidly, robots must recognize the humans' intentions and adapt to their actions appropriately. Pike is an online executive introduced previously in the literature that unifies intent recognition and plan adaptation for temporally flexible plans with choice. While successful at coordinating human-robot teams, Pike had limited robustness to temporal uncertainty about the durations of actions. This paper presents two extensions to Pike that make it much more robust to temporal uncertainty. First, we extend Pike to handle uncontrollable action durations by enforcing strong temporal controllability. We accomplish this by generalizing standard strong controllability algorithms for STNUs to plans with choice. Second, in case a realized duration exceeds even the specified bounds and makes the entire plan infeasible, we attempt to intelligently negotiate with a human to relax some of the temporal constraints and restore feasibility, rather than immediately failing and halting execution. This negotiation is guided by a state-of-the-art conflict directed relaxation algorithm, which has previously only been used offline.
PLEASE: Palm Leaf Search for POMDPs with Large Observation Spaces
Authors: Zhang Zongzhang , Hsu David , Lee Wee Sun , Lim Zhan Wei , Bai Aijun
Published: September 2022

Trial-based asynchronous value iteration algorithms for large Partially Observable Markov Decision Processes (POMDPs), such as HSVI2, FSVI and SARSOP, have made impressive progress in the past decade. In the forward exploration phase of these algorithms, only the outcome that has the highest potential impact is searched. This paper provides a novel approach, called Palm LEAf SEarch (PLEASE), which allows the selection of more than one outcome when their potential impacts are close to the highest one. Compared with existing trial-based algorithms, PLEASE can save considerable time to propagate the bound improvements of beliefs in deep levels of the search tree to the root belief because of fewer point-based value backups. Experiments show that PLEASE scales up SARSOP, one of the fastest algorithms, by orders of magnitude on some POMDP tasks with large observation spaces.
A Normal Form for Classical Planning Tasks
Authors: Pommerening Florian , Helmert Malte
Published: September 2022

We describe transition normal form (TNF) for classical planning tasks, where there is a unique goal state and variables occur in an operator precondition iff they appear in the effect. Tasks can be efficiently converted to TNF, all common planning heuristics are invariant under the transformation, and tasks in normal form are easier to study theoretically.
A Multi-Parameter Complexity Analysis of Cost-Optimal and Net-Benefit Planning
Authors: Aghighi Meysam , Backstrom Christer
Published: September 2022

Aghighi and Bäckström have previously studied cost-optimal planning (COP) and net-benefit planning (NBP) for three action cost domains: the positive integers (Z_+), the non-negative integers (Z_0) and the positive rationals (Q_+). These were indistinguishable under standard complexity analysis for both problems, but separated for COP using parameterised complexity analysis. With the plan cost, k, as parameter, COP was W[2]-complete for Z_+, but para-NP-hard for both Z_0 and Q_+, i.e. presumably much harder. NBP was para-NP-hard for all three domains, thus remaining unseparable. We continue by considering combinations with several additional parameters and also the non-negative rationals (Q_0). Examples of new parameters are the plan length, l, and the largest denominator of the action costs, d. Our findings include: (1) COP remains W[2]-hard for all domains, even if combining all parameters; (2) COP for Z_0 is in W[2] for the combined parameter {k,l}; (3) COP for Q_+ is in W[2] for {k,d} and (4) COP for Q_0 is in W[2] for {k,d,l}. For NBP we consider further additional parameters, where the most crucial one for reducing complexity is the sum of variable utilities. Our results help to understand the previous results, eg. the separation between Z_+ and Q_+ for COP, and to refine the previous connections with empirical findings.
Strict Theta*: Shorter Motion Path Planning Using Taut Paths
Authors: Oh Shunhao , Leong Hon Wai
Published: September 2022

A common way to represent dynamic 2D open spaces in robotics and video games for any-angle path planning is through the use of a grid with blocked and unblocked cells. The Basic Theta* algorithm is an existing algorithm that produces near-optimal solutions with a running time close to A* on 8-directional grids. However, a disadvantage is that it often finds non-taut paths that make unnecessary turns. In this paper, we demonstrate that by restricting the search space of Theta* to taut paths, the algorithm will, in most cases, find much shorter paths than the original. We describe two novel variants of the Theta* algorithm, which are simple to implement and use, yet produce a remarkable improvement over Theta* in terms of path length, with a very small running time trade-off. Another side benefit is that almost all paths found will be taut, which makes more convincing paths.