12
$\begingroup$

I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, nonlinear, optimal, stochastic), advanced signal processing and convex optimization.

I am trying to figure out a good area to tackle for my dissertation paper and I was wondering whether I can somehow relate to some TCS subject.

The only area that I can think of it could relate is optimization, but I don't have anything particular in mind, the whole subject being very interesting.

It would be great if you could share which topic you think belongs to both worlds.

PS: This question might be totally out of the scope of this Q&A site, so I totally agree if you feel like it's worth closing. Thanks!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ So you are basically asking if there are any theoretical computer science approaches to control theory? $\endgroup$
    – András Salamon
    Oct 13, 2010 at 9:36
  • $\begingroup$ Yes, it should be plenty of results from TCS that can be applied in control theory and I am interested in which are those. $\endgroup$
    – hyperboreean
    Oct 13, 2010 at 9:39
  • $\begingroup$ Thanks Kaveh, I've edited the title to be more suggestive. $\endgroup$
    – hyperboreean
    Oct 13, 2010 at 10:31
  • $\begingroup$ y, thanks to the latest dependencied , space problem , where would i keep academic material i am practically tacking naturally throw-out but I will read more this before obvious whole interest now. $\endgroup$
    – herberto silva
    Aug 16, 2021 at 16:04
  • $\begingroup$ Congestion control (in networks) is sort of in the intersection of control theory and TCS. (example of applying TCS in this context: doi.org/10.1109/SFCS.2002.1181953) $\endgroup$
    – Neal Young
    Aug 16, 2021 at 23:04

8 Answers 8

Reset to default
10
$\begingroup$

Since you mentioned signal processing, you should look at the area of "compressive sensing". Here is an excellent non-technical description of the main ideas involved: http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/

Improve this answer
$\endgroup$
0
7
$\begingroup$

You might want to see if there are any problems in verifying hybrid systems (aka cyberphysical systems) that you want to tackle. The interaction of discrete control with continuous systems is pretty fascinating, and lets you add some logic and model theory to control theory, and it has many useful applications, too (ie, any time a computer interacts with the world!).

Andre Platzer's homepage has a pretty good summary of this area.

Improve this answer
$\endgroup$
6
$\begingroup$

Another possible connection to explore is the use of coinduction and coalgebraic techniques for reasoning about control theoretic systems. Jan Rutten did some work in this directions some years ago, namely:

  • J.J.M.M. Rutten Coalgebra, concurrency, and control. In: R. Boel and G. Stremersch (eds.), Discrete Event Systems (analysis and control), Proceedings of WODES 2000 (5th Workshop on Discrete Event Systems), Kluwer, 2000, pp. 31--38. (This link to the paper seems to be broken, though).

The coalgebraic tecnology has advanced in the last 10 years, though I don't know whether the connection has been further explored. Edit Jan Komenda (and here) seems to have been following up the connection.

Other possible approaches could involve using process algebra, I/O automata, interface automata, and hybrid variants of these things. The interface automata have a very strong game theoretic feeling which corresponds closely to somethings done in control theory, namely, the distinction between controllable and uncontrollable actions can be though of as actions being played by two different players. I'm not sure whether anything has been done in that area. The connection seems quite obvious.

A final connection that could be worth exploring is between control theory and epistemic logic. The connection can be seen via the games analogy. What does each party know? How can they use that to achieve a suitable outcome in the system being controlled?

Improve this answer
$\endgroup$
5
$\begingroup$

Robotics (or as it is all too often called these days, "cyberphysical systems") is a good source of problems that require both control theory and algorithms. See Steve Lavalle's Planning Algorithms for a good intro.

Improve this answer
$\endgroup$
3
$\begingroup$

Social choice seems to be a nice area at the crossroads of many fields: control theory, complexity, etc. Moreover, it is always a surprise (I mean to me) to see that the problems of the guys from the dept of economics are almost the same as the ones we are trying to solve... Believe me, it is worth having a coffee with them (and let them pay, they won't mind ;)).

Improve this answer
$\endgroup$
3
$\begingroup$

A good area to explore could be the theory of optimal control (i.e., controlling a system while minimizing some given cost function), which was mainly developed by Richard Bellman, together with the dynamic programming paradigm, that is now ubiquitous in computer science.

A very useful application of optimal control is found, e.g., in Markov decision processes: a dynamical system is modeled by a Markov chain which can be altered by using some admissible policies. Costs are given for transitions and/or controls and one is usually interested in finding a policy that minimizes the total/average/discounted cost for a finite/infinite temporal horizon. This can be accomplished, e.g., by formulating a suitable Hamilton-Jacobi-Bellman equation for the system and then solving it by means of dynamic programming (many other methods exist depending on the systems).

Hence a natural application is in stochastic optimization settings in which the dynamical system can be modeled as Markovian. A standard reference for optimal control is:

  • Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific.
Improve this answer
$\endgroup$
1
$\begingroup$

How about using optimization algorithms (such as Simulated Annealing or Genetic) to tune the parameters of your choice of control loop algorithm?

Improve this answer
$\endgroup$
0
$\begingroup$

There is some work on robust/private control that would benefit from a cryptographic perspective

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.