MODELING, CONTROL AND OPTIMIZATION OF COMPLEX SYSTEMS In Honor ofProfessor Yu-Chi Ho THE KLUWER INTERNATIONAL SERIES ON DISCRETE EVENT DYNAMIC SYSTEMS Series Editor Yu-ChiHo HarvardUniversity SUPERVISIONOFPETRINETS GeertStremersch ISBN: 0-7923-7486-X ANALYSISOFMANUFACTURINGENTERPRISES:AnApproachto LeveragingValueDeliveryProcesses/orCompetitiveAdvantage N. Viswanadham ISBN:0-7923-8671-X INTRODUCTIONTODISCRETEEVENTSYSTEMS ChristosG. Cassandras,StephaneLafortune ISBN: 0-7923-8609-4 OBJECT·ORIENTEDCOMPUTERSIMULATIONOFDISCRETE·EVENT SYSTEMS JerzyTyszer ISBN: 0-7923-8506-3 TIMEDPETRINETS: TheoryandAppUcation JiacunWang ISBN: 0-7923-8270-6 SUPERVISORYCONTROLOFDISCRETEEVENTSYSTEMSUSINGPETRI NETS JohnO.MoodyandPanosJ. Antsaklis ISBN:0-7923-8199-8 GRADIENTESTIMATIONVIA PERTURBATIONANALYSIS P.Glasserman ISBN: 0-7923-9095-4 PERTURBATIONANALYSISOFDISCRETEEVENTDYNAMICSYSTEMS Yu-ChiHoandXi-RenCao ISBN: 0-7923-9174-8 PETRI NETSYNTHESISFORDISCRETEEVENTCONTROLOF MANUFACTURINGSYSTEMS MengChuZhouandFrankDiCesare ISBN: 0-7923-9289-2 MODELINGANDCONTROLOFLOGICALDISCRETEEVENTSYSTEMS RatneshKumarandVijayK.Garg ISBN: 0-7923-9538-7 UNIFORM RANDOM NUMBERS: THEORYANDPRACTICE ShuTezuka ISBN: 0-7923-9572-7 MODELING, CONTROL AND OPTIMIZATION OF COMPLEX SYSTEMS In Honor of Professor Yu-Chi Ho edited by WeiboGong University ofM assachusetts, Amherst Leyuan Shi University ofWisconsin, Madison SPRINGER SCIENCE+BUSINESS MEDIA, LLC Library of Congress Cataloging-in-Publication Data Modeling, control and optimization of complex systems : in honor of Professor Yu-Chi Hol edited by Weibo Gong, Leyuan Shi. p. cm.--(Kluwer international series on discrete event dynamic systems ; 14) Includes bibliographical references. ISBN 978-1-4613-5411-6 ISBN 978-1-4615-1139-7 (eBook) DOI 10.1007/978-1-4615-1139-7 1. Control theory. 2. System analysis. 3. Mathematical optimization. 1. Ho, Yu-Chi, 1934- II. Gong, Weibo. III. Shi, Leyuan. IV. Series. QA402.3 .M57 2002 003'.5--dc21 2002028784 Copyright @ 2003 by Springer Science+Business Media New York Origina1ly published by Kluwer Academic Publishers in 2003 Softcover reprint ofthe hardcover lst edition 2003 AlI rights reserved. No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording, or otherwise, without the written permis sion from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Permission for books published in Europe: [email protected] Permissions for books published in the United States of America: [email protected] Printed an acid-free paper. Contents List ofFigures vii List ofTables xi Foreword xiii Acknowledgements xv 1OptimalRepresentationand VisualizationofMultivariateDataandFunc- tions in Low-Dimensional Spaces 1 Jian Song 2Modeling ofComplex Systems 19 K.J. Astrom 3 Power Control in ad hoc Wireless Networks: An Architectural Solution for a Melee ofMultiple Agents, Cost Criteria),and Information Pattern 47 Swetha Narayanaswamy, Vikas Kawadia, R. S. .)reenivas and P. R. Kumar 4Some Examples ofOptimal Control 63 A. E. Bryson 5 Adaptive Control Using Multiple Models: A Methodology 83 Kumpati S. Narendra, Osvaldo A. Driollet and Koshy George 6 Constrained Control: Polytopic Techniques 111 D. Q. Mayne 7 An Introduction to Constrained Control 131 Graham C. Goodwin and Tristan Perezand Jose A. De Dona 8 On Feasibility of Interplanetary Travel: The Flight from Earth to Mars ~B~ IN Angelo Miele vi MODELING, CONTROL AND OPTIMIZATION OF COMPLEX SYSTEMS 9 Linear Quadratic Control Revisited 195 David D. Yao , Shv.zhong Zhang and Xv.n Yv. Zhov. 10 Discrete Events: Timetables, Capacity Questions, and Planning Issues for Railway Systems 237 Geert Jan Olsderand Antoine F. de Kort 11 A Sensitivity View of Markov Decision Processes and Reinforcement Learning 261 Xi-Ren Cao 12 Optimal Control for Discrete Event and Hybrid Systems 285 Christos G. Cassandras and Kagan Gokbayrak List of Figures 2.1 Block diagram as an illustrationofinformation hid- ing. From [50]. 22 2.2 Asimple hydraulicsystem withan inflow and a free outflow is shown in A. The block diagram represen- tation ofthe system is shown in B. The system ob- tainedbyconnectingtwo hydraulicsystemsisshown in C. This system cannot be represented by the se- ries connection ofthe block diagrams in B. 24 2.3 Illustratestwosituationswherestatesdisappearwhen two systems are connected. 26 2.4 Schematic picture ofsteam generator. 33 2.5 Comparison of model (solid line) and plant data (dots) for perturbationsinsteamflowrateat medium load, from [7]. 38 2.6 Comparison of model (solid line) and plant data (dots) for perturbations in steam flow rate at high load, from [7]. 39 3.1 An ad hoc network. 49 3.2 A network with 500 nodes randomly located in a square. The graph on the left shows the edges lying "f't minimum power routes for path loss. The graph on the right is for ~. It is clearly a sub-graph of that on the left. 52 3.3 The architecture of the COMPOW power control protocol whichexploits the port demultiplexingfea- ture ofUDP. 55 3.4 The software implementation of COMPOW in the Linux kerneL 55 4.1 Nomenclature for a Bicycle Robot 64 4.2 Stroboscopic Movie ofBicycle Making an S-Turn 64 viii MODELING, CONTROL AND OPTIMIZATION OF COMPLEX SYSTEMS 4.3 Nomenclature for a Unicycle Robot 65 4.4 Stroboscopic Movie ofa Unicycle Making an S-Turn 66 4.5 Nomenclature for a Thuck with a Thailer 67 4.6 Stroboscopic Movie of a Thuck-Thailer Backing Up to a Loading Dock; Case 1 67 4.7 Stroboscopic Movie of a Thuck-Trailer Backing Up to a Loading Dock; Case 2 67 4.8 Nomenclature for a Thuck with Two Thailers 68 4.9 Stroboscopic Movie of a Truck with Two Thailers Making a 90 Degree Turn 69 4.10 Nomenclature for a Cart with a Double Pendulum 70 4.11 StroboscopicMovieoftheThanslationofa Cartwith a Double Pendulum 70 4.12 Nomenclaturefor a Cart witha DoubleInverted Pendulum 71 4.13 StroboscopicMovieoftheTranslationofa Cartwith a Double Inverted Pendulum 72 4.14 Nomenclature for Erection of a Pendulum Using Bounded Force on a Cart 73 4.15 Stroboscopic Movie ofthe Minimum Time Erection ofa Pendulum Using Bounded Force on a Cart 74 4.16 Nomenclature for Two Link Robot Arm 75 4.17 Stroboscopic Movie ofa Two Link Robot Making a Minimum Time Pick and Place Motion 75 4.18 Nomenclature for a Flexible Robot Arm 76 4.19 Stroboscopic Movie of a Minimum Effort Pick and Place Motion ofa Flexible Robot Arm 76 4.20 Nomenclature for Stick-Person Robot 77 4.21 Stroboscopic Movie of a Stick-Person Robot Doing Knee Bends 78 4.22 Nomenclature for Planetary Gear Rolling on a Sun Gear 79 4.23 Stroboscopic Movie ofa Planetary Gear Rolling on a Sun Gear; Case 1 80 4.24 Stroboscopic Movie ofa Planetary Gear Rolling on a Sun Gear; Case 2 81 5.1 Multiple model, switching and tuning scheme. 87 5.2 Switching according to Ji = 1Ef=le~(k). 98 5.3 The states of a third order nonlinear system when adaptively controlled using one model (Parts (a)- (c)) and using multiple models (Parts (d)-(f)). 102 5.4 Modifieddirect adaptivecontrol for a benchmarkexample. 104 List ofFigures ix 5.5 Theperformanceofa secondordernonlinearsystem when adaptively controlled using multiple models. 105 7.1 Simplified anti-windup control loop. 134 7.2 Anti-wind up scheme for state variable control. 135 7.3 Set boundaries for the example. (In the case ofZN an estimate obtained numerically is shown. Note that 0 C ZN C YN.) 155 00 7.4 92(A,'TI,0'2) andd92(A,'TI,0'2)/d'TIfor different values of0'2 and for A = 5. 165 7.5 Standardnotationandsignconventionsfor shipmo- tion description. 170 7.6 Ship Motion with no constraints on the rudder. 172 7.7 Shipmotion whenthe rudder isconstrainedto max- imum angle of30 deg. and maximum rate of 15 deg/sec. 173 8.1 Minimumenergy trajectory ininterplanetaryspace, Suncoordinates, totaltime=970.0days, staytimein LMO=454.3days, total velocityimpulse=11.30km/s, no midcourse impulse. 190 8.2 Fast trajectory in interplanetary space, Sun coor- dinates, total time=440.0 days, stay time in LMO =30.0 days, total velocity impulse =20.79 km/s, outgoing trip midcourse impulse 191 10.1 The Dutch intercity network 239 10.2 Distances along HSL South and its three tunnels 241 10.3 The two stations example 242 10.4 Layout ofthe generic building block 251 10.5 The geographical location ofHSL South 252 10.6 Long-run inter-departure times at HSL South for varying train amounts 258 11.1 The Example 276 11.2 The Relations Among PA, MDP and RL 281 12.1 Hybrid Controller Operation 293 12.2 Typical state trajectory 299 List of Tables 8.1 Phaseangletravelofspacecraft, Earth, and Mars(loops around Sun) for a round-trip LEO-LMO-LEO 189 8.2 '!ravel/stay times[days] for a round-trip LEO-LMO-LEO 189 8.3 Characteristicvelocities[km/s] fora round-tripLEO- LMO-LEO. 192 = :11 = 8.4 Mass ratios 'T/i for interplanetary flight, € = O.lO,lsp 4508 192 8.5 Massratios'T/i=...!!!L forplanetaryfiight,€ = 0.10,lsp = mi+l 4508 192 8.6 Cumulative mass ratios for round-trip Earth-Mars- = = Earth,€ 0.10,lsp 4508. 193 10.1 Speed restrictions at HSL South tunnels for TGV trains 257 10.2 Main characteristics for TGV2 trains 257