This semester I have taken a robotics course. From that robotic course I learn something: something very intuitive and very original. Complex behavior doesn’t necessarily mean complex algorithm. Complex behavior can be achieved from the combination of very simple behaviors. This is called reactive approach in traditional robotic literature. I was thinking one step ahead of it. It may not make any sense but it is just an idea. Actually I don’t have much time to explore it further. If anybody found it interesting then I would be happy to talk to him/her for further detail. Here is the idea:
We solve lot of complicated problems in our everyday life with limited problem size. “Complicated” here means NP-Hard or NP-complete. Does it necessarily means we have a very complicated exponential algorithm running in our brain? I think this is not always true. Sometimes, we solve some complicated problems almost without any deliberation. Now, my point is how do we achieve it? Sometime people call it intuition. Then what is intuition? To me, intuition is nothing but a complicated and controlled collaboration of some simple behaviors. In our daily life we solve a bunch of optimization problem. But we just can’t solve the same problem with higher input size.
This behavior based approach tempted me to look further for the different type of computing. The new approach should have lot of small computing unit in it and the approach must have an architecture to facilitate the collaboration between the components. Each of the components will know what is the problem or sub problem it can solve and what are the output it can provide. Like reactive robotics, all the components find a problem fits with its input domain will try to solve it completely or partially. Finally the combination of all the results will be our final result. If I sound reasonable so far then the success of this approach depends a lot upon how to combine the results? I am suggesting the same approach for the combination of the results. There would be couple of components who knows what kind of results they are capable to deal with and how to combine them. I am proposing output fusion in this point. Finally they will combine the results. The process continues until we found a single component working on the next level results and produce a single output and no component fit the current output with its own input domain. Let say, for the fun of it I fixed a name, may be “reactive computing”.
Well couple of questions may come at first, what is the difference with ubiquitous computing? Well first of all in the ubiquitous computing components are working with different sub-problems and each of them provides the solution. One output might be the input of another and so forth. But here in reactive computing it is not controlled and it is fuzzier from any sorts of ubiquitous computing. So the computation itself and the result are kind of uncertain. It depends on how many components it has, how each of the components works, how they combine and so forth. Now the next question is it a non deterministic algorithm? Well I would say the result is non-deterministic not the algorithm is.
It’s just an idea, an idea from an idle mind. I know there are lot fuzziness is still out there but it could be something to give a shot. I would like hear the comments and criticisms.
wow !!!
ReplyDeleteread 1/2 of it. but looks original. keep it up
The idea worths further formal effort.
ReplyDeleteI want to introduce 'SELF LEARNING' from mistakes here. If a problem finally remains unsolved, the components may exchange information among them, and improve the knowledge base, that will be helpful for solving next one - seems humanly?
ReplyDeleteAnyway, good thinking.
I liked it.
ReplyDeleteHuman takes decision based on experience and just matching current situation with previous situations. So, here all previous experience works as what you called components. The problem with this approach is it produces different result for different set of expetience- so different people takes dicision differently. Some decisions are close to right some are close to wrong- based on the set of components used to take the decision. And yes- we merge our results and try to take a binary dicision from all those.
It seems very interesting- go ahead. I'll be posting comments when I get a new idea- for first one its no use I think :)
1. "The problem with this approach is it produces different result for different set of expetience" -> As I mentioned earlier, the output would be somewhat non-deterministic (for the problem which doesn't have deterministic polynomial algorithm). But the good part of the story is if the deterministic polynomial algorithm is available then a single component (deterministic) can be made for that that type of problem only and deterministic result can be obtained.
ReplyDelete2. "And yes- we merge our results and try to take a binary dicision from all those." -> I would rather say its a convex combination of results (maybe incorrect, but that's another story).
Thanks a lot.
Wow! I meet an interesting student who is working with a very similar idea to some extend. They are not exactly identical but they share few major concepts. The good part is he is not like me. He extends his work beyond the conceptual level a little bit. I am very excited.
ReplyDeleteHi there,
ReplyDeleteI think you're mistaken when you said we solve NP-complete problems in our daily day life. If it was so, why do we need computers to solve these? Human system is complex, but it definitely doesn't imply we solve NP-complete problems. As for example, say an event has 20! ways to occur. Now, we were that smart, we could enumerate all those possibilities and took the best. But, we can't. Not even our smartest creation Von Neumann model of computation can solve it in reasonable time.
Hope I was able to clarify.
I appreciate your writing, anyway.
Good Luck
@Sazzad Bin Kamal: Okay, The word 'solve' very much dependent on the model we are using, if a model is well defined it can solve (or at least can provide a proof of existence of solution) of any well posed problem. The catch is human computation model (aka human brain) is not a well defined model. As off now, in my best knowledge, no computing model exists for human brain; hence it is difficult to proof that human brain can solve NP complete problem. Interestingly, the reverse cannot be proved either. It is assumed, human brain can solve problem non deterministically, hence it might be possible to have solution of NP complete problems using human computing machine. Again, there is no formal proof of this claim.
ReplyDeleteIn my context, when I said the word solution by human, I certainly mean non deterministic, heuristics based solution. I am sorry, I should have been very specific with these words. I tried to avoid the direct claim (we solve NP-complete problems) but now when I am reading again, it seems like it was an indirect claim but the claim was not my argument, it was my motivation.
We need computer to solve the problem, but not necessarily means we only use computer to solve the problem what are beyond our capability. Sometimes the scale of the problem become intractable for human perception or computing system. The human perception system is much weaker than human computing system in terms of completeness. Whatever the reason is, we solve some optimization problems (vision system, balancing system, etc) pretty efficiently (not unique, these solutions are not unique) and machines are far behind us. And such optimization may or may not be achieved by simple collaboration.
Oh, yes. I heard somewhere about protein folding. If I'm not mistaken, the mathematical formulation of this process is proved to be NP-complete. Nature solves it anyway. So they were asking, our neurons don't know something that our DNA knows! My personal assumption is, a proof of P==NP, in contrary to its opposite notion among computer scientists, would come from either bio-informatics/biologist community or programming community. I feel really disturbed when, regardless of all those Big Oh notation , I see certain proved NP-Complete problems are easily solved even with hard instances. Isn't it pity when you see an order of n^3, is solved within fraction of seconds?
ReplyDeleteHappy Posting!
:)
@Sazzad Bin Kamal: "Our neurons don't know something that our DNA knows!" Interesting!
ReplyDelete"I feel really disturbed when, regardless of all those Big Oh notation , I see certain proved NP-Complete problems are easily solved even with hard instances. Isn't it pity when you see an order of n^3, is solved within fraction of seconds?" Would you please clarify a bit further?
"Our neurons don't know something that our DNA knows!"
ReplyDeleteThe difference is scale or perspective! Is it the scale that makes the difference or the perspective?
Hello! Thanks for mentioning it. I think I was wrong when I stated "Our neurons don't know something that our DNA knows!". I read in COSMOS that our body cells are different from neurons. Body cells are meant to keep hereditary information through DNA, while neurons are meant to create 'Knowledge'. Neurons help us to learn. I, mistakenly thought probably, neurons don't have DNA! :P. That's why I thought the information of protein folding is kept in body cells, not in neurons.
ReplyDeleteI just googled and found some exciting info. You can check this group: http://parasol.tamu.edu/groups/amatogroup/research/computationalBio.php
By the way, can I register to your blog posts and comments? Otherwise it is hard to know when you post anything knew or about newer comments.
Best Wishes
Well by "Isn't it pity when you see an order of n^3, is solved within fraction of seconds?" I meant, for even n=100000, desktop PCs are powerful enough to iterate through all these withing several seconds. But, in theory you try to generalize, right? So it seems BIG and impossible. But, in reality you don't work on problems in general but on problem instances.
ReplyDeleteDon't get me wrong, as I'm not an opponent of Theorems. It is just probably our theorems are not still that smart to mean exactly what it says and be applicable verbatim thereby. I read somewhere, that some researcher, probably from SUNY, solved TSP with hard instance in almost linear time. :)
Even if it was not so, one could take any paper and implement it's algorithm and discover the algorithms runs much faster than any one could guess studying asymptotic analysis.
Thanks
@Sazzad Bin Kamal: "Even if it was not so, one could take any paper and implement it's algorithm and discover the algorithms runs much faster than any one could guess studying asymptotic analysis." - Not very sure what exactly you mean?
ReplyDeleteYes it is true we work with problem instances not the whole class. In my view, working with problem instances is very different from work with the entire class and that was idea which makes me think that something ad hoc might be well capable of solving problems.
No I am sorry I don't have any subscription url for individual thread of a post but certainly I do have a subscription url (http://mssadik73.blogspot.com/feeds/posts/default) for entire blog.