Hamzah I Khan

Harvey Mudd College Independent Program of Studies in Robotics 2018

mugshot
Thesis Advisor: Prof. Susan E. Martonosi
Second Reader: Prof. James C. Boerkoel, Jr., HMC Computer Science Department
Email: hkhan@math.hmc.edu

An Exploration of Concurrent Subnetworks Within Simple Temporal Scheduling Problems

Simple temporal networks (STNs) were introduced by Dechter et al. (1991) as a means of describing temporal constraints graphically for scheduling problems. Since then, the concept has been extended to model and develop algorithms for uncertain and multiagent scheduling situations. This work builds on the geometric interpretation for STNs that was presented in recent work (Lloyd et al. 2018). We identify relationships between properties of the directed graphical and convex polygonal representations of an STN. In addition, we extend the desidarata proposed by Lloyd et al. (2018) to probabilistic STNs. Finally, we use this analysis to investigate the convex polygons formed by concurrent sets of events within STNs and the role they play in making an uncertain multiagent scheduling problem difficult to satisfy.