{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/109531"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/109531","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Efficient learning and planning using spatial side information","abstract":"This thesis investigates the following question: how to efficiently integrate side information, available either a priori or online, with existing algorithms for learning and planning in environments with stochastic features? Side information in this context refers to any information that does not directly determine system parameters, but indicates a relationship between them. Such information can often be obtained from existing data, including that collected by onboard sensors. Algorithms that exploit side information are of interest in solving many real-world problems that can be modeled as stochastic control processes with unknown transition probabilities or unknown transition times. Specifically, we consider the problems of reward maximization in grid-world environments with unknown, stochastic dynamics and travel time minimization in urban transit routing problems with deterministic dynamics and stochastic travel times. Exploiting additional information available to solve these problems, when classical algorithms leave much to be desired in terms of performance and accuracy, is the main theme of this thesis. The first part of the thesis proposes the idea of indirect sampling for accelerated learning in Markov decision processes when additional information is available in the form of bounds on the differences between the transition probabilities at different states. In addition, it proposes a greedy approximation algorithm that utilizes the additional side information to effectively balance exploration and exploitation. It also analyzes the performance of indirect sampling algorithms in different information settings and defines the notion of agent safety, a vital consideration for systems operating in the physical environment, in the context of our problem. Under certain assumptions, it provides guarantees on the safety of an agent exploring with our algorithm that exploits side information. The second part proposes a methodology and a tool that, given an origin-destination pair, a travel time budget, and a measure of the passenger's tolerance for ambiguity, provide the optimal online route choice in a transit network by balancing the objectives of maximizing on-time arrival probability and minimizing expected travel time. This framework is a significant improvement over existing algorithms where the problem of optimal routing in urban transit networks is usually studied with only the least expected travel time as the performance criteria under the assumption of travel time independence on different road segments. The proposed algorithm utilizes side information, available in the form of historic travel time data and upstream real-time data, to build and update the underlying model online. We demonstrate the utility and the performance of the proposed algorithms with the help of realistic numerical experiments conducted (i) on a fixed-route bus system that serves the residents of the Champaign-Urbana metropolitan area and, (ii) in the setting of a Mars rover navigating on unknown or partially known terrain. In both of these problems, data from onboard sensors and external sources acts as the side information.","abstract_html":"This thesis investigates the following question: how to efficiently integrate side information, available either a priori or online, with existing algorithms for learning and planning in environments with stochastic features? Side information in this context refers to any information that does not directly determine system parameters, but indicates a relationship between them. Such information can often be obtained from existing data, including that collected by onboard sensors. Algorithms that exploit side information are of interest in solving many real-world problems that can be modeled as stochastic control processes with unknown transition probabilities or unknown transition times. Specifically, we consider the problems of reward maximization in grid-world environments with unknown, stochastic dynamics and travel time minimization in urban transit routing problems with deterministic dynamics and stochastic travel times. Exploiting additional information available to solve these problems, when classical algorithms leave much to be desired in terms of performance and accuracy, is the main theme of this thesis. The first part of the thesis proposes the idea of indirect sampling for accelerated learning in Markov decision processes when additional information is available in the form of bounds on the differences between the transition probabilities at different states. In addition, it proposes a greedy approximation algorithm that utilizes the additional side information to effectively balance exploration and exploitation. It also analyzes the performance of indirect sampling algorithms in different information settings and defines the notion of agent safety, a vital consideration for systems operating in the physical environment, in the context of our problem. Under certain assumptions, it provides guarantees on the safety of an agent exploring with our algorithm that exploits side information. The second part proposes a methodology and a tool that, given an origin-destination pair, a travel time budget, and a measure of the passenger's tolerance for ambiguity, provide the optimal online route choice in a transit network by balancing the objectives of maximizing on-time arrival probability and minimizing expected travel time. This framework is a significant improvement over existing algorithms where the problem of optimal routing in urban transit networks is usually studied with only the least expected travel time as the performance criteria under the assumption of travel time independence on different road segments. The proposed algorithm utilizes side information, available in the form of historic travel time data and upstream real-time data, to build and update the underlying model online. We demonstrate the utility and the performance of the proposed algorithms with the help of realistic numerical experiments conducted (i) on a fixed-route bus system that serves the residents of the Champaign-Urbana metropolitan area and, (ii) in the setting of a Mars rover navigating on unknown or partially known terrain. In both of these problems, data from onboard sensors and external sources acts as the side information.","abstract_has_math":false,"creators":["Thangeda, Pranay"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Aerospace Engineering","degree_department":null,"school":null,"contributors":["Ornik, Melkior"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-03-05T21:42:51Z","date_published":"2021-03-05T21:42:51Z","updated_at":"2026-07-22T22:24:50Z","subjects":["Autonomous Systems","Reinforcement Learning","Optimal Planning","Transit Networks"],"languages":["en"],"rights":["Copyright 2020 Pranay Thangeda"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/109531","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ornik, Melkior"]},{"key":"dc:creator","label":"Author","values":["Thangeda, Pranay"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-03-05T21:42:51Z","2023-03-05T21:43:00Z","2020-12-09","2020-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Aerospace Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Autonomous Systems","Reinforcement Learning","Optimal Planning","Transit Networks"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Pranay Thangeda"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/109531"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis investigates the following question: how to efficiently integrate side information, available either a priori or online, with existing algorithms for learning and planning in environments with stochastic features? Side information in this context refers to any information that does not directly determine system parameters, but indicates a relationship between them. Such information can often be obtained from existing data, including that collected by onboard sensors. Algorithms that exploit side information are of interest in solving many real-world problems that can be modeled as stochastic control processes with unknown transition probabilities or unknown transition times. Specifically, we consider the problems of reward maximization in grid-world environments with unknown, stochastic dynamics and travel time minimization in urban transit routing problems with deterministic dynamics and stochastic travel times. Exploiting additional information available to solve these problems, when classical algorithms leave much to be desired in terms of performance and accuracy, is the main theme of this thesis. The first part of the thesis proposes the idea of indirect sampling for accelerated learning in Markov decision processes when additional information is available in the form of bounds on the differences between the transition probabilities at different states. In addition, it proposes a greedy approximation algorithm that utilizes the additional side information to effectively balance exploration and exploitation. It also analyzes the performance of indirect sampling algorithms in different information settings and defines the notion of agent safety, a vital consideration for systems operating in the physical environment, in the context of our problem. Under certain assumptions, it provides guarantees on the safety of an agent exploring with our algorithm that exploits side information. The second part proposes a methodology and a tool that, given an origin-destination pair, a travel time budget, and a measure of the passenger's tolerance for ambiguity, provide the optimal online route choice in a transit network by balancing the objectives of maximizing on-time arrival probability and minimizing expected travel time. This framework is a significant improvement over existing algorithms where the problem of optimal routing in urban transit networks is usually studied with only the least expected travel time as the performance criteria under the assumption of travel time independence on different road segments. The proposed algorithm utilizes side information, available in the form of historic travel time data and upstream real-time data, to build and update the underlying model online. We demonstrate the utility and the performance of the proposed algorithms with the help of realistic numerical experiments conducted (i) on a fixed-route bus system that serves the residents of the Champaign-Urbana metropolitan area and, (ii) in the setting of a Mars rover navigating on unknown or partially known terrain. In both of these problems, data from onboard sensors and external sources acts as the side information.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-12-01","The student, Pranay Thangeda, accepted the attached license on 2020-12-07 at 20:36.","The student, Pranay Thangeda, submitted this Thesis for approval on 2020-12-07 at 21:47.","This Thesis was approved for publication on 2020-12-09 at 15:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16086 on 2021-03-04 at 16:20:43","Made available in DSpace on 2021-03-05T21:42:51Z (GMT). No. of bitstreams: 2 THANGEDA-THESIS-2020.pdf: 2804943 bytes, checksum: 7ceb6a1733dd8f8ba27f08e2bb31d0a0 (MD5) LICENSE.txt: 4212 bytes, checksum: 1604efe3ab15ae4102972a9c2dbfde93 (MD5) Previous issue date: 2020-12-09","Embargo set by: Seth Robbins for item 117236 Lift date: 2023-03-05T21:43:00Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Efficient learning and planning using spatial side information"]}]}],"canonical_facts":{"dc:contributor":["Ornik, Melkior"],"dc:creator":["Thangeda, Pranay"],"dc:date":["2021-03-05T21:42:51Z","2023-03-05T21:43:00Z","2020-12-09","2020-12"],"dc:description":["This thesis investigates the following question: how to efficiently integrate side information, available either a priori or online, with existing algorithms for learning and planning in environments with stochastic features? Side information in this context refers to any information that does not directly determine system parameters, but indicates a relationship between them. Such information can often be obtained from existing data, including that collected by onboard sensors. Algorithms that exploit side information are of interest in solving many real-world problems that can be modeled as stochastic control processes with unknown transition probabilities or unknown transition times. Specifically, we consider the problems of reward maximization in grid-world environments with unknown, stochastic dynamics and travel time minimization in urban transit routing problems with deterministic dynamics and stochastic travel times. Exploiting additional information available to solve these problems, when classical algorithms leave much to be desired in terms of performance and accuracy, is the main theme of this thesis. The first part of the thesis proposes the idea of indirect sampling for accelerated learning in Markov decision processes when additional information is available in the form of bounds on the differences between the transition probabilities at different states. In addition, it proposes a greedy approximation algorithm that utilizes the additional side information to effectively balance exploration and exploitation. It also analyzes the performance of indirect sampling algorithms in different information settings and defines the notion of agent safety, a vital consideration for systems operating in the physical environment, in the context of our problem. Under certain assumptions, it provides guarantees on the safety of an agent exploring with our algorithm that exploits side information. The second part proposes a methodology and a tool that, given an origin-destination pair, a travel time budget, and a measure of the passenger's tolerance for ambiguity, provide the optimal online route choice in a transit network by balancing the objectives of maximizing on-time arrival probability and minimizing expected travel time. This framework is a significant improvement over existing algorithms where the problem of optimal routing in urban transit networks is usually studied with only the least expected travel time as the performance criteria under the assumption of travel time independence on different road segments. The proposed algorithm utilizes side information, available in the form of historic travel time data and upstream real-time data, to build and update the underlying model online. We demonstrate the utility and the performance of the proposed algorithms with the help of realistic numerical experiments conducted (i) on a fixed-route bus system that serves the residents of the Champaign-Urbana metropolitan area and, (ii) in the setting of a Mars rover navigating on unknown or partially known terrain. In both of these problems, data from onboard sensors and external sources acts as the side information.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-12-01","The student, Pranay Thangeda, accepted the attached license on 2020-12-07 at 20:36.","The student, Pranay Thangeda, submitted this Thesis for approval on 2020-12-07 at 21:47.","This Thesis was approved for publication on 2020-12-09 at 15:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16086 on 2021-03-04 at 16:20:43","Made available in DSpace on 2021-03-05T21:42:51Z (GMT). No. of bitstreams: 2 THANGEDA-THESIS-2020.pdf: 2804943 bytes, checksum: 7ceb6a1733dd8f8ba27f08e2bb31d0a0 (MD5) LICENSE.txt: 4212 bytes, checksum: 1604efe3ab15ae4102972a9c2dbfde93 (MD5) Previous issue date: 2020-12-09","Embargo set by: Seth Robbins for item 117236 Lift date: 2023-03-05T21:43:00Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/109531"],"dc:language":["en"],"dc:rights":["Copyright 2020 Pranay Thangeda"],"dc:subject":["Autonomous Systems","Reinforcement Learning","Optimal Planning","Transit Networks"],"dc:title":["Efficient learning and planning using spatial side information"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Aerospace Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:50Z"}