Publications

T-HTN: Timeline based HTN Planning for Multiple Robots

Published in ICAPS | Hierarchical Planning, 2022

Effective coordinated actions by a team of robots operating in close proximity to one another is an important requirement in many emerging applications, ranging from warehousing and material movement to the conduct of autonomous house-keeping and maintenance of deep space habitats during unmanned periods. Yet, such multi-robot planning problems remain a significant challenge for contemporary planning technologies, due to several complicating factors: goals must be assigned to robots and accomplished over time in the presence of complex temporal and spatial constraints in a manner that optimizes overall team performance, attention must be given to the durational uncertainty inherent in robot task execution, and planning must be responsive to changing and unexpected execution circumstances. In this paper, we present T-HTN, a novel planner that attempts to overcome this challenge by coupling the structure and efficiency of Hierarchical Task Network (HTN) models with the flexible scheduling infrastructure of timeline-based planning systems. We present initial results on a simple set of multi-robot problems that show the potential of T-HTN in comparison to a state-of-the-art PDDL-style temporal planner.

T-HTN: Timeline based HTN Planning for Multi-Agent Systems

Published in Thesis | Carnegie Mellon University, 2021

Planning in mission-critical systems like deep-space habitats with onboard robotic systems must be robust to unforeseen circumstances. Such systems are expected to complete a set of goals with different deadlines each day for routine maintenance while also accounting for emergencies. With the presence of humans within the habitat, the robotic systems can be required to perform specific tasks while possibly collaborating with the humans. Further, since the habitat can support multiple robots, this becomes a source of contention as they have to share the limited set of onboard resources. This dynamic between the humans, robots, and the habitat generates a complex system where failures at any level can cause significant delays leading to temporal uncertainty. Such delays can have huge implications depending on whether or not the delay causes the system to miss a goal’s deadline. Hence, it becomes crucial for the planner to address the overall schedule within the context of the current temporal deadlines of the goals and the resource constraints within the environment. Assuming a known map of the environment and a fixed horizon time, one can develop a schedule for the robotic systems that accounts for such temporal uncertainty and resource constraints by leveraging the timeline-based planning framework. To this end, this thesis proposes T-HTN, a novel planner that extends the Hierarchical Task Networks (HTN) model by incorporating temporal reasoning via flexible timeline structures to produce plans that respect the goal’s deadlines and the complex resource constraints introduced in multi-robot scenarios. T-HTN is a robust extension to a timeline-based planner whose efficacy has been tested on multiple example scenarios within a simulation environment.

On the Vulnerability of Community Structure in Complex Networks

Published in Principles of Social Networking, Springer, 2021

In this paper, we study the role of nodes and edges in a complex network in dictating the robustness of a community structure towards structural perturbations. Specifically, we attempt to identify all vital nodes, which, when removed, would lead to a large change in the underlying community structure of the network. This problem is critical because the community structure of a network allows us to explore deep underlying insights into how the function and topology of the network affect each other. Moreover, it even provides a way to condense large networks into smaller modules where each community acts as a meta node and aids in more straightforward network analysis. If the community structure were to be compromised by either accidental or intentional perturbations to the network, that would make such analysis difficult. Since identifying such vital nodes is computationally intractable, we propose a suite of heuristics that allow to find solutions close to the optimality. To show the effectiveness of our approach, we first test these heuristics on small networks and then move to more extensive networks to show that we achieve similar results. Further analysis reveals that the proposed approaches are useful to analyze the vulnerability of communities in networks irrespective of their size and scale. Additionally, we show the performance through an extrinsic evaluation framework – we employ two tasks, i.e., link prediction and information diffusion, and show that the effect of our algorithms on these tasks is higher than the other baselines.

Hierarchical Bayesian Framework for Bus Dwell Time Prediction

Published in IEEE Transactions on Intelligent Transportation Systems, Volume 22 | Issue 5 | May 2021, 2020

In many applications, uncertainty regarding the duration of activities complicates the generation of accurate plans and schedules. Such is the case for the problem considered in this paper - predicting the arrival times of buses at signalized intersections. Direct vehicle-to-infrastructure communication of location, speed and heading information offers unprecedented opportunities for real-time optimization of traffic signal timing plans, but to be useful bus arrival time prediction must reliably account for bus dwell time at near-side bus stops. To address this problem, we propose a novel, Bayesian hierarchical approach for constructing bus dwell time duration distributions from historical data. Unlike traditional statistical learning techniques, the proposed approach relies on minimal data, is inherently adaptive to time varying task duration distribution, and provides a rich description of confidence for decision making, all of which are important in the bus dwell time prediction context. The effectiveness of this approach is demonstrated using historical data provided by a local transit authority on bus dwell times at urban bus stops. Our results show that the dwell time distributions generated by our approach yield significantly more accurate predictions than those generated by both standard regression techniques and a more data intensive deep learning approach.

Evaluating Accuracy of DSRC GPS for Pedestrian Localization in Urban Environments

Published in RISS Working Papers Journal - Volume 6 | Fall 2018, 2018

Dedicated Short-Range Communications (DSRC) are a standard of communications designed for vehicle-tovehicle and vehicle-to-infrastructure communication. This technology offers significant promise for improving pedestrian safety, as it allows pedestrians to communicate directly with nearby infrastructure elements and vehicles, and offers more precise GPS localization. Our work shows the current standard is too imprecise at low speeds, and as such cannot be used for pedestrian localization. We propose a method to increase the accuracy of DSRC GPS readings at low velocities and to increase precision by utilizing both iPhone and DSRC GPS readings

Viraj Parimi