Search

We propose a design for a functional programming language for autonomous agents, built off the ideas and motivations of Behavior Trees (BTs). BTs are a popular model for designing agents behavior in robotics and AI. However, as their growth has increased dramatically, the simple model of BTs has come to be limiting. There is a growing push to increase the functionality of BTs, with the end goal of BTs evolving into a programming language in their own right, centred around the defining BT properties of modularity and reactiveness. In this paper, we examine how the BT model must be extended in order to grow into such a language. We identify some fundamental problems which must be solved: implementing `reactive' selection, 'monitoring' safety-critical conditions, and passing data between actions. We provide a variety of small examples which demonstrate that these problems are complex, and that current BT approaches do not handle them in a manner consistent with modularity. We instead provide a simple set of modular programming primitives for handling these use cases, and show how they can be combined to build complex programs. We present a full specification for our BT-inspired language, and give an implementation in the functional programming language Haskell. Finally, we demonstrate our language by translating a large and complex BT into a simple, unambiguous program.

In regulatory proceedings, few issues are more hotly debated than the cost of capital. This article formalises the theoretical foundation of cost of capital estimation for regulatory purposes. Several common regulatory practices lack a solid foundation in the theory. For example, the common practice of estimating a single cost of capital for the regulated firm suffers from a circularity problem, especially in the context of a multi-year regulatory period. In addition, the relevant cost of debt cannot be estimated using the yield-to-maturity on a corporate bond. We suggest possible directions for reform of cost of capital practices in regulatory proceedings., Comment: 33 pages, 3 tables, 2 figures

In this paper we characterise the long-run behaviour of the replicator dynamic in zero-sum games (symmetric or non-symmetric). Specifically, we prove that every zero-sum game possesses a unique global replicator attractor, which we then characterise. Most surprisingly, this attractor depends only on each player's preference order over their own strategies and not on the cardinal payoff values, defined by a finite directed graph we call the game's preference graph. When the game is symmetric, this graph is a tournament whose nodes are strategies; when the game is not symmetric, this graph is the game's response graph. We discuss the consequences of our results on chain recurrence and Nash equilibria., Comment: 17 pages, 2 figures. Accepted version, to appear at ALT 2024

In this paper we examine the relationship between the flow of the replicator dynamic, the continuum limit of Multiplicative Weights Update, and a game's response graph. We settle an open problem establishing that under the replicator, sink chain components -- a topological notion of long-run outcome of a dynamical system -- always exist and are approximated by the sink connected components of the game's response graph. More specifically, each sink chain component contains a sink connected component of the response graph, as well as all mixed strategy profiles whose support consists of pure profiles in the same connected component, a set we call the content of the connected component. As a corollary, all profiles are chain recurrent in games with strongly connected response graphs. In any two-player game sharing a response graph with a zero-sum game, the sink chain component is unique. In two-player zero-sum and potential games the sink chain components and sink connected components are in a one-to-one correspondence, and we conjecture that this holds in all games., Comment: 22 pages, 2 figures. Accepted version. To appear in Algorithmic Learning Theory 2023

In this paper we analyse two-player games by their response graphs. The response graph has nodes which are strategy profiles, with an arc between profiles if they differ in the strategy of a single player, with the direction of the arc indicating the preferred option for that player. Response graphs, and particularly their sink strongly connected components, play an important role in modern techniques in evolutionary game theory and multi-agent learning. We show that the response graph is a simple and well-motivated model of strategic interaction which captures many non-trivial properties of a game, despite not depending on cardinal payoffs. We characterise the games which share a response graph with a zero-sum or potential game respectively, and demonstrate a duality between these sets. This allows us to understand the influence of these properties on the response graph. The response graphs of Matching Pennies and Coordination are shown to play a key role in all two-player games: every non-iteratively-dominated strategy takes part in a subgame with these graph structures. As a corollary, any game sharing a response graph with both a zero-sum game and potential game must be dominance-solvable. Finally, we demonstrate our results on some larger games., Comment: 16 pages, 11 figures

One in five Americans, or about 60 million people, lives in a rural area. Because 97% of the nation's landmass is considered rural, by definition these areas are sparsely populated and far from urban centers (United States Census Bureau, 2017). Although rural school districts are small--median enrollment is fewer than 500 students--the overall numbers are not: 28.5% of schools are rural and 9.3 million students attend them (Showalter, Hartman, Johnson, & Klein, 2019). The well-being and success of rural students is a critical determinant of the well-being and success of the nation as a whole. However one of the commonalities connecting rural areas is a lack of access to services, infrastructure, and equitable policies and practices. This article provides an overview of how equity relates to rural America and its students and schools. It examines racial diversity, poverty, intersecting discrimination, resource allocation for schools, broadband connectivity, access to high-quality child care, health services, and other topics impacting families in rural areas.

In this paper we develop an analogue of the graph-theoretic `modular decomposition' in automata theory. This decomposition allows us to identify hierarchical finite state machines (HFSMs) equivalent to a given finite state machine (FSM). We first define a module of an FSM, which is a collection of nodes which can be treated as a nested FSM. We then identify a natural subset of FSM modules called thin modules, which are algebraically well-behaved. We construct a linear-space directed graph, which uniquely represents every thin module, and hence every equivalent (thin) HFSM. We call this graph the modular decomposition. The modular decomposition makes clear the significant common structure underlying equivalent HFSMs, and allows us to efficiently construct equivalent HFSMs. Finally, we provide an $O(n^2k)$ algorithm for constructing the modular decomposition of an $n$-state $k$-symbol FSM., Comment: 28 pages, 5 figures. This version shortens and restructures the paper

In this paper we provide a formal framework for comparing the expressive power of Behavior Trees (BTs) to other action selection architectures. Taking inspiration from the analogous comparisons of structural programming methodologies, we formalise the concept of `expressiveness'. This leads us to an expressiveness hierarchy of control architectures, which includes BTs, Decision Trees (DTs), Teleo-reactive Programs (TRs) and Finite State Machines (FSMs). By distinguishing between BTs with auxiliary variables and those without, we demonstrate the existence of a trade-off in BT design between readability and expressiveness. We discuss what this means for BTs in practice., Comment: 8 pages, 2 figures. Accepted to IEEE Robotics and Automation Letters

Modularity is a central principle throughout the design process for cyber-physical systems. Modularity reduces complexity and increases reuse of behavior. In this paper we pose and answer the following question: how can we identify independent `modules' within the structure of reactive control architectures? To this end, we propose a graph-structured control architecture we call a decision structure, and show how it generalises some reactive control architectures which are popular in Artificial Intelligence (AI) and robotics, specifically Teleo-Reactive programs (TRs), Decision Trees (DTs), Behavior Trees (BTs) and Generalised Behavior Trees ($k$-BTs). Inspired by the definition of a module in graph theory, we define modules in decision structures and show how each decision structure possesses a canonical decomposition into its modules. We can naturally characterise each of the BTs, $k$-BTs, DTs and TRs by properties of their module decomposition. This allows us to recognise which decision structures are equivalent to each of these architectures in quadratic time. Our proposed concept of modules extends to formal verification, under any verification scheme capable of verifying a decision structure. Namely, we prove that a modification to a module within a decision structure has no greater flow-on effects than a modification to an individual action within that structure. This enables verification on modules to be done locally and hierarchically, where structures can be verified and then repeatedly locally modified, with modules replaced by modules while preserving correctness. To illustrate the findings, we present an example of a solar-powered drone controlled by a decision structure. We use a Linear Temporal Logic-based verification scheme to verify the correctness of this structure, and then show how one can modify modules while preserving its correctness., Comment: Accepted to ACM Transactions on Cyber-Physical Systems. 26 pages, 9 figures. Version 3 changes: accepted version, minor changes

As complex autonomous robotic systems become more widespread, the need for transparent and reusable Artificial Intelligence (AI) designs becomes more apparent. In this paper we analyse how the principles behind Behavior Trees (BTs), an increasingly popular tree-structured control architecture, are applicable to these goals. Using structured programming as a guide, we analyse the BT principles of reactiveness and modularity in a formal framework of action selection. Proceeding from these principles, we review a number of challenging use cases of BTs in the literature, and show that reasoning via these principles leads to compatible solutions. Extending these arguments, we introduce a new class of control architectures we call generalised BTs or $k$-BTs and show how they can extend the applicability of BTs to some of the aforementioned challenging BT use cases while preserving the BT principles., Comment: 13 pages, 11 figures. The content of the previous version is now split between this and arXiv:2104.07919, which have both been significantly updated

The usual advantages put forward for including nullability declarations in the type systems of programming languages are that they improve program reliability or performance. But there is another, entirely different, reason for doing so. In the right context, this information enables the software artifacts we produce, the objects and methods, to exhibit much greater malleability. For declaratively typed languages, we can obtain greater software malleability by extending the model of method call so that assurance of a method's availability can be provided by any non-nullable parameter, not simply the target parameter, and by allowing the method's implementation to reside in classes or objects other than the target.. This paper examines the question of whether this hypothetical improvement in software malleability is consistent with existing programming practice by examining the question of the extent to which methods in existing software have multiplicities of non-nullable parameters. The circumstance occurs frequently enough to provide an important reason to introduce declarations of nullability into programming languages.

The Netherlands has been characterized by highly differentiated secondary education, with separate practical, vocational, secondary, and pre-university institutions. Over time, these have converged somewhat. Well-thought-out vocational and adult programs emphasize providing skills needed in the workplace. At least part-time education is compulsory until age 18. The Netherlands has recently introduced student loans in university and vocational education. The most innovative aspect of a growing emphasis on private funding in post-compulsory education is introduction of performance-contingent grants that are converted into income-contingent loans if students fail to perform satisfactorily. The Netherlands is characterized by high rates of mandatory and notional savings and relatively low rates of discretionary savings. Notional savings displace discretional savings strongly; motives for saving mainly concern health-related and general uncertainties, not job loss or pension income uncertainty. There is no direct evidence of saving for learning. Increased costs of education to students and parents since 1996 have not led to increased savings. Short-term effects have been that many students have chosen to increase their hours of paid work during study, some take student loans, and a minority postpone or avoid studying. (Appendixes include a report on saving, borrowing, and investment and a 10-item bibliography.) (YLB)

This report compares education systems, incentives, and evidence of saving for education in four countries--Denmark, Japan, New Zealand, and the United States--with implications for the United Kingdom. The report's objective is to identify evidence of saving for education in each comparator country, along with government policies and mechanisms that provide incentives for individuals or families to save for education. The report begins with an overview of the education system in each country to better understand the importance of education and its impact on household finances. The next section offers an overview of theories of household saving and outlines trends in saving rates for each country. The next section discusses forms of saving for education. Results of analyses show that the most important determinant of saving for education is simply the cost of education. Therefore, if the costs were to rise in the UK, there would be a rise in saving for education. Also, tax breaks to encourage saving for education in the UK are unlikely to alter saving patterns. Individuals tend to save regardless of whether tax incentives are in place. (Contains a glossary, 4 appendices, 7 Internet resources, 11 tables, 14 figures, and 37 references.) (WFA)

This study contains analyses of trends in the level of university research and development expenditures in the sciences and engineering from 1964 through 1973. The report is divided into three main sections: (1) current research and development expenditures in the sciences and engineering; (2) capital expenditures for research, development, and instruction in the sciences and engineering; and (3) current direct expenditures for instruction and departmental research in graduate-degree-granting institutions in the sciences and engineering. Statistical tables show current research and development allocations according to: (1) source of funds, (2) type of research and development activity, (3) field of science, (4) type of control, (5) type of institution, (6) geographic distribution, and (7) concentration of research and development expenditures. The study also distinguishes between universities and colleges and federally-funded research and development centers administered by universities and colleges in the reporting of data. (Author/CP)