A trajectory control problem for simple micro air vehicles (MAVs) is introduced and studied. The MAVs are endowed with the ability to estimate their position and velocity and can control their drag coefficient. The objective of this work is to design a control law for the drag coefficient in order to land the MAV close to a desired streamwise location, after being dropped from an airborne carrier at low altitude. We use a simple model-predictive control law, relying on a two-dimensional time-averaged atmospheric velocity field, which is validated on an unsteady three-dimensional representation of an unstratified atmospheric boundary layer. The simulation results show that the proposed control law results in a significant (10-fold) improvement in the accuracy of the streamwise landing point location, with respect to the uncontrolled case. Similar results are obtained when errors are considered in the location of the release point and in the estimate of the mean flow field.
@article{Dorgan.Loth.ea:AIAAJ05, Abstract = {A trajectory control problem for simple micro air vehicles (MAVs) is introduced and studied. The MAVs are endowed with the ability to estimate their position and velocity and can control their drag coefficient. The objective of this work is to design a control law for the drag coefficient in order to land the MAV close to a desired streamwise location, after being dropped from an airborne carrier at low altitude. We use a simple model-predictive control law, relying on a two-dimensional time-averaged atmospheric velocity field, which is validated on an unsteady three-dimensional representation of an unstratified atmospheric boundary layer. The simulation results show that the proposed control law results in a significant (10-fold) improvement in the accuracy of the streamwise landing point location, with respect to the uncontrolled case. Similar results are obtained when errors are considered in the location of the release point and in the estimate of the mean flow field. }, Author = {A.J. Dorgan and E. Loth and E. Frazzoli}, Date-Added = {2004-11-02 16:55:49 -0800}, Date-Modified = {2008-07-18 14:30:44 -0400}, Journal = {AIAA Journal}, Keywords = {Flight Control}, Local-Url = {/www/papers/Dorgan.Loth.ea.AIAAJ05.PROOFS.pdf}, Month = {March}, Number = {4}, Pages = {768-775}, Pdf = {/papers/Dorgan.Loth.ea.AIAAJ05.PROOFS.pdf}, Title = {Autonomous control of micro-aircraft vehicles falling through an atmospheric boundary layer}, Volume = {43}, Year = {2005}, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QUC4uLy4uLy4uLy4uL0xpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvRG9yZ2FuLkxvdGguZWEuQUlBQUowNS5QUk9PRlMucGRm0hcLGBlXTlMuZGF0YU8RAdwAAAAAAdwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMarQ7ZIKwAAABYHTB9Eb3JnYW4uTG90aC5lYS5BSUFBSiMxNjBBQUEucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAFgqqwxVQtQAAAAAAAAAAAAQABQAACSAAAAAAAAAAAAAAAAAAAAAGcGFwZXJzABAACAAAxqt79gAAABEACAAAwxWI9QAAAAEAEAAWB0wDnQx0A50McgOZtXgAAgBTTWFjaW50b3NoIEhEOkxpYnJhcnk6AFdlYlNlcnZlcjoARG9jdW1lbnRzOgBwYXBlcnM6AERvcmdhbi5Mb3RoLmVhLkFJQUFKIzE2MEFBQS5wZGYAAA4ARAAhAEQAbwByAGcAYQBuAC4ATABvAHQAaAAuAGUAYQAuAEEASQBBAEEASgAwADUALgBQAFIATwBPAEYAUwAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIARExpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvRG9yZ2FuLkxvdGguZWEuQUlBQUowNS5QUk9PRlMucGRmABMAAS8A//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4A4QDmAO4CzgLQAtUC4ALpAvcC+wMCAwsDEAMdAyADMgM1AzoAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADPA==} }
@article{Frazzoli.Dahleh.ea:TRO05, Author = {E.~Frazzoli and M.~A.~Dahleh and E.~Feron}, Date-Added = {2004-10-27 11:20:46 -0700}, Date-Modified = {2008-07-18 14:30:25 -0400}, Journal = {IEEE Trans. on Robotics}, Keywords = {Motion Planning, Robotics}, Month = {December}, Number = {6}, Pages = {1077--1091}, Pdf = {/papers/Frazzoli.Dahleh.ea.TRO05.pdf}, Title = {Maneuver-Based Motion Planning for Nonlinear Systems with Symmetries}, Volume = {21}, Year = {2005} }
@incollection{Sharma.Savchenko.ea:RSS05, Address = {Cambridge, MA}, Author = {V. Sharma and M. Savchenko and E. Frazzoli and P. Voulgaris}, Booktitle = {Robotics: Science and Systems I}, Date-Added = {2005-08-30 17:17:55 -0700}, Date-Modified = {2007-10-20 21:06:11 -0400}, Editor = {S. Thrun and G. S. Sukhatme and S. Schaal}, Keywords = {Robotic Networks}, Pages = {297--304}, Pdf = {/papers/Sharma.Savchenko.ea.RSS05.pdf}, Publisher = {MIT Press}, Title = {Time Complexity of Sensor-Based Vehicle Routing}, Year = {2005} }
@conference{Cheng.Frazzoli.ea:ICRA05, Address = {Barcelona, Spain}, Author = {S. Chitta and P. Cheng and E. Frazzoli and V. Kumar}, Booktitle = {IEEE Int. Conf. on Robotics and Automation}, Date-Added = {2006-10-20 00:03:38 -0400}, Date-Modified = {2011-01-19 22:52:21 -0500}, Keywords = {Motion Planning; Robotics}, Pages = {1597--1602}, Title = {Robo{T}rikke: A Novel Undulatory Locomotion System}, Year = {2005} }
In this paper we consider the following problem. An Uninhabited Aerial Vehicle (UAV), modeled as a vehicle moving at unit speed along paths of bounded curvature, must visit stochastically-generated targets in a convex, compact region of the plane. Targets are generated according to a spatio-temporal Poisson process, uniformly in the region. It is desired to minimize the expected waiting time between the appearance of a target, and the time it is visited. We present algorithms for UAV routing, and compare their performance with respect to asymptotic performance bounds, in the light and heavy load limits. Simulation results are presented and discussed.
@conference{Enright.Frazzoli:IFAC05, Abstract = {In this paper we consider the following problem. An Uninhabited Aerial Vehicle (UAV), modeled as a vehicle moving at unit speed along paths of bounded curvature, must visit stochastically-generated targets in a convex, compact region of the plane. Targets are generated according to a spatio-temporal Poisson process, uniformly in the region. It is desired to minimize the expected waiting time between the appearance of a target, and the time it is visited. We present algorithms for UAV routing, and compare their performance with respect to asymptotic performance bounds, in the light and heavy load limits. Simulation results are presented and discussed.}, Address = {Prague, Czech Republic}, Author = {J.~J. Enright and E. Frazzoli}, Booktitle = {Proc. of the IFAC World Congress}, Date-Added = {2004-11-02 17:25:19 -0800}, Date-Modified = {2008-08-08 11:59:12 -0400}, Keywords = {Motion Planning; Robotic Networks; UAVs/Autonomous Systems}, Local-Url = {~/papers/ifac05/ifac05.pdf}, Month = {July}, Pdf = {http://ares.seas.ucla.edu/papers/Enright.Frazzoli.IFAC05.pdf}, Title = {{UAV} Routing in a Stochastic, Time-Varying Environment}, Year = {2005}, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QFC4uL2lmYWMwNS9pZmFjMDUucGRm0hcLGBlXTlMuZGF0YU8RAXwAAAAAAXwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAANCJVfpIKwAAABHkFwppZmFjMDUucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEeQ2vlODwQAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAGaWZhYzA1ABAACAAA0ImcSgAAABEACAAAvlPKEQAAAAEAEAAR5BcAEJzNAAk+vQACk9MAAgA4TWFjaW50b3NoIEhEOlVzZXJzOgBmcmF6em9saToAcGFwZXJzOgBpZmFjMDU6AGlmYWMwNS5wZGYADgAWAAoAaQBmAGEAYwAwADUALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASACdVc2Vycy9mcmF6em9saS9wYXBlcnMvaWZhYzA1L2lmYWMwNS5wZGYAABMAAS8AABUAAgAP//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4ApQCqALICMgI0AjkCRAJNAlsCXwJmAm8CdAKBAoQClgKZAp4AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAACoA==} }
@conference{Enright.Frazzoli.ea:GNC05, Address = {San Francisco, CA}, Author = {J.J. Enright and E. Frazzoli and K. Savla and F. Bullo}, Booktitle = {Proc. of the AIAA Conf. on Guidance, Navigation, and Control}, Date-Added = {2005-08-31 00:51:07 -0700}, Date-Modified = {2008-08-08 11:59:02 -0400}, Keywords = {UAVs/Autonomous Systems; Robotic Networks}, Month = {August}, Pdf = {/papers/Enright.Frazzoli.ea.GNC05.pdf}, Title = {On Multiple {UAV} Routing with Stochastic Targets: Performance Bounds and Algorithms}, Year = {2005} }
@conference{Frazzoli.Pallottino.ea:GNC05, Address = {San Francisco, CA}, Author = {E. Frazzoli and L. Pallottino and V.G. Scordio and A. Bicchi}, Booktitle = {Proc. of the AIAA Conf. on Guidance, Navigation, and Control}, Date-Added = {2005-08-31 00:57:24 -0700}, Date-Modified = {2008-08-08 11:59:06 -0400}, Keywords = {Air Traffic Control, Robotic Networks; UAVs/Autonomous Systems}, Month = {August}, Pdf = {/papers/Frazzoli.Pallottino.ea.GNC05.pdf}, Title = {Decentralized Cooperative Conflict Resolution for Multiple Nonholonomic Vehicles}, Year = {2005} }
This paper proposes a formal model for a network of robotic agents that move and communicate. Building on concepts from distributed computation, robotics and control theory, we define notions of robotic network, control and communication law, coordination task, and time and communication complexity. We illustrate our model and compute the proposed complexity measures in the example of a network of locally connected agents on a circle that agree upon a direction of motion and pursue their immediate neighbors.
@conference{Martinez.Bullo.ea:CDC05a, Abstract = {This paper proposes a formal model for a network of robotic agents that move and communicate. Building on concepts from distributed computation, robotics and control theory, we define notions of robotic network, control and communication law, coordination task, and time and communication complexity. We illustrate our model and compute the proposed complexity measures in the example of a network of locally connected agents on a circle that agree upon a direction of motion and pursue their immediate neighbors. }, Address = {Seville, Spain}, Author = {S. Mart{\'\i}nez and F. Bullo and J. Cort\'es and E. Frazzoli}, Booktitle = {Proc. of the IEEE Conf. on Decision and Control}, Date-Added = {2005-03-08 16:47:28 -0800}, Date-Modified = {2011-01-19 22:18:28 -0500}, Keywords = {Robotic Networks}, Local-Url = {/www/papers/Martinez.Bullo.ea.CDC05a.DRAFT.pdf}, Month = {December}, Pages = {2847--2852}, Pdf = {http://rigoletto.seas.ucla.edu/papers/Martinez.Bullo.ea.CDC05a.DRAFT.pdf}, Title = {On synchronous robotic networks --- {Part I:} Models, tasks and complexity notions}, Year = {2005}, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QUS4uLy4uLy4uLy4uL0xpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvTWFydGluZXouQnVsbG8uZWEuQ0RDMDVhLkRSQUZULnBkZtIXCxgZV05TLmRhdGFPEQHgAAAAAAHgAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADGq0O2SCsAAAAWB0wfTWFydGluZXouQnVsbG8uZWEuQ0QjMTYwQUQyLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABYK0sMVUgMAAAAAAAAAAAAEAAUAAAkgAAAAAAAAAAAAAAAAAAAABnBhcGVycwAQAAgAAMare/YAAAARAAgAAMMVikMAAAABABAAFgdMA50MdAOdDHIDmbV4AAIAU01hY2ludG9zaCBIRDpMaWJyYXJ5OgBXZWJTZXJ2ZXI6AERvY3VtZW50czoAcGFwZXJzOgBNYXJ0aW5lei5CdWxsby5lYS5DRCMxNjBBRDIucGRmAAAOAEYAIgBNAGEAcgB0AGkAbgBlAHoALgBCAHUAbABsAG8ALgBlAGEALgBDAEQAQwAwADUAYQAuAEQAUgBBAEYAVAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIARUxpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvTWFydGluZXouQnVsbG8uZWEuQ0RDMDVhLkRSQUZULnBkZgAAEwABLwD//wAAgAbSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBVAGAAZwBqAGwAbgBxAHMAdQB3AIQAjgDiAOcA7wLTAtUC2gLlAu4C/AMAAwcDEAMVAyIDJQM3AzoDPwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANB} }
This paper analyzes a number of basic coordination algorithms running on synchronous robotic networks. We provide upper and lower bounds on the time complexity of the move-toward average and circumcenter laws, both achieving rendezvous, and of the centroid law, achieving deployment over a region of interest. The results are derived via novel analysis methods, including a set of results on the convergence rates of linear dynamical systems defined by tridiagonal Toeplitz and circulant matrices.
@conference{Martinez.Bullo.ea:CDC05b, Abstract = {This paper analyzes a number of basic coordination algorithms running on synchronous robotic networks. We provide upper and lower bounds on the time complexity of the move-toward average and circumcenter laws, both achieving rendezvous, and of the centroid law, achieving deployment over a region of interest. The results are derived via novel analysis methods, including a set of results on the convergence rates of linear dynamical systems defined by tridiagonal Toeplitz and circulant matrices.}, Address = {Seville, Spain}, Author = {S. Mart{\'\i}nez and F. Bullo and J. Cort\'es and E. Frazzoli}, Booktitle = {Proc. of the IEEE Conf. on Decision and Control}, Date-Added = {2005-03-08 16:47:28 -0800}, Date-Modified = {2011-01-19 22:40:11 -0500}, Keywords = {Robotic Networks}, Local-Url = {/www/papers/Martinez.Bullo.ea.CDC05b.DRAFT.pdf}, Month = {December}, Pages = {8313--8318}, Pdf = {http://rigoletto.seas.ucla.edu/papers/Martinez.Bullo.ea.CDC05b.DRAFT.pdf}, Title = {On synchronous robotic networks --- {Part II:} Time complexity of rendezvous and deployment algorithms}, Year = {2005}, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QUS4uLy4uLy4uLy4uL0xpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvTWFydGluZXouQnVsbG8uZWEuQ0RDMDViLkRSQUZULnBkZtIXCxgZV05TLmRhdGFPEQHgAAAAAAHgAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADGq0O2SCsAAAAWB0wfTWFydGluZXouQnVsbG8uZWEuQ0QjMTYwQUQzLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABYK08MVUhMAAAAAAAAAAAAEAAUAAAkgAAAAAAAAAAAAAAAAAAAABnBhcGVycwAQAAgAAMare/YAAAARAAgAAMMVilMAAAABABAAFgdMA50MdAOdDHIDmbV4AAIAU01hY2ludG9zaCBIRDpMaWJyYXJ5OgBXZWJTZXJ2ZXI6AERvY3VtZW50czoAcGFwZXJzOgBNYXJ0aW5lei5CdWxsby5lYS5DRCMxNjBBRDMucGRmAAAOAEYAIgBNAGEAcgB0AGkAbgBlAHoALgBCAHUAbABsAG8ALgBlAGEALgBDAEQAQwAwADUAYgAuAEQAUgBBAEYAVAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIARUxpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvTWFydGluZXouQnVsbG8uZWEuQ0RDMDViLkRSQUZULnBkZgAAEwABLwD//wAAgAbSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBVAGAAZwBqAGwAbgBxAHMAdQB3AIQAjgDiAOcA7wLTAtUC2gLlAu4C/AMAAwcDEAMVAyIDJQM3AzoDPwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANB} }
In this paper, we study the following problem: given $n$ vehicles and origin-destination pairs in the plane, what is the minimum time needed to transfer each vehicle from its origin to its destination, avoiding conflicts with other vehicles? The environment is free of obstacles, and a conflict occurs when the distance between any two vehicles is smaller than a velocity-dependent safety distance. We derive lower and upper bounds on the time needed to complete the transfer, in the case in which the origin and destination points can be chosen arbitrarily, proving that the transfer takes $\Theta(\sqrt{n}\bar L)$ time to complete, where $\bar L$ is the average distance between origins and destinations. We also analyze the case in which origin and destination points are generated randomly according to a uniform distribution, and present an algorithm providing a constructive upper bound on the time needed for complete the transfer, proving that in the random case the transfer requires $O(\sqrt{n \log n})$ time.
@conference{Savchenko.Frazzoli:ACC05, Abstract = { In this paper, we study the following problem: given $n$ vehicles and origin-destination pairs in the plane, what is the minimum time needed to transfer each vehicle from its origin to its destination, avoiding conflicts with other vehicles? The environment is free of obstacles, and a conflict occurs when the distance between any two vehicles is smaller than a velocity-dependent safety distance. We derive lower and upper bounds on the time needed to complete the transfer, in the case in which the origin and destination points can be chosen arbitrarily, proving that the transfer takes $\Theta(\sqrt{n}\bar L)$ time to complete, where $\bar L$ is the average distance between origins and destinations. We also analyze the case in which origin and destination points are generated randomly according to a uniform distribution, and present an algorithm providing a constructive upper bound on the time needed for complete the transfer, proving that in the random case the transfer requires $O(\sqrt{n \log n})$ time. }, Address = {Portland, OR}, Author = {M. Savchenko and E. Frazzoli}, Booktitle = {Proc. of the American Control Conference}, Date-Added = {2004-11-02 17:34:45 -0800}, Date-Modified = {2011-01-19 22:42:20 -0500}, Keywords = {Robotic Networks}, Local-Url = {/www/papers/Savchenko.Frazzoli.ACC05.pdf}, Month = {June}, Pages = {3536--3541}, Title = {On the Time Complexity of Conflict-Free Vehicle Routing}, Volume = {5}, Year = {2005}, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QSy4uLy4uLy4uLy4uL0xpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvU2F2Y2hlbmtvLkZyYXp6b2xpLkFDQzA1LnBkZtIXCxgZV05TLmRhdGFPEQHKAAAAAAHKAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADGq0O2SCsAAAAWB0wcU2F2Y2hlbmtvLkZyYXp6b2xpLkFDQzA1LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABYK5cMVU70AAAAAAAAAAAAEAAUAAAkgAAAAAAAAAAAAAAAAAAAABnBhcGVycwAQAAgAAMare/YAAAARAAgAAMMVi/0AAAABABAAFgdMA50MdAOdDHIDmbV4AAIAUE1hY2ludG9zaCBIRDpMaWJyYXJ5OgBXZWJTZXJ2ZXI6AERvY3VtZW50czoAcGFwZXJzOgBTYXZjaGVua28uRnJhenpvbGkuQUNDMDUucGRmAA4AOgAcAFMAYQB2AGMAaABlAG4AawBvAC4ARgByAGEAegB6AG8AbABpAC4AQQBDAEMAMAA1AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgA/TGlicmFyeS9XZWJTZXJ2ZXIvRG9jdW1lbnRzL3BhcGVycy9TYXZjaGVua28uRnJhenpvbGkuQUNDMDUucGRmAAATAAEvAP//AACABtIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFUAYABnAGoAbABuAHEAcwB1AHcAhACOANwA4QDpArcCuQK+AskC0gLgAuQC6wL0AvkDBgMJAxsDHgMjAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAAyU=} }
In this paper we propose some novel planning and routing strategies for Dubins' vehicle, i.e., for a nonholonomic vehicle moving along paths with bounded curvature, without reversing direction. First, we study a stochastic version of the Traveling Salesperson Problem (TSP): given n targets randomly sampled from a uniform distribution in a rectangle, what is the shortest Dubins' tour through the targets and what is its length? We show that the expected length of such a tour is Omega(n^(2/3) ) and we propose a novel algorithm that generates a tour of length O(n^(2/3) log(n)^(1/3) ) with high probability. Second, we study a dynamic version of the TSP (known as ``Dynamic Traveling Repairperson Problem'' in the Operations Research literature): given a stochastic process that generates targets, is there a policy that allows a Dubins vehicle to stabilize the system, in the sense that the number of unvisited targets does not diverge over time? If such policies exist, what is the minimum expected waiting period between the time a target is generated and the time it is visited? We propose a novel receding-horizon algorithm whose performance is almost within a constant factor from the optimum.
@conference{Savla.Bullo.ea:CDC05, Abstract = { In this paper we propose some novel planning and routing strategies for Dubins' vehicle, i.e., for a nonholonomic vehicle moving along paths with bounded curvature, without reversing direction. First, we study a stochastic version of the Traveling Salesperson Problem (TSP): given n targets randomly sampled from a uniform distribution in a rectangle, what is the shortest Dubins' tour through the targets and what is its length? We show that the expected length of such a tour is Omega(n^(2/3) ) and we propose a novel algorithm that generates a tour of length O(n^(2/3) log(n)^(1/3) ) with high probability. Second, we study a dynamic version of the TSP (known as ``Dynamic Traveling Repairperson Problem'' in the Operations Research literature): given a stochastic process that generates targets, is there a policy that allows a Dubins vehicle to stabilize the system, in the sense that the number of unvisited targets does not diverge over time? If such policies exist, what is the minimum expected waiting period between the time a target is generated and the time it is visited? We propose a novel receding-horizon algorithm whose performance is almost within a constant factor from the optimum. }, Address = {Seville, Spain}, Author = {K. Savla and F. Bullo and E. Frazzoli}, Booktitle = {Proc. IEEE Conf. on Decision and Control}, Date-Added = {2005-03-06 22:29:51 -0800}, Date-Modified = {2011-01-19 22:20:21 -0500}, Keywords = {Motion Planning}, Local-Url = {~/papers/cdc05/dtsp/Savla.Bullo.ea.CDC05.pdf}, Month = {December}, Note = {Best student paper finalist.}, Pages = {4530--4535}, Pdf = {http://rigoletto.seas.ucla.edu/papers/Savla.Bullo.ea.CDC05.pdf}, Title = {On {T}raveling {S}alesperson {P}roblems for {D}ubins' vehicle: stochastic and dynamic environments}, Year = {2005} }
In this paper we study the length of optimal paths for Dubin's vehicle, i.e., a vehicle constrained to move forward along paths of bounded curvature. First, we obtain an upper bound on the optimal length in the point-to-point problem. Next, we consider the corresponding Traveling Salesperson Problem (TSP). We provide an algorithm with worst-case performance within a constant factor approximation of the optimum. We also establish an asymptotic bound on the worstcase length of the Dubin's TSP.
@conference{Savla.Frazzoli.ea:ACC05, Abstract = {In this paper we study the length of optimal paths for Dubin's vehicle, i.e., a vehicle constrained to move forward along paths of bounded curvature. First, we obtain an upper bound on the optimal length in the point-to-point problem. Next, we consider the corresponding Traveling Salesperson Problem (TSP). We provide an algorithm with worst-case performance within a constant factor approximation of the optimum. We also establish an asymptotic bound on the worstcase length of the Dubin's TSP.}, Address = {Portland, OR}, Author = {K. Savla and E. Frazzoli and F. Bullo}, Booktitle = {Proc. of the American Control Conference}, Date-Added = {2005-03-06 04:31:19 -0800}, Date-Modified = {2011-01-19 22:25:52 -0500}, Keywords = {Motion Planning}, Local-Url = {/www/papers/Savla.Frazzoli.ea.ACC05.pdf}, Month = {June}, Pages = {786--791}, Pdf = {http://rigoletto.seas.ucla.edu/papers/Savla.Frazzoli.ea.ACC05.pdf}, Title = {On the point-to-point and traveling salesperson problems for {D}ubins' vehicles}, Volume = {2}, Year = {2005}, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QSi4uLy4uLy4uLy4uL0xpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvU2F2bGEuRnJhenpvbGkuZWEuQUNDMDUucGRm0hcLGBlXTlMuZGF0YU8RAcYAAAAAAcYAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMarQ7ZIKwAAABYHTBtTYXZsYS5GcmF6em9saS5lYS5BQ0MwNS5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAFgrowxVTzQAAAAAAAAAAAAQABQAACSAAAAAAAAAAAAAAAAAAAAAGcGFwZXJzABAACAAAxqt79gAAABEACAAAwxWMDQAAAAEAEAAWB0wDnQx0A50McgOZtXgAAgBPTWFjaW50b3NoIEhEOkxpYnJhcnk6AFdlYlNlcnZlcjoARG9jdW1lbnRzOgBwYXBlcnM6AFNhdmxhLkZyYXp6b2xpLmVhLkFDQzA1LnBkZgAADgA4ABsAUwBhAHYAbABhAC4ARgByAGEAegB6AG8AbABpAC4AZQBhAC4AQQBDAEMAMAA1AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgA+TGlicmFyeS9XZWJTZXJ2ZXIvRG9jdW1lbnRzL3BhcGVycy9TYXZsYS5GcmF6em9saS5lYS5BQ0MwNS5wZGYAEwABLwD//wAAgAbSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBVAGAAZwBqAGwAbgBxAHMAdQB3AIQAjgDbAOAA6AKyArQCuQLEAs0C2wLfAuYC7wL0AwEDBAMWAxkDHgAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAMg} }
Mobility has been shown to increase the capacity of wireless networks. As the number of mobile entities in a bounded environment increases, traffic congestion occurs and these entities have to slow down to avoid colliding physically with their neighbors. This increases the time a mobile entity takes to physically carry data from one point in the environment to another. In this paper, we provide a lower bound on the maximum delay that it takes in delivering data in networks where mobility is used to achieve constant throughput per node. We also show that this delay is achievable for some networks.
@conference{Sharma.Frazzoli.ea:CDC05, Abstract = {Mobility has been shown to increase the capacity of wireless networks. As the number of mobile entities in a bounded environment increases, traffic congestion occurs and these entities have to slow down to avoid colliding physically with their neighbors. This increases the time a mobile entity takes to physically carry data from one point in the environment to another. In this paper, we provide a lower bound on the maximum delay that it takes in delivering data in networks where mobility is used to achieve constant throughput per node. We also show that this delay is achievable for some networks. }, Address = {Seville, Spain}, Author = {V. Sharma and E. Frazzoli and P.~G. Voulgaris}, Booktitle = {Proc. of the IEEE Conf. on Decision and Control}, Date-Added = {2005-03-08 16:42:49 -0800}, Date-Modified = {2011-01-19 23:06:08 -0500}, Keywords = {Sensor Networks; Robotic Networks; UAVs/Autonomous Systems}, Local-Url = {/www/papers/Sharma.Frazzoli.ea.CDC05.DRAFT.pdf}, Month = {December}, Pages = {1149--1154}, Pdf = {/papers/Sharma.Frazzoli.ea.CDC05.pdf}, Title = {Delay in Mobility-Assisted Constant-Throughput Wireless Networks}, Year = {2005}, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QUS4uLy4uLy4uLy4uL0xpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvU2hhcm1hLkZyYXp6b2xpLmVhLkNEQzA1LkRSQUZULnBkZtIXCxgZV05TLmRhdGFPEQHgAAAAAAHgAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADGq0O2SCsAAAAWB0wfU2hhcm1hLkZyYXp6b2xpLmVhLkMjMTYwQUVFLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABYK7sMVU+UAAAAAAAAAAAAEAAUAAAkgAAAAAAAAAAAAAAAAAAAABnBhcGVycwAQAAgAAMare/YAAAARAAgAAMMVjCUAAAABABAAFgdMA50MdAOdDHIDmbV4AAIAU01hY2ludG9zaCBIRDpMaWJyYXJ5OgBXZWJTZXJ2ZXI6AERvY3VtZW50czoAcGFwZXJzOgBTaGFybWEuRnJhenpvbGkuZWEuQyMxNjBBRUUucGRmAAAOAEYAIgBTAGgAYQByAG0AYQAuAEYAcgBhAHoAegBvAGwAaQAuAGUAYQAuAEMARABDADAANQAuAEQAUgBBAEYAVAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIARUxpYnJhcnkvV2ViU2VydmVyL0RvY3VtZW50cy9wYXBlcnMvU2hhcm1hLkZyYXp6b2xpLmVhLkNEQzA1LkRSQUZULnBkZgAAEwABLwD//wAAgAbSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBVAGAAZwBqAGwAbgBxAHMAdQB3AIQAjgDiAOcA7wLTAtUC2gLlAu4C/AMAAwcDEAMVAyIDJQM3AzoDPwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANB} }
This paper proposes a formal model for a network of robotic agents that move and communicate. Building on concepts from distributed computation, robotics and control theory, we define notions of robotic network, control and communication law, coordination task, and time and communication complexity. We then analyze a number of basic motion coordination algorithms such as pursuit, rendezvous and deployment.
@electronic{Martinez.Cortes.ea:ARX05, Abstract = {This paper proposes a formal model for a network of robotic agents that move and communicate. Building on concepts from distributed computation, robotics and control theory, we define notions of robotic network, control and communication law, coordination task, and time and communication complexity. We then analyze a number of basic motion coordination algorithms such as pursuit, rendezvous and deployment.}, Author = {S. Mart\`inez and F. Bullo and J. Cort\'es and E. Frazzoli}, Date-Added = {2004-10-27 15:58:14 -0700}, Date-Modified = {2007-10-20 21:06:11 -0400}, Keywords = {Robotic Networks}, Local-Url = {/www/papers/Martinez.Bullo.ea.ARX05.pdf}, Month = {January}, Pdf = {http://arxiv.org/pdf/math.OC/0501499}, Title = {Synchronous robotic networks and complexity of control and communication laws}, Url = {http://arxiv.org/pdf/math.OC/0501499}, Urldate = {January 2005}, Year = {2005}, Bdsk-Url-1 = {http://arxiv.org/pdf/math.OC/0501499} }
In this paper, we consider a sensor network consisting of a set of sensors deployed in a two-dimensional region. This network of sensors is required to sense a random scalar field and transport these values to a collector node where this field is reconstructed using this data. The number of times this task can be repeated is termed as the functional lifetime of the sensor network. The maximum mean square error of a snapshot of the field generated at the collector node is the maximum distortion. We consider the problem of sensor placement and routing measurements so as to maximize the functional lifetime and minimize maximum distortion. A centralized gradient descent approach is developed where both quantities are improved at each iteration starting from an initial sensor placement. This scheme requires solving convex programs at each iteration. The centralized algorithm can be used to improve upon any sensor placement strategy. We then consider situations where the initial deployment of sensors cannot be controlled. Post-deployment strategies for each sensor, that require them to run convex programs using only local information, are developed that can be employed to move to a new position so as to increase functional lifetime and decrease maximum distortion.
@unpublished{Sharma.Frazzoli.ea:TSN05, Abstract = {In this paper, we consider a sensor network consisting of a set of sensors deployed in a two-dimensional region. This network of sensors is required to sense a random scalar field and transport these values to a collector node where this field is reconstructed using this data. The number of times this task can be repeated is termed as the functional lifetime of the sensor network. The maximum mean square error of a snapshot of the field generated at the collector node is the maximum distortion. We consider the problem of sensor placement and routing measurements so as to maximize the functional lifetime and minimize maximum distortion. A centralized gradient descent approach is developed where both quantities are improved at each iteration starting from an initial sensor placement. This scheme requires solving convex programs at each iteration. The centralized algorithm can be used to improve upon any sensor placement strategy. We then consider situations where the initial deployment of sensors cannot be controlled. Post-deployment strategies for each sensor, that require them to run convex programs using only local information, are developed that can be employed to move to a new position so as to increase functional lifetime and decrease maximum distortion. }, Author = {V. Sharma and E. Frazzoli and P.~G. Voulgaris}, Date-Added = {2005-11-28 18:20:22 -0800}, Date-Modified = {2008-07-18 14:31:41 -0400}, Keywords = {Sensor Networks; Robotic Networks}, Month = {November}, Pdf = {http://rigoletto.seas.ucla.edu/papers/Sharma.Frazzoli.ea.TSN05.DRAFT.pdf}, Title = {Using Mobility for Sensor Placement to Increase Functional Lifetime and Decrease Sensing Distortion}, Year = {2005} }
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
This document was translated from BibT_{E}X by bibtex2html