PageSourceSearch

https://yangfan.github.io/publications/

html yangfan.github.io collected 2026-10-03 10:12:18 UTC 24,330 bytes, 5 lines download raw bytes

1<!DOCTYPE html> <html lang="en"> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <title> publications | Fan Yang </title> <meta name="author" content="Fan Yang"> <meta name="description" content="publications by categories in reversed chronological order. generated by jekyll-scholar."> <meta name="keywords" content="jekyll, jekyll-theme, academic-website, portfolio-website"> <link rel="stylesheet" href="/assets/css/bootstrap.min.css?a4b3f509e79c54a512b890d73235ef04"> <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/css/mdb.min.css" integrity="sha256-jpjYvU3G3N6nrrBwXJoVEYI/0zw8htfFnhT9ljN3JJw=" crossorigin="anonymous"> <link defer rel="stylesheet" href="/assets/css/academicons.min.css?f0b7046b84e425c55f3463ac249818f5"> <link defer rel="stylesheet" href="/assets/css/scholar-icons.css?62b2ac103a88034e6882a5be5f3e2772"> <link defer rel="stylesheet" type="text/css" href="https://fonts.googleapis.com/css?family=Roboto:300,400,500,700|Roboto+Slab:100,300,400,500,700|Material+Icons&amp;display=swap"> <link defer rel="stylesheet" href="/assets/css/jekyll-pygments-themes-github.css?591dab5a4e56573bf4ef7fd332894c99" media="" id="highlight_theme_light"> <link rel="shortcut icon" href="/assets/img/favicon.ico?7caa1cd875903989345dfb468ae09997"> <link rel="stylesheet" href="/assets/css/main.css?d41d8cd98f00b204e9800998ecf8427e"> <link rel="canonical" href="https://yangfan.github.io/publications/"> 
1<script src="/assets/js/theme.js?a81d82887dd692e91686b43de4542f18"></script>
1 <link defer rel="stylesheet" href="/assets/css/jekyll-pygments-themes-native.css?5847e5ed4a4568527aa6cfab446049ca" media="none" id="highlight_theme_dark"> 
1<script>
2    initTheme();
3  </script>
3 </head> <body class="fixed-top-nav "> <header> <nav id="navbar" class="navbar navbar-light navbar-expand-sm fixed-top" role="navigation"> <div class="container"> <a class="navbar-brand title font-weight-lighter" href="/"> <i class="fas fa-fan fa-spin"></i> <span class="font-weight-bold">Fan</span> Yang </a> <button class="navbar-toggler collapsed ml-auto" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation"> <span class="sr-only">Toggle navigation</span> <span class="icon-bar top-bar"></span> <span class="icon-bar middle-bar"></span> <span class="icon-bar bottom-bar"></span> </button> <div class="collapse navbar-collapse text-right" id="navbarNav"> <ul class="navbar-nav ml-auto flex-nowrap"> <li class="nav-item "> <a class="nav-link" href="/">about </a> </li> <li class="nav-item "> <a class="nav-link" href="/projects/">projects </a> </li> <li class="nav-item active"> <a class="nav-link" href="/publications/">publications <span class="sr-only">(current)</span> </a> </li> <li class="nav-item "> <a class="nav-link" href="/research/">research </a> </li> <li class="nav-item "> <a class="nav-link" href="/repositories/">repositories </a> </li> <li class="nav-item "> <a class="nav-link" href="/cv/">cv </a> </li> <li class="nav-item "> <a class="nav-link" href="/blog/">blog </a> </li> <li class="nav-item"> <button id="search-toggle" title="Search" onclick="openSearchModal()"> <span class="nav-link">ctrl k <i class="ti ti-search"></i></span> </button> </li> <li class="toggle-container"> <button id="light-toggle" title="Change theme"> <i class="ti ti-sun-moon" id="light-toggle-system"></i> <i class="ti ti-moon-filled" id="light-toggle-dark"></i> <i class="ti ti-sun-filled" id="light-toggle-light"></i> </button> </li> </ul> </div> </div> </nav> <progress id="progress" value="0"> <div class="progress-container"> <span class="progress-bar"></span> </div> </progress> </header> <div class="container mt-5" role="main"> <div class="post"> <header class="post-header"> <h1 class="post-title">publications</h1> </header> <article> 
3<script src="/assets/js/bibsearch.js?1bc438ca9037884cc579601c09afd847" type="module"></script>
3 <p><input type="text" id="bibsearch" spellcheck="false" autocomplete="off" class="search bibsearch-form-input" placeholder="Type to filter"></p> <div class="publications"> <h2 class="bibliography">2021</h2> <ol class="bibliography"><li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">ICRA</abbr> </div> <div id="Yang2021" class="col-sm-8"> <div class="title">Chance Constrained Simultaneous Path Planning and Task Assignment with Bottleneck Objective</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In 2021 IEEE International Conference on Robotics and Automation (ICRA)</em>, 2021 </div> <div class="periodical"> </div> <div class="links"> <a class="abstract btn btn-sm z-depth-0" role="button">Abs</a> <a href="https://ieeexplore.ieee.org/document/9561276" class="btn btn-sm z-depth-0" role="button" rel="external nofollow noopener" target="_blank">HTML</a> <a href="/assets/pdf/ICRA2021.pdf" class="btn btn-sm z-depth-0" role="button">PDF</a> </div> <div class="abstract hidden"> <p>We present a novel algorithm for combined taskassignment and path planning on a roadmap with stochasticcosts. In this problem, the initially unassigned robots and tasksare located at known positions in a roadmap. We want to assigna unique task to each robot and compute a path for the robot togo to the task location. Given the means and variances of travelcost, our goal is to develop algorithms that guarantee that foreach robot, with high probability, the total travel cost is belowa minimum value in any realization of the stochastic travelcosts. We prove that the solution can be obtained by solving(a) a chance-constrained shortest path problems for all robot-task pairs and (b) a linear bottleneck assignment problem inwhich the cost of an assignment is equal to the optimal objectivevalue of the former problem. We propose algorithms for solvingthe chance-constrained shortest path problem either optimallyor approximately by solving a number of deterministic shortestpath problems that minimize some linear combination of meansand variances of edge costs. We present simulation results onrandomly generated networks and data to demonstrate that ouralgorithm is scalable with the number of robots (or tasks) andthe size of the network.</p> </div> </div> </div> </li></ol> <h2 class="bibliography">2020</h2> <ol class="bibliography"> <li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">IROS</abbr> </div> <div id="Yang2020iros" class="col-sm-8"> <div class="title">Algorithm for Multi-robot Chance-constrained Generalized Assignment Problem with Stochastic Resource Consumption</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)</em>, 2020 </div> <div class="periodical"> </div> <div class="links"> <a class="abstract btn btn-sm z-depth-0" role="button">Abs</a> <a href="https://doi.org/10.1109/IROS45743.2020.9341726" class="btn btn-sm z-depth-0" role="button" rel="external nofollow noopener" target="_blank">DOI</a> <a href="https://ieeexplore.ieee.org/document/9341726" class="btn btn-sm z-depth-0" role="button" rel="external nofollow noopener" target="_blank">HTML</a> <a href="/assets/pdf/IROS2020.pdf" class="btn btn-sm z-depth-0" role="button">PDF</a> </div> <div class="abstract hidden"> <p>We present a novel algorithm for the multi-robot generalized assignment problem (GAP) with stochastic resource consumption. In this problem, each robot has a resource (e.g., battery life) constraint and it consumes a certain amount of resource to perform a task. In practice, the resource consumed for performing a task can be uncertain. Therefore, we assume that the resource consumption is a random variable with known mean and variance. The objective is to find an assignment of the robots to tasks that maximizes the team payoff. Each task is assigned to at most one robot and the resource constraint for each robot has to be satisfied with very high probability. We formulate the problem as a chance-constrained combinatorial optimization problem and call it the chance-constrained generalized assignment problem (CC-GAP). This problem is an extension of the deterministic generalized assignment problem, which is a NP-hard problem. We design an iterative algorithm for solving CC-GAP in which each robot maximizes its own objective by solving a chance-constrained knapsack problem in an iterative manner. The approximation ratio of our algorithm is (1+α), assuming that the deterministic knapsack problem is solved by an α-approximation algorithm. We present simulation results to demonstrate that our algorithm is scalable with the number of robots and tasks.</p> </div> </div> </div> </li> <li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">ICRA</abbr> </div> <div id="Yang2020" class="col-sm-8"> <div class="title">Chance Constrained Simultaneous Path Planning and Task Assignment for Multiple Robots with Stochastic Path Costs</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In 2020 IEEE International Conference on Robotics and Automation (ICRA)</em>, 2020 </div> <div class="periodical"> </div> <div class="links"> <a class="abstract btn btn-sm z-depth-0" role="button">Abs</a> <a href="https://ieeexplore.ieee.org/abstract/document/9197354" class="btn btn-sm z-depth-0" role="button" rel="external nofollow noopener" target="_blank">HTML</a> <a href="/assets/pdf/ICRA2020.pdf" class="btn btn-sm z-depth-0" role="button">PDF</a> </div> <div class="abstract hidden"> <p>We present a novel algorithm for simultaneous task assignment and path planning on a graph (or roadmap) with stoch
3astic edge costs. In this problem, the initially unassigned robots and tasks are located at known positions in a roadmap. We want to assign a unique task to each robot and compute a path for the robot to go to its assigned task location. Given the mean and variance of travel cost of each edge, our goal is to develop algorithms that, with high probability, the total path cost of the robot team is below a minimum value in any realization of the stochastic travel costs. We formulate the problem as a chance-constrained simultaneous task assignment and path planning problem (CC-STAP). We prove that the optimal solution of CC-STAP can be obtained by solving a sequence of deterministic simultaneous task assignment and path planning problems in which the travel cost is a linear combination of mean and variance of the edge cost. We show that the deterministic problem can be solved in two steps. In the first step, robots compute the shortest paths to the task locations and in the second step, the robots solve a linear assignment problem with the costs obtained in the first step. We also propose a distributed algorithm that solves CC-STAP near-optimally. We present simulation results on randomly generated networks and data to demonstrate that our algorithm is scalable with the number of robots (or tasks) and the size of the network.</p> </div> </div> </div> </li> <li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">PhD Thesis</abbr> </div> <div id="Yang2020Thesis" class="col-sm-8"> <div class="title">Algorithms for Chance-constrained Multi-robot Task Allocation</div> <div class="author"> <em>Fan Yang</em> </div> <div class="periodical"> <em></em> 2020 </div> <div class="periodical"> </div> <div class="links"> <a class="abstract btn btn-sm z-depth-0" role="button">Abs</a> </div> <div class="abstract hidden"> <p>Coordinating multi-robot systems (MRS) have a wide range of application domains including collaborative autonomous manufacturing, automated transport of goods in warehouses and factory floors, environmental monitoring, search and rescue, surveillance, and sensing data collection. Two fundamental problems arise naturally in the autonomous operation of the multi-robot system: (a) multi-robot task allocation; (b) multi-robot path planning. Generally speaking, multi-robot task allocation solves the following problem: given a set of robots and tasks with each robot obtaining a certain payoff for each task, compute a subset of tasks for each robot such that a team performance criterion is optimized subject to a set of constraints on the tasks and/or the robots. Multi-robot path planning solves the following problem: given the initial positions of a set of robots and target positions of the spatially distributed tasks, compute a collision-free path for each robot from its initial position to its target position. Most current works on multi-robot task allocation consider as deterministic parameters like robot-task payoffs, resource consumption of robots performing tasks. However, these parameters may not be known exactly in practice, especially in the open environment in which there are other (uncontrolled) moving entities like humans or human-operated vehicles that occupy the space. One goal of this thesis is to formulate multi-robot task allocation problems with uncertain parameters and develop solution algorithms for them. Further, in the extant literature, task allocation and path planning problems are commonly considered separately. In particular, it is assumed in task allocation that there are planned paths for all robot-task assignments and thus the payoff or the resource consumption to perform a task is available. In path planning, it is assumed that the tasks are assigned to robots and target positions are thus specified. When both problems have to be solved, the decoupling approach (solving two problems separately) is usually used. Although conceptually convenient, the decoupling approach may lead to sub-optimal solutions. Therefore another goal of this thesis is to simultaneously compute the allocation of tasks to robots as well as plan the path from the initial position of robots to the destinations.</p> </div> </div> </div> </li> </ol> <h2 class="bibliography">2019</h2> <ol class="bibliography"><li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">MRS</abbr> </div> <div id="Yang2019abs" class="col-sm-8"> <div class="title">Multirobot Simultaneous Path Planning and Task Assignment on Graphs with Stochastic Costs</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In 2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)</em>, 2019 </div> <div class="periodical"> </div> <div class="links"> <a href="https://ieeexplore.ieee.org/document/8901052" class="btn btn-sm z-depth-0" role="button" rel="external nofollow noopener" target="_blank">HTML</a> <a href="/assets/pdf/MRS2019.pdf" class="btn btn-sm z-depth-0" role="button">PDF</a> <a href="/assets/pdf/MRS19poster.pdf" class="btn btn-sm z-depth-0" role="button">Poster</a> </div> </div> </div> </li></ol> <h2 class="bibliography">2018</h2> <ol class="bibliography"> <li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">ICRA</abbr> </div> <div id="Yang2018" class="col-sm-8"> <div class="title">Algorithm for Optimal Chance Constrained Knapsack Problem with Applications to Multi-Robot Teaming</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In 2018 IEEE International Conference on Robotics and Automation (ICRA)</em>, May 2018 </div> <div class="periodical"> </div> <div class="links"> <a class="abstract btn btn-sm z-depth-0" role="button">Abs</a> <a href="https://ieeexplore.ieee.org/document/8461040" class="btn btn-sm z-depth-0" role="button" rel="external nofollow noopener" target="_blank">HTML</a> <a href="/assets/pdf/ICRA2018.pdf" class="btn btn-sm z-depth-0" role="button">PDF</a> </div> <div class="abstract hidden"> <p>Motivated by applications in multirobot team selection, in this paper, we present a novel algorithm for computing optimal solution of chance-constrained 0-1 knapsack problem. In this variation of the knapsack problem, the objective function is deterministic but the weights of the items are stochastic and therefore the knapsack constraint is stochastic. We convert the chance-constrained knapsack problem to a two-dimensional discrete optimization problem on the variance-mean plane, where each point on the plane can be identified with an assignment of items to the knapsack. By exploiting the geometry of the non-convex feasible region of the chance-constrained knapsack problem in the variance-mean plane, we present a novel deterministic technique to find an optimal solution by solving a sequence of deterministic knapsack problems (called risk-averse knapsack problem). We apply our algorithm to a multirobot team selection problem to cover a given route, where the length of the route is much larger than the length each individual robot can fly and the length that an individual robot can fly is a random variable (with known mean and variance). We present simulation results on randomly generated data to demonstrate that our approach is scalable with both the number of robots and increasing uncertainty of the distance an individual robot can travel.</p> </div> </div> </div> </li> <li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">NERC</abbr> </div> <div id="NERC2018abs" class="col-sm-8"> <div class="title">Multi-robot Team Formation Under Uncertain Environment</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In Northeast Robotics Colloquium</em>, May 2018 </div> <div class="periodical"> </div> <div class="links"> <a href="/assets/pdf/NERCposter.pdf" class="btn btn-sm z-depth-0" role="button">Poster</a> </div> </div> </div> </li> </ol> <h2 class="bibliography">2017</h2> <ol class="bibliography"> <li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">ICRA</abbr> </div> <div id="Yang17" class="col-sm-8"> <div class="title">Algorithm for Optimal Chance Constrained Linear Assignment</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In 2017 IEEE International Conference on Robotics and Automation (ICRA)</em>, May 2017 </div> <div class="periodical"> </div> <div class="links"> <a class="abstract btn btn-sm z-depth-0" role="button">Abs</a> <a href="https://ieeexplore.ieee.org/document/7989099" class="btn btn-sm z-depth-0" role="button" rel="external nofollow noopener" target="_blank">HTML</a> <a href="/assets/pdf/ICRA2017.pdf" class="btn btn-sm z-depth-0" role="button">PDF</a> </div> <div class="abstract hidden"> <p>In this paper, we design provably-good algorithms for task allocation in multi-robot systems in the presence of payoff uncertainty. We consider a group of robots that has to perform a given set of tasks where each robot performs at most one task. The payoffs of the robots doing the tasks are assumed to be Gaussian random variables with known mean and variances. The total payoff of the robots is a sum of the individual payoffs of all the robots. The goal is to find an assignment with maximum payoff that can be achieved with a specified probability irrespective of the realization of the random variable. This problem can be formulated as a chance constrained combinatorial optimization problem. We develop a novel deterministic technique to solve this chance constrained optimization problem that ensures that the chance constraints are always satisfied. Adopting the notion of risk-aversion from the economics literature, we formulate a risk-averse task allocation problem, which is a deterministic integer optimization problem. We prove that by repeatedly solving the risk-averse task allocation problem using a one-dimensional search on the risk aversion parameter we find a solution for the chance constrained optimization formulation of the linear assignment problem with uncertain payoffs. We provide simulation results on randomly generated data to demonstrate our approach and also compare our method to existing approaches.</p> </div> </div> </div> </li> <li> <div class="row"> <div class="col col-sm-2 abbr"> <abbr class="badge rounded w-100">FWCG</abbr> </div> <div id="FWCG2017abs" class="col-sm-8"> <div class="title">Algorithm for Optimal Chance Constrained Knapsack with Applications to Multi-robot Teaming</div> <div class="author"> <em>Fan Yang</em> and Nilanjan Chakraborty </div> <div class="periodical"> <em>In 27th Annual Fall Workshop on Computational Geometry</em>, May 2017 </div> <div class="periodical"> </div> <div class="links"> <a href="/assets/pdf/FWCG2017.pdf" class="btn btn-sm z-depth-0" role="button">PDF</a> </div> </div> </div> </li> </ol> </div> </article> </div> </div> <footer class="fixed-bottom" role="contentinfo"> <div class="container mt-0"> © Copyright 2026 Fan Yang. Powered by <a href="https://jekyllrb.com/" target="_blank" rel="external nofollow noopener">Jekyll</a> with <a href="https://github.com/alshedivat/al-folio" rel="external nofollow noopener" target="_blank">al-folio</a> theme. Hosted by <a href="https://pages.github.com/" target="_blank" rel="external nofollow noopener">GitHub Pages</a>. Last updated: June 27, 2026. </div> </footer> 
3<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/jquery.min.js" integrity="sha256-/xUj+3OJU5yExlq6GSYGSHk7tPXikynS7ogEvDej/m4=" crossorigin="anonymous"></script>
3 
3<script src="/assets/js/bootstrap.bundle.min.js"></script>
3 
3<script src="https://cdn.jsdelivr.net/npm/[email protected]/js/mdb.min.js" integrity="sha256-NdbiivsvWt7VYCt6hYNT3h/th9vSTL4EDWeGs5SN3DA=" crossorigin="anonymous"></script>
3 
3<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/masonry.pkgd.min.js" integrity="sha256-Nn1q/fx0H7SNLZMQ5Hw5JLaTRZp0yILA/FRexe19VdI=" crossorigin="anonymous"></script>
3 
3<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/imagesloaded.pkgd.min.js" integrity="sha256-htrLFfZJ6v5udOG+3kNLINIKh2gvoKqwEhHYfTTMICc=" crossorigin="anonymous"></script>
3 
3<script defer src="/assets/js/masonry.js?a0db7e5d5c70cc3252b3138b0c91dcaf" type="text/javascript"></script>
3 
3<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/medium-zoom.min.js" integrity="sha256-ZgMyDAIYDYGxbcpJcfUnYwNevG/xi9OHKaR/8GK+jWc=" crossorigin="anonymous"></script>
3 
3<script defer src="/assets/js/zoom.js?85ddb88934d28b74e78031fd54cf8308"></script>
3 
3<script src="/assets/js/no_defer.js?2781658a0a2b13ed609542042a859126"></script>
3 
3<script defer src="/assets/js/common.js?c15de51d4bb57887caa2c21988d97279"></script>
3 
3<script defer src="/assets/js/copy_code.js?c8a01c11a92744d44b093fc3bda915df" type="text/javascript"></script>
3 
3<script defer src="/assets/js/jupyter_new_tab.js?d9f17b6adc2311cbabd747f4538bb15f"></script>
3 
3<script async src="https://d1bxh8uas1mnw7.cloudfront.net/assets/embed.js"></script>
3 
3<script async src="https://badge.dimensions.ai/badge.js"></script>
3 
3<script defer type="text/javascript" id="MathJax-script" src="https://cdn.jsdelivr.net/npm/[email protected]/es5/tex-mml-chtml.js" integrity="sha256-MASABpB4tYktI2Oitl4t+78w/lyA+D7b/s9GEP0JOGI=" crossorigin="anonymous"></script>
3 
3<script src="/assets/js/mathjax-setup.js?a5bb4e6a542c546dd929b24b8b236dfd"></script>
3 
3<script defer src="https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6" crossorigin="anonymous"></script>
3 
3<script defer src="/assets/js/progress-bar.js?2f30e0e6801ea8f5036fa66e1ab0a71a" type="text/javascript"></script>
3 
3<script src="/assets/js/vanilla-back-to-top.min.js?f40d453793ff4f64e238e420181a1d17"></script>
3 
3<script>
4    addBackToTop();
5  </script>
5 
5<script type="module" src="/assets/js/search/ninja-keys.min.js?a3446f084dcaecc5f75aa1757d087dcf"></script>
5 <ninja-keys hidebreadcrumbs noautoloadmdicons placeholder="Type to start searching"></ninja-keys> 
5<script src="/assets/js/search-setup.js?6c304f7b1992d4b60f7a07956e52f04a"></script>
5 
5<script src="/assets/js/search-data.js"></script>
5 
5<script src="/assets/js/shortcut-key.js?6f508d74becd347268a7f822bca7309d"></script>
5 </body> </html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.