Increased space sensing enables new measurements of a wide range of Earth science phenomena including volcanism, flooding, wildfires, and weather. Large-scale observation constellations of hundreds of assets have alre...
详细信息
Increased space sensing enables new measurements of a wide range of Earth science phenomena including volcanism, flooding, wildfires, and weather. Large-scale observation constellations of hundreds of assets have already been deployed (for example, Planet Labs's Dove satellites), and several constellations of tens of thousands of assets are planned. New challenges exist to rapidly assimilate available data and to optimize measurements by directing spacecraft assets to best observe complex Earth science phenomena. Centralized approaches to managing request allocation in these large constellations are constrained by 1) the need to assign/elect a central node to assign requests to spacecraft and 2) reliance on a single agent communicating with potentially thousands of dependent agents. On the other hand, entirely decentralized approaches to request allocation and observation are prone to oversatisfaction of some requests and undersatisfaction of others due to a lack of communication among agents. In large constellations, an intermediary method is necessary to solve the request allocation problem in a distributed manner. We present distributed artificial intelligence/multiagent methods that leverage existing work on distributed constraint optimization to allocate observations in a satellite constellation. We compare their performance to centralized and highly decentralized approaches using realistic orbits and observation request distributions. Our distributed algorithms can find approximate solutions to the large-scale constellation request allocation problem with low data volume for agent coordination and extend to continuous planning problems with varying request sets and availability of spacecraft agents.
This paper examines whether undergraduate students perform better and experience lower cognitive load when programming in Algot, a visual programming language that supports programming by demonstration, than in the te...
详细信息
ISBN:
(纸本)9798400704239
This paper examines whether undergraduate students perform better and experience lower cognitive load when programming in Algot, a visual programming language that supports programming by demonstration, than in the textual programming language Python. We recruited 38 first-semester computer science university students who had received prior instruction in the programming language Python but were unfamiliar with Algot. Participants reviewed a 12-minute video tutorial about Algot and performed the same programming tasks in Python and Algot. We graded student submissions, estimated cognitive load through physiological measures and a validated post-test survey, and evaluated free-form feedback. Our results indicated that students experienced lower negative (extraneous and intrinsic) and higher positive (germane) cognitive load when programming in Algot. Additionally, students programming in Algot scored an average grade of 5.8 out of 10, compared to an average grade of 3.4 when using Python for the same tasks, and according to the free-form feedback, Algot is perceived as well-designed and easy to learn.
We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachabili...
详细信息
We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed in O(n log n) expected time and space to answer reachability queries in O(log n) time. Furthermore, we present a series of strings that require circle minus(n root n) time and space to answer reachability queries in O(log n) time for the same algorithm. Exhaustive computational calculations for strings of length n <= 33 have revealed that the same strings are also the worst case instances of the algorithm. We therefore conjecture that reachability queries can be answered in O(log n) time with a worst case time and space preprocessing complexity of circle minus(n root n).
We study the parameterized complexity of the directed variant of the classical STEINER TREE problem on various classes of directed sparse graphs. While the parameterized complexity of STEINER TREE parameterized by the...
详细信息
We study the parameterized complexity of the directed variant of the classical STEINER TREE problem on various classes of directed sparse graphs. While the parameterized complexity of STEINER TREE parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected STEINER TREE problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for DIRECTED STEINER TREE (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for DOMINATING SET on sparse undirected graphs. These algorithms are asymptotically optimal.
We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are ...
详细信息
We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it;for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily;see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005)[4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gasieniec et al. (2008) [7] to be no more than 3.75n - 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most (4 + 1/3)n - 4 for oblivious agents and a period length of at most 3.5n - 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n - 2, on the period length for the oblivious case. (c) 2012 Elsevier B.V. All rights reserved.
暂无评论