A review of travel time estimation and forecasting for advanced traveler information systems

Providing on line travel time information to commuters has become an important issue for Advanced Traveler Information Systems and Route Guidance Systems in the past years, due to the increasing traffic volume and congestion in the road networks. Travel time is one of the most useful traffic variables because it is more intuitive than other traffic variables such as flow, occupancy or density, and is useful for travelers in decision making. The aim of this paper is to present a global view of the literature on the modeling of travel time, introducing crucial concepts and giving a thorough classification of the existing tech- niques. Most of the attention will focus on travel time estimation and travel time prediction, which are generally not presented together. The main goals of these models, the study areas and methodologies used to carry out these tasks will be further explored and categorized.

Invariant-free deduction systems for temporal logic

In this thesis we propose a new approach to deduction methods for temporal logic. Our proposal is based on an inductive definition of eventualities that is different from the usual one. On the basis of this non-customary inductive definition for eventualities, we first provide dual systems of tableaux and sequents for Propositional Linear-time Temporal Logic (PLTL). Then, we adapt the deductive approach introduced by means of these dual tableau and sequent systems to the resolution framework and we present a clausal temporal resolution method for PLTL. Finally, we make use of this new clausal temporal resolution method for establishing logical foundations for declarative temporal logic programming languages. The key element in the deduction systems for temporal logic is to deal with eventualities and hidden invariants that may prevent the fulfillment of eventualities. Different ways of addressing this issue can be found in the works on deduction systems for temporal logic. Traditional tableau systems for temporal logic generate an auxiliary graph in a first pass.Then, in a second pass, unsatisfiable nodes are pruned. In particular, the second pass must check whether the eventualities are fulfilled. The one-pass tableau calculus introduced by S. Schwendimann requires an additional handling of information in order to detect cyclic branches that contain unfulfilled eventualities. Regarding traditional sequent calculi for temporal logic, the issue of eventualities and hidden invariants is tackled by making use of a kind of inference rules (mainly, invariant-based rules or infinitary rules) that complicates their automation. A remarkable consequence of using either a two-pass approach based on auxiliary graphs or aone-pass approach that requires an additional handling of information in the tableau framework, and either invariant-based rules or infinitary rules in the sequent framework, is that temporal logic fails to carry out the classical correspondence between tableaux and sequents. In this thesis, we first provide a one-pass tableau method TTM that instead of a graph obtains a cyclic tree to decide whether a set of PLTL-formulas is satisfiable. In TTM tableaux are classical-like. For unsatisfiable sets of formulas, TTM produces tableaux whose leaves contain a formula and its negation. In the case of satisfiable sets of formulas, TTM builds tableaux where each fully expanded open branch characterizes a collection of models for the set of formulas in the root. The tableau method TTM is complete and yields a decision procedure for PLTL. This tableau method is directly associated to a one-sided sequent calculus called TTC. Since TTM is free from all the structural rules that hinder the mechanization of deduction, e.g. weakening and contraction, then the resulting sequent calculus TTC is also free from this kind of structural rules. In particular, TTC is free of any kind of cut, including invariant-based cut. From the deduction system TTC, we obtain a two-sided sequent calculus GTC that preserves all these good freeness properties and is finitary, sound and complete for PLTL. Therefore, we show that the classical correspondence between tableaux and sequent calculi can be extended to temporal logic. The most fruitful approach in the literature on resolution methods for temporal logic, which was started with the seminal paper of M. Fisher, deals with PLTL and requires to generate invariants for performing resolution on eventualities. In this thesis, we present a new approach to resolution for PLTL. The main novelty of our approach is that we do not generate invariants for performing resolution on eventualities. Our method is based on the dual methods of tableaux and sequents for PLTL mentioned above. Our resolution method involves translation into a clausal normal form that is a direct extension of classical CNF. We first show that any PLTL-formula can be transformed into this clausal normal form. Then, we present our temporal resolution method, called TRS-resolution, that extends classical propositional resolution. Finally, we prove that TRS-resolution is sound and complete. In fact, it finishes for any input formula deciding its satisfiability, hence it gives rise to a new decision procedure for PLTL. In the field of temporal logic programming, the declarative proposals that provide a completeness result do not allow eventualities, whereas the proposals that follow the imperative future approach either restrict the use of eventualities or deal with them by calculating an upper bound based on the small model property for PLTL. In the latter, when the length of a derivation reaches the upper bound, the derivation is given up and backtracking is used to try another possible derivation. In this thesis we present a declarative propositional temporal logic programming language, called TeDiLog, that is a combination of the temporal and disjunctive paradigms in Logic Programming. We establish the logical foundations of our proposal by formally defining operational and logical semantics for TeDiLog and by proving their equivalence. Since TeDiLog is, syntactically, a sublanguage of PLTL, the logical semantics of TeDiLog is supported by PLTL logical consequence. The operational semantics of TeDiLog is based on TRS-resolution. TeDiLog allows both eventualities and always-formulas to occur in clause heads and also in clause bodies. To the best of our knowledge, TeDiLog is the first declarative temporal logic programming language that achieves this high degree of expressiveness. Since the tableau method presented in this thesis is able to detect that the fulfillment of an eventuality is prevented by a hidden invariant without checking for it by means of an extra process, since our finitary sequent calculi do not include invariant-based rules and since our resolution method dispenses with invariant generation, we say that our deduction methods are invariant-free.

Panel discussion: U.S. EPA using modeling and ecosystem services to enhance coastal decision making

This panel will discuss the research being conducted, and the models being used in three current coastal EPA studies being conducted on ecosystem services in Tampa Bay, the Chesapeake Bay and the Coastal Carolinas. These studies are intended to provide a broader and more comprehensive approach to policy and decision-making affecting coastal ecosystems as well as provide an account of valued services that have heretofore been largely unrecognized. Interim research products, including updated and integrated spatial data, models and model frameworks, and interactive decision support systems will be demonstrated to engage potential users and to elicit feedback. It is anticipated that the near-term impact of the projects will be to increase the awareness by coastal communities and coastal managers of the implications of their actions and to foster partnerships for ecosystem services research and applications. (PDF contains 4 pages)

Using climate extension to assist coastal decision-makers with climate adaptation

Coastal managers need accessible, trusted, tailored resources to help them interpret climate information, identify vulnerabilities, and apply climate information to decisions about adaptation on regional and local levels. For decades, climate scientists have studied the impacts that short term natural climate variability and long term climate change will have on coastal systems. For example, recent estimates based on Intergovernmental Panel on Climate Change (IPCC) warming scenarios suggest that global sea levels may rise 0.5 to 1.4 meters above 1990 levels by 2100 (Rahmstorf 2007; Grinsted, Moore, and Jevrejeva 2009). Many low-lying coastal ecosystems and communities will experience more frequent salt water intrusion events, more frequent coastal flooding, and accelerated erosion rates before they experience significant inundation. These changes will affect the ways coastal managers make decisions, such as timing surface and groundwater withdrawals, replacing infrastructure, and planning for changing land use on local and regional levels. Despite the advantages, managers’ use of scientific information about climate variability and change remains limited in environmental decision-making (Dow and Carbone 2007). Traditional methods scientists use to disseminate climate information, like peer-reviewed journal articles and presentations at conferences, are inappropriate to fill decision-makers’ needs for applying accessible, relevant climate information to decision-making. General guides that help managers scope out vulnerabilities and risks are becoming more common; for example, Snover et al. (2007) outlines a basic process for local and state governments to assess climate change vulnerability and preparedness. However, there are few tools available to support more specific decision-making needs. A recent survey of coastal managers in California suggests that boundary institutions can help to fill the gaps between climate science and coastal decision-making community (Tribbia and Moser 2008). The National Sea Grant College Program, the National Oceanic and Atmospheric Administration's (NOAA) university-based program for supporting research and outreach on coastal resource use and conservation, is one such institution working to bridge these gaps through outreach. Over 80% of Sea Grant’s 32 programs are addressing climate issues, and over 60% of programs increased their climate outreach programming between 2006 and 2008 (National Sea Grant Office 2008). One way that Sea Grant is working to assist coastal decision-makers with using climate information is by developing effective methods for coastal climate extension. The purpose of this paper is to discuss climate extension methodologies on regional scales, using the Carolinas Coastal Climate Outreach Initiative (CCCOI) as an example of Sea Grant’s growing capacities for climate outreach and extension. (PDF contains 3 pages)

Distributed optimization in power networks and general multi-agent systems

The dissertation studies the general area of complex networked systems that consist of interconnected and active heterogeneous components and usually operate in uncertain environments and with incomplete information. Problems associated with those systems are typically large-scale and computationally intractable, yet they are also very well-structured and have features that can be exploited by appropriate modeling and computational methods. The goal of this thesis is to develop foundational theories and tools to exploit those structures that can lead to computationally-efficient and distributed solutions, and apply them to improve systems operations and architecture.

Specifically, the thesis focuses on two concrete areas. The first one is to design distributed rules to manage distributed energy resources in the power network. The power network is undergoing a fundamental transformation. The future smart grid, especially on the distribution system, will be a large-scale network of distributed energy resources (DERs), each introducing random and rapid fluctuations in power supply, demand, voltage and frequency. These DERs provide a tremendous opportunity for sustainability, efficiency, and power reliability. However, there are daunting technical challenges in managing these DERs and optimizing their operation. The focus of this dissertation is to develop scalable, distributed, and real-time control and optimization to achieve system-wide efficiency, reliability, and robustness for the future power grid. In particular, we will present how to explore the power network structure to design efficient and distributed market and algorithms for the energy management. We will also show how to connect the algorithms with physical dynamics and existing control mechanisms for real-time control in power networks.

The second focus is to develop distributed optimization rules for general multi-agent engineering systems. A central goal in multiagent systems is to design local control laws for the individual agents to ensure that the emergent global behavior is desirable with respect to the given system level objective. Ideally, a system designer seeks to satisfy this goal while conditioning each agent’s control on the least amount of information possible. Our work focused on achieving this goal using the framework of game theory. In particular, we derived a systematic methodology for designing local agent objective functions that guarantees (i) an equivalence between the resulting game-theoretic equilibria and the system level design objective and (ii) that the resulting game possesses an inherent structure that can be exploited for distributed learning, e.g., potential games. The control design can then be completed by applying any distributed learning algorithm that guarantees convergence to the game-theoretic equilibrium. One main advantage of this game theoretic approach is that it provides a hierarchical decomposition between the decomposition of the systemic objective (game design) and the specific local decision rules (distributed learning algorithms). This decomposition provides the system designer with tremendous flexibility to meet the design objectives and constraints inherent in a broad class of multiagent systems. Furthermore, in many settings the resulting controllers will be inherently robust to a host of uncertainties including asynchronous clock rates, delays in information, and component failures.