View in EDS HTML Full Text PDF Full Text

Bayesian Graph Traversal.

Saved in:
Bibliographic Details
Authors: Caballero, William N.1 (AUTHOR) william.caballero@afit.edu, Jenkins, Phillip R.1 (AUTHOR) phillip.jenkins.4@us.af.mil, Banks, David2 (AUTHOR) dlbanks@duke.edu, Robbins, Matthew1 (AUTHOR) matthew.robbins@afit.edu
Source: Decision Analysis (INFORMS). Mar2026, Vol. 23 Issue 1, p11-27. 17p.
Subject Terms: *Bayesian analysis, *Decision making, Graph algorithms, NP-hard problems, Routing systems, Gaussian processes, Drone aircraft
Abstract: This research considers Bayesian decision-analytic approaches toward the traversal of an uncertain graph. Namely, a traveler progresses over a graph in which rewards are gained upon a node's first visit, and costs are incurred for every edge traversal. The traveler knows the graph's adjacency matrix and the starting position but does not know the rewards and costs. The traveler is a Bayesian who encodes his beliefs about these values using a Gaussian process prior and who seeks to maximize his expected utility over these beliefs. Adopting a decision-analytic perspective, we develop sequential decision-making solution strategies for this coupled information-collection and network-routing problem. We show that the problem is NP-hard and derive properties of the optimal walk. These properties provide heuristics for the traveler's problem that balance exploration and exploitation. We provide a practical case study focused on the use of unmanned aerial systems for public safety and empirically study policy performance in myriad Erdös–Rényi settings. Funding: This work was supported by the Office of Naval Research [Grant 6000012277] and the Air Force Office of Scientific Research [Grant 21RT0867]. [ABSTRACT FROM AUTHOR]
Database: Entrepreneurial Studies Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: ent
DbLabel: Entrepreneurial Studies Source
An: 192085243
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Caballero%2C+William+N%2E%22">Caballero, William N.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> william.caballero@afit.edu</i><br /><searchLink fieldCode="AR" term="%22Jenkins%2C+Phillip+R%2E%22">Jenkins, Phillip R.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> phillip.jenkins.4@us.af.mil</i><br /><searchLink fieldCode="AR" term="%22Banks%2C+David%22">Banks, David</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> dlbanks@duke.edu</i><br /><searchLink fieldCode="AR" term="%22Robbins%2C+Matthew%22">Robbins, Matthew</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> matthew.robbins@afit.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Decision+Analysis+%28INFORMS%29%22">Decision Analysis (INFORMS)</searchLink>. Mar2026, Vol. 23 Issue 1, p11-27. 17p.
– Name: Subject
  Label: Subject Terms
  Group: Su
  Data: *<searchLink fieldCode="DE" term="%22Bayesian+analysis%22">Bayesian analysis</searchLink><br />*<searchLink fieldCode="DE" term="%22Decision+making%22">Decision making</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+algorithms%22">Graph algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22NP-hard+problems%22">NP-hard problems</searchLink><br /><searchLink fieldCode="DE" term="%22Routing+systems%22">Routing systems</searchLink><br /><searchLink fieldCode="DE" term="%22Gaussian+processes%22">Gaussian processes</searchLink><br /><searchLink fieldCode="DE" term="%22Drone+aircraft%22">Drone aircraft</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: This research considers Bayesian decision-analytic approaches toward the traversal of an uncertain graph. Namely, a traveler progresses over a graph in which rewards are gained upon a node's first visit, and costs are incurred for every edge traversal. The traveler knows the graph's adjacency matrix and the starting position but does not know the rewards and costs. The traveler is a Bayesian who encodes his beliefs about these values using a Gaussian process prior and who seeks to maximize his expected utility over these beliefs. Adopting a decision-analytic perspective, we develop sequential decision-making solution strategies for this coupled information-collection and network-routing problem. We show that the problem is NP-hard and derive properties of the optimal walk. These properties provide heuristics for the traveler's problem that balance exploration and exploitation. We provide a practical case study focused on the use of unmanned aerial systems for public safety and empirically study policy performance in myriad Erdös–Rényi settings. Funding: This work was supported by the Office of Naval Research [Grant 6000012277] and the Air Force Office of Scientific Research [Grant 21RT0867]. [ABSTRACT FROM AUTHOR]
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=ent&AN=192085243
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1287/deca.2024.0239
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 17
        StartPage: 11
    Subjects:
      – SubjectFull: Bayesian analysis
        Type: general
      – SubjectFull: Decision making
        Type: general
      – SubjectFull: Graph algorithms
        Type: general
      – SubjectFull: NP-hard problems
        Type: general
      – SubjectFull: Routing systems
        Type: general
      – SubjectFull: Gaussian processes
        Type: general
      – SubjectFull: Drone aircraft
        Type: general
    Titles:
      – TitleFull: Bayesian Graph Traversal.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Caballero, William N.
      – PersonEntity:
          Name:
            NameFull: Jenkins, Phillip R.
      – PersonEntity:
          Name:
            NameFull: Banks, David
      – PersonEntity:
          Name:
            NameFull: Robbins, Matthew
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: Mar2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 15458490
          Numbering:
            – Type: volume
              Value: 23
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Decision Analysis (INFORMS)
              Type: main
ResultId 1